1658C - Shinju and the lost permutation

#codeforces

Question link : https://codeforces.com/problemset/problem/1658/C

Pre-requisite : Relationship between \(p\) and \(c\)

In the question, we are given that: > \(c_i\) is the power of the (i - 1)th cyclic-shift of the permutation \(p\)

This means that \(c_1\) is the 0th shift : Which means that is, for that case, the permutation remains as is => \(p_1, p_2, p_3,...,p_n\)

\(c_2\) is the 1st shift : \(p_n, p_1, p_2, ..., p_{n-1}\) \(c_3\) is the 2nd shift : \(p_{n-1}, p_n, p1, p2, ..., p_{n-2}\)

So as you see items in \(c\) from 1st index to nth index, you start with the first item being at the start, then you suddenly go \(p_n\) and come back until \(p_2\)

So: \(c_1 \rightarrow p_1\) \(c_2 \rightarrow p_n\) \(c_3 \rightarrow p_{n-1}\) … \(c_n \rightarrow p_2\)

Where does \(c_i + 1 \geq c_{i+1}\) come from?

Case 1 : \(p_1 > p_n\)

Note that \(p_1\) corresponds to \(c_1\) and \(p_n\) corresponds to \(c_2\)

In this case, the next item that is coming at the start (\(p_n\)) is smaller than the current item. When \(p_n\) was at the last point, it didn’t contribute to \(c_1\) as \(p_n < p_1\), therefore it’s removal from the last point doesn’t affect the \(c\) value of \(p_1\). But now that it has come to the start of the permutation, we can see that the c-value increases by 1. Therefore in this case \(c_i + 1 =c_{i+1}\)

Case 2 : \(p_1 < p_n\)

Note that \(p_1\) corresponds to \(c_1\) and \(p_n\) corresponds to \(c_2\)

Now at the start we are bringing a bigger element.

When \(p_n\) was at the end of the array, it was more than \(p_1\) so it might be contributing to the c-value in that case (this will happen when \(p_n\) is the largest number in \(p\)). So removing it from the last position might decrease the c-value.

Also, when \(p_n\) comes at the start of the array, then it will shadow \(p_1\) and other items smaller than \(p_n\). This means, that the c-value could further decrease.

So we can see that in this case \(c_i \geq c_{i+1}\) (There are cases where the c-value remains the same. Example : 1, 3, 2 has c-value of 2, and 2, 1, 3 also has a c-value of 2)

So by combining \(c_i \geq c_{i+1}\) and \(c_i + 1 = c_{i+1}\) we can say that \(c_i + 1 \geq c_{i+1}\)

How is this condition enough to check whether a valid permutation can be formed?

Let’s first think about what a permutation would look like, when following the condition \(c_i + 1 \geq c_{i+1}\)

This, simply, means that we can have drastic reductions, but increments can only be done in 1s.

Case 1 : Maximum value in \(c\) is \(n\)

In this case, we will have a simple incremental array from 1 to n in \(c\). That is, it will look like : \(1, 2, ..., n\) because we NEED to have a single one, to represent the biggest element in \(p_n\), and we need to reach \(n\) from this value, and we can only increase by 1.

This would generate the simple permutation : \(n, 1, 2, ..., n-1\)

Case 2 : Maximum value in \(c\) is less than \(n\)

In this case, we would have repetitions of numbers in \(c\). Note that we can not have more than one 1 in \(c\). Other numbers can repeat.

So we need to reach this max number (let’s say \(m\)) from 1, and we can increase by one only.

So this can look like : \(1, 2, 3, 4, ..., m, m - 2, m - 1, ...\) Basically an increasing phase, followed by random drops and increases. The increasing phase can also have repetitions, and drops.

In order to construct the array, this construction method : https://codeforces.com/blog/entry/101302?#comment-899615

When the c value increases, then we can simply put a smaller number at the curr position. That will ensure that a correct permutation is being generated.

When the c-value decreases, note that this value would be a repetition - We already would have seen this value atleast once. Why? Because we started from 1, and in order to decrease, we must have reached the current value by increments of 1. That means we have seen all numbers between 1 and the current number. Therefore, all drops / decrements would generate a number, which already has been seen.

Another point to note : Between the previous instance of this number, and the current instance of this number, we either: - Decreased and increased - This would be handled by the “c-value increase” case. - Increased and decreased - This would mean that c-value increased, and decreased to come back at the same point. An “increase” in c-value means a decrease in absolute value in \(p\). Therefore, all numbers between the same instances would be smaller. This simply means that we can indeed have a correct permutation in this case too.

I think these inferences are enough to see that the condition is enough to check whether a valid permutation can be created from the given c-values.

Bangalore to Coorg notes

Trip

Links:

• https://www.youtube.com/watch?v=XFkKjiBVY6M&ab_channel=OffbeatTravel

• https://www.youtube.com/watch?v=DoBTsJEJN4U&ab_channel=90sec

• https://www.youtube.com/watch?v=Xmeo-qVtLQk&ab_channel=CurlyBhavya

• https://www.youtube.com/watch?v=YvF1U2XRfrQ&ab_channel=Tripoto

• https://www.youtube.com/watch?v=Y6uBoh9-ocE&ab_channel=CurlyTales

• https://www.youtube.com/watch?v=Lzxhu-eeUTI&t=7s

Place : Coorg

Plans:

1. Friday, Saturday, Sunday
   1. We reach on Friday morning, go back in Sunday afternoon
   2. Days : Friday, Saturday
   3. Nights, Friday, Saturday

2. Saturday, Sunday
   1. We reach on Saturday morning, and go back in Sunday afternoon

Roads:

• NH75

• Mysore - 2 options

Links:

• https://turuhi.com/resources/route-bangalore-to-coorg/

Choosing option 6 here : https://goo.gl/maps/5NGWo7wLr5WXGk966

Homestays:

• 3 hills (costly ~3.5k per person per day):
  • https://3hills.in/

• MMT has a good list : https://www.makemytrip.com/hotels/hotel-listing/?checkin=12302022&checkout=01012023&locusId=CTXCR&locusType=city&city=CTXCR&country=IN&searchText=Homestay%2C Coorg&roomStayQualifier=2e0e2e0e2e0e&_uCurrency=INR&reference=hotel&homeStay=true&type=city

• Carpe diem stay : https://www.makemytrip.com/hotels/hotel-details/?hotelId=201810101811219537&_uCurrency=INR&checkin=12302022&checkout=01012023&city=CTXCR&country=IN&homeStay=true&lat=12.4233&lng=75.91968&locusId=CTXCR&locusType=city&rank=4&reference=hotel&roomStayQualifier=2e0e2e0e2e0e&searchText=Homestay%2C Coorg&type=city&mtkeys=defaultMtkey
  • Gone

• Done

To visit

• Raja’s seat
  • Right next to our homestay
  • Can cover on Friday

• Mallalli water falls [North] : 1.5 hours from our homestay

• Namdrolling monastery [East] : 1 hour from our homestay

• Sera Jey monastic institute [East] : 1 hr from our homestay

• Dubare elephant camp [East]: On the way to namdrolling monastery
  • 1 hour from our homestay
  • Still water river rafting

• Chelavara water fall [South]
  • 1.25 hour from homestay

• Karike waterfall [West]
  • 1.75 hour from homestay

• Coffee plantation?

• nisargadhama forest park

Activities

River rafting

Links:

• https://traveltriangle.com/blog/river-rafting-in-coorg/

Places :

1. Barapole river rafting base - Fast, not perfect for beginners

2. Dubare river rafting base - Slower, better for beginners

Water will not be turbulent enough. So can skip this.

Cost : 1000 - 2000 per person

Trekking

1. Mandalpatti trek :
   1. Will need a jeep for this : ~1200
   2. Plastic is not allowed
   3. 1 km trek, if via Jeep
   4. No shops

Not a trek I guess

2. Kumara parvatha?

Links :

• https://indiahikes.com/kumara-parvatha-trek

• Most challenging trek in Karnataka

• Not recommended for beginners

3. Kote betta trek

Links :

• https://www.treknomads.com/kotebetta

• https://www.thrillophilia.com/attractions/kote-betta-hill

Points of interest:

• 10 KM in length

• Experienced trekkers can cover in 3-4 hours

• Might be too long for our taste

4. Tadiandamol trek

Links:

• https://indiahikes.com/tadiandamol-trek

Points of interest:

• Around 12 Km from one side, so it’s a long trek.

• Can be ignored in this case

Routes:

1. Kote abbe falls : Good road via makkandaru

2. Abbi falls : Bad road, for offroading

Coffee plantation visit

Links:

• https://www.thrillophilia.com/experiences/coorg-coffee-estate

Can look into this

Food

• Coorg cuisine is good

• Taste of coorg

• Rain tree restaurant

• Ain maine caffe

• Taste of tibet

Daywise activities

Friday

Things to do:

• We will reach around 3-4 PM

• Rest

• Sunset can be seen in Raja’s seat (happens around 6:15 PM)

• Can find some cafe to eat
  • Coorg cuisine is very near (400m)
    • This can be done for dinner

• Chill at the night

Saturday

Things to do:

• Complete mandalapatti until afternoon (1-2 PM)
  • This will cover abbey falls

• Can visit taste of coorg for lunch / dinner

• Can also check raintree restraurant

AIs

• Check homestays.
  • How to book?

  • Can also book on the spot

  • Cost?
    • 1700 per day for 2 people

• Rental bikes are available
  • Zoom is good

  • Availability is low in weekends

• Air BnB?

• River rafting good in December?

• Find things to do on Friday

• Find things to do on Saturday
  • Can start with Mandalpatti

  • Abbey waterfall

• Confirm places to eat food

Notes for "Clean code" by Robert Cecil Martin

 

1603/B - Moderate Modular Mode

 Moderate Modular Mode

Problem

Link to the problem : https://codeforces.com/problemset/problem/1603/B

Here, we basically are given two numbers $x$ and $y$, and we need to find a number $n$ such that:

$$ n \text{%} x = y \text{%} n$$

$x$ and $y$ are pretty big numbers (~$2 \times 10 ^{18}$)

Solution

Let's divide the conditions. 

1. y < x

Case a) n < y < x

In this case $n \text{%} x = n$ and $y \text{%} n < n$. So these can never be equal and this case will never be true

Case b) y < n < x

In this case $n \text{%} x = n$ and $y \text{%} n = y$, and these will not be equal, so this case will also not be true

Case c) y < x < n

In this case $n \text{%} < x$ and $y \text{%} n = y$. This can be true. Note that a simple solve for this is $n = x + y$

This is what we can use in this case.

2. x = y

In this case we can simply put $n = x$, so both LHS and RHS will be zero.

3. x < y

This case can be divided into two more cases.

Case a) x doesn't divide y

So let's think about a multiple of $x$ that is nearest to $y$, and also less than $y$. That can be found by $\lfloor y / x \rfloor \times x$. Let's assume that value to be $k$.

Let's see the values between $k$ and $y$. The middle of those will not be divisible by $x$ (as the next multiple of $x$ will be more than $y$). Let's call this number $z$ (which is $(y + k)/2$).

Also note that this will not divide $y$ too. The maximum divisor of $y$ is $y/2$. $z$ is clearly more than that.

Now if we see the $ z \text{%} x$ we will find that it will be the delta between $z$ and $k$

Also $y \text{%} y$ will be be the delta between $z$ and $y$. Note that $z$ was in the middle of $k$ and $y$ so both these deltas will be equal. Therefore $z$ will be the answer, which is $ y/2 + \lfloor (y/x) \rfloor \times (x/2) $

Case b) x divides y

In this case $k$ will be equal to $y$. So a simple solution for this is to take the previous multiple of $x$. 

This will be equal to : $ x \times (\lfloor y / x \rfloor -1)$. We do the same calculation as in Case a.

The answer comes out to be $y - (x/2)$ in this case.

My submission : https://codeforces.com/contest/1603/submission/183138750

1514C - Product 1 Modulo N

 1514C - Product 1 Modulo N

Link : https://codeforces.com/problemset/problem/1514/C

Problem statement

We are given a number $n$, for which we want to find the maximum count of numbers which are less than this $n$, and have the modulo of their product as 1.

Solution

Here, the crux of the solution is this math stack exchange's post : https://math.stackexchange.com/questions/441667 

The critical point being:

Let $1 \leq b_1 < b_2 <...< b_{\phi(n)} < n$ be integers relatively prime with n.Prove that 

$$B_n = b_1 b_2 ... b_{\phi(n)} \equiv \pm 1 \bmod n $$

This can be proven by seeing that there are two types of numbers amongst Bs. One, which have a partner number, such that their product is 1 modulo $n$.

Two, which don't have a partner, and their product to themselves (i.e their square) modulo $n$ is $1$. But we don't have two of them. Instead note that $$ (x \times (n - x) ) \text{%} n = (-x^2)\text{%} n = -1$$

So let's see what the product of these two types of numbers will be. The first one will only contribute to 1, but the 2nd ones will contribute -1 for each of them. 

So we just have to multiply the co-primes, and check whether their product modulo $n$ is 1. If not, it will be $n-1$. This means that we can remove the pair of the 2nd type $1, (n-1)$ from the co-primes list. This would decrease the pairs of the 2nd type by 1, and thus our product will become 1 again. 

Note that removing 1 wouldn't make any sense from the co-primes, so we can just remove $n-1$. 

My submission : https://codeforces.com/contest/1514/submission/181683452

Closing of the American mind - Questioning the mixed philosophy which might be contradictory sometimes

 So I have been reading (or hearing, to be precise) "The closing of the American mind" for some months. I hear it often when I am working out, so around 1 hr per day. The audiobook on audible is around 17 hours long, and given my attention span of a small bird, I don't really catch everything Alan Bloom says in the book. 

With the impressive retention of 5%, I imagine something is better than nothing. So I hear along to the meta-philosophy cookbook, where bloom points out the origin of the western liberal thought. I haven't read a lot of philosophy, so I think it wasn't the most wise decision to read the book. Anyhow, as I need to complete my 50 books aim of the year, I don't really care.

This force feeding has actually worked out pretty well. Bloom points out the contradictory nature of the modern man, with ruthless economics on the mind, like a protestant, but also he understands the healing property of nature on man. This contradiction doesn't arise until you're a woodcutter. Otherwise, it keeps at bay. 

We, in our mind, have great capacity to keep contradictory notions in our mind, without actually noticing them. We might need to force ourselves to be crystal clear on what we actually think. 

Also Bloom brought out one more good point. In a democratic society each person is equal. So they don't have anyone above them to tell them what's right or wrong, and therefore they need to make a decision on what is to be done, and how is it to be done. This takes work. What food to eat? What stock to buy? What does the news actually mean? Whom to vote? All these questions, and we need to make choices for them. Not everyone can go and collect information, and think deeply and then make a rational choice. We just don't have enough time for that. Then what do we do in that case? Fallback to the next best choice. What are the others doing? What are the others saying about the current incidents? What are the sectors that will grow in the next 5 years? These decisions are deferred to whatever person we think is good enough to answer these. Unless, obviously, we get bitten back for some, and decide to research and then make an informed decision. 

So the freedom of choice is not exercised, just because we don't have the time to understand what the right choice is for us. 

This is intriguing. 

There was some discussion in the book around science being the prominent source of truth, with are mixed with liberal thought in America, leads them to think that they're non-religious, and thus can go meta, and judge each religion. Each being inferior to the scientific truth obviously. Then (not really sure on this) Bloom points out that, that's what the other religions do. They don't accept other religions. They just tolerate them. So maybe what Americans do isn't meta religion, instead it's a religion in itself. I didn't totally get the point there, as my, again impressive, 5% retention didn't allow me to listen and understand much.