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. 

Why getting a very good voting system will bring dictator ship

 Why getting a very good voting system will bring dictatorship - Arrow's impossibility theorem

Premise

Imagine that we want to improve how the world works, and as a start, we look at our voting system and decide that it does not represent the real preferences of people. So we decide that our voting system should have two conditions:

1. Pareto Efficiency : If every voter says that the party A is more preferred that the party B, then in that case, the result, after voting should also have A ranked above over B.
2. Independence of irrelevant alternatives: Let's say there are two parties, A and B, and there is an output A > B, in the results. Now let's shuffle the other preferences of voters for every other party than A and B. Then in that case, the relative ranking of A and B shouldn't change in the result, even though there absolute position in the output ranking can change.

So what? Our system already has these two conditions!

So these two perfectly reasonable conditions are the ones that we want to have in our voting system. 

Now let's say our system is a majoritarian system, that is, the one person getting the maximum amount of votes will be the winner. I will try to prove, that in this voting system, there are cases when the second condition, independence of irrelevant alternatives (IIA), will be broken. 

Let's say we have a total of 21 voters, and 3 parties in the election, with the following configuration:

• 10 voters have the preference : $ A > B > C $
• 2 voters have the preference : $ C > B > A $
• 9 voters have the preference : $ B > C > A $

Now in accordance to this voting system, A would win. But let's remove C from this. In that case, this would be the situation :

• 10 voters : $ A > B $
• 2 voters : $ B > A $
• 9 voters : $ B > A $

That is, 11 votes to B, and 10 votes to A, which would mean that B would win.

This means that the presence of C, actually changes the results, and the relative position between A and B. Which means that this system doesn't follow the IIA condition.

Then let's improve things?

Okay. So this means let's go towards a system which actually has these two conditions followed. But there is a mathematical proof which says that if both of these conditions are followed, there will be dictatorship. Wow. Pretty dark theorem.

Less go.

Why can't we improve things?

Let's prove one important theorem, which is a secret tool that will help us later.

Theorem 1: If some preference B is either at the top or bottom of everyone's preference sequence, then it would be either on the top, or at the bottom of the result's sequence.

Let's prove this using contradiction. Let's have $n$ voters with different preferences, each represented by a line. As shown in the  diagram. Now, let's say that in the output, the output $B$, is in the middle. It's neither at the top, nor at the bottom. So this would mean that it has some output $A$ above $B$, and $C$ below $B$. 

Now as you can see in the output $ A > B $, and $ B > C $. Now IIA says that only the relative positions of A, and B determine $A > B$, and the relative positions of B and C, determine $B > C$. So let's just change the positions of A and C in each of our voter's preferences, and put C above A. This would mean that $C > A$. 

This neither changes the relative position of A and B, nor the relative positions of B and C, since A and C are either both above or below B.

Now the condition looks some thing like:

Now using Pareto efficiency (PE)  which was our first condition : Since everyone agrees that $C > A$, therefore, in the results, we should also see that $C >_{Result}  A$.

Now let's go to our original conditions, that is : $A > B$, and $B > C$. Due to transitivity, $A > C$. 

So we have a contradiction, and $B$ can never be in the middle. It can either be at the top, or at the bottom of the result.

[X] (The box that comes in math books, after the "hence proved").

Theorem 2: In the voting system where PE and IIA both are present, there always will be a dictator.

Slow down death. 

Let's say initially we have $B$ at the bottom of every voter's preference. And gradually we move $B$ from the bottom to the top of the preference sequence. Let's say there is some voter $n^*$ who, as soon as moves $B$ from bottom to the top of his preference sequence, the result also puts $B$ back to the top. 

Due to theorem 1, we can say that $B$ will go directly to the top, because $B$'s are either at the top or at the bottom of the preferences of every voter.

The process can be described here:

Now let's prove that this guy, $n^*$ is a dictator for every pair A and C (excluding B). This means that, $n^*$ decides the result directly for every pair of outputs.

Let's put A above B for $n^*$ only, and let all the preferences for all the other voters remain same. For all the other preferences the relationship between A and B's positions is random.

The output should look something like this:

Now, let's compare this to the time, when $n^*$ had decided to put $B$ at the bottom of their preferences. 

In that case, the result had $B$ at the bottom. That is $A > B$. But notice that in this case too, the relative positions between A and B are the same. A is above B, for $n^*$'s preferences too. 

So using IIA we can say that for this case too, $A>B$.

Now let's see the case, when $n^*$ has shifted B to the top of their preferences. In that case, C is below B for $n^*$, and also in the result.

In this case too, C is below B. Moreover, the relative positions of B and C are the same, so we can directly say that $B > C$.

Using this, we can say that $n^*$ is a dictator for all pairs A and C.

Now let's see whether this works for B too. Well obviously! Since B's position at the top, for $n^*$'s preferences determines that the result has B at the top, and vice-versa, we can say that $n^*$ is a dictator for B too.

Using this information, we can say that $n^*$ is a dictator for all pairs.

Improving at competitive coding

 How not to bitch about solving lesser problems

Whenever I ask anyone about how to improve, all they say is "Solve more problems". Bitch. I know that. Do you have anything else to offer? 

So just like other things, this too we have to do on our own. And what does that mean? Analysis!

So I thought of all the phases of solving a problem and made this shitty diagram : 

My main aim to find the most time taking stages. What I understood was, that the main "problem solving" stage, where we think the hardest is the most important one. It might not be the one that takes most of the time itself, but surely is the one that directly affects the total time taken.

Let's just say that I as a person can solve some problem in $T$ minutes, when no re-implementation or code changes are made.

Now let's consider the case that I ran some tests on the code, and it failed for some case. Either we did some silly mistake, so we need to debug it, or our solution is wrong, and we need to rethink the problem.

In this case, again, intense thinking is required, and immense time is wasted. What we can do is make sure that the solution we're implementing is the best version we can give. It's well tested, via dry runs, and should have the least amount of bugs. 

This is a doable thing. It's more of a good habit, than a skill upgradation, as it doesn't require you to improve problem solving, but just stopping a while, testing the solution well in mind, creating some edge cases, and then  implementing it. 

This should save massive amounts of time in competitions. Let's see if this actually improves anything, or is just the intuitive thing people anyways follow. Big eh time.

1335C - Counting Triangles - How to be a bitch of a problem 101

 1355C - Counting Triangles

Problem:

So here is this 1800 rating question acting like it's not that  hard by being a Div2 C. No, fuck you 1355C, we know your truth.

The problem can be found here.

What does it say?

Well you have to make a triangle. You're given four values $A,B,C \text{ and } D$, such that $A \leq B \leq C \leq D$. Now you have two create a triangle, such that the sides of the triangle are of lengths $x,y,z$ such that, $A \leq x \leq B \leq y \leq C \leq z \leq D$. 

Initial thoughts

A triangle can be created when $ x + y \geq z $, $y + z \geq x$ and $x+z \geq y$. Since we have to have only those triangles which have a positive are, thus the equal to sign is removed. Thus $$ x+y > z \\ y + z > x \\ x+z > y $$.

But since $z$ is already greater than $x$ and $y$, you only need to consider $ x+y > z$.

Delving deeper

So, since the differences between A,B,C and D can go upto $5 \times 10^5$, forget brute force. If you have something $O(n^2)$, forget it too. We need something better here.

We have three areas (A to B for x, B to C for y and C to D for z) to cover. So, we might lean into pointers or something, I don't know I'm illiterate.

Since, I know the answer now (which I definitely knew after reading the editorial only), I don't have any other option than to delve straight into the solution.

The Solution

We take two pointers, $xp$ for $x$ and $zp$ for $z$. Now we can calculate minimum $y$, that satisfies our condition by $yp = zp-xp+1$ (remember that we had removed the equals sign).

We can check whether this $yp$ value is sane or not, by checking if it's between B and C only, but more on this later.

Now we know that a triangle can be formed by $xp$, $yp$ and $zp$. Notice that if we increase $yp$, the condition would still hold. That is, $$xp+yp > zp \\ xp+yp+1>zp$$.

Glad to know that. So, that means if we keep $xp$ and $zp$ constant, all eligible y's, from $yp$ all the way to $C$ are eligible triangles.

We can get their number as $C-yp+1$

Noice.

Now, what if we increased $xp$ by one? 

So if $$xp+yp>zp \\ xp+1+(-1)+yp>zp \\ xp + 1 + yp -1 > zp $$

What does it mean? It means that if we increase $xp$, then we can still satisfy the same condition by decreasing the value of $yp$. So, notice that in this case, our eligible triangles would increase by one from the previous case.

To be precise, it would be $C-yp+2$.

Do we see a pattern here? 

Yes. As we increase $xp$, we can decrease $yp$ and increase the number of eligible triangles.

But there should be some limit right. Yes. So you can only decrease $yp$ until $B$. Anything less is not acceptable.

So we increase the value of eligible triangles till then, which would be $C-B+1$, in the end.

But what if we still have some x's left? That is, we traversed by increasing $xp$ and decreasing $yp$. Our value of $yp$ could not be reduced anymore because it had reached it's limit $B$, but $xp$ still had not reached it's upper limit $B$. So since the current value of $xp$ satisfies the condition $xp+yp>z$, we know that if we increase $xp$, then the constraint would still be satisfied.

Notice, that in that case, the total number of eligible triangles would be limited to $C-B+1$ for each such "extra" $xp$.

Now you're getting a hang at it don't you.

Now coming back at the sanity of $yp$ initially. you should know that if intially $yp$ is greater than $C$, then no valid $y$ value satisfies that. So in that case, your $x$ was not good enough to create something greater than $z$, so you increase $xp$.

If in some case $yp$ is less than B, then voila! For all the remaining x's, you can take whole range of $y$. That is $C-B+1$.

I think this should be enough to make the core concept of the problem clear.

Anyhow, if you don't get something or something is wrong here, please leave a comment.

Here is my submission.