### nskybytskyi's blog

By nskybytskyi, 3 years ago,

### A. Three-Point Shot

The team behind has min(x, y) points, and the team ahead has max(x, y), so we can check if min(x, y) + 3 > max(x, y).

### B. Orthogonality

Just compute inner product according to the given formula. Use int64_t if you are as paranoid about overflows as I am :)

### C. ABC Tournament

Two finalists are max of their halves, so left = max(a[:middle]) and right = max(a[middle:]). Second place is min of finalists.

### D. Snuke Prime

All these interval processing problems can be solved in the same way, by splitting each interval into two events: start and end. After sorting events we can process them in a sequential fashion, maintaining the current daily cost.

### E. Peddler

DP on DAG, which is already conveniently represented in its topological sort order. Create a dp storing min price at ancestors, and update it along the edges of the graph.

### F. +1-1x2

Solve problem backwards: try to get from $y$ to $x$ with $\pm1$ and $/2$ operations. If we make at least one $/2$ operation, then it is reasonable to make at most one $\pm1$ operation before each $/2$ operation. Therefore, we can write a recursive solution as follows:

• base cases are $x \ge y$, with $x - y$ operations, and no $/2$ operations with $y - x$ operations;

• if $y$ is odd then take min with $2 + \text{solve}((y-1)/2)$ and $2 + \text{solve}((y+1)/2)$;

• if $y$ is even then take min with $1 + \text{solve}(y/2)$;

It works in logarithmic time if you cache answers, because on each layer we have only two consecutive numbers: $\{2k, 2k+1\} \mapsto \{k,k,k+1\} = \{k,k+1\}$, and $\{2k-1,2k\}\mapsto\{k-1,k,k\}=\{k-1,k\}$.

• +98

| Write comment?
 » 3 years ago, # |   +6 (...) then it is reasonable to make at most one ±1 operation before each /2 operation why?
•  » » 3 years ago, # ^ |   +14 Good question! $(x+1+1)/2$ is three operations, but you can achieve the same result with $x/2 + 1$, which is two operations.
•  » » » 3 years ago, # ^ |   +1 Indeed. And thanks for the editorial!
•  » » » 3 years ago, # ^ |   +1 How did you end up going from y to x instead of x to y? I tried going from x to y and got stuck.
•  » » » » 3 years ago, # ^ |   +4 You have to replace operations with their duals. Let's look at the example: if you can get from $1$ to $7$ in $4$ operations $1 \mapsto 1 \times 2 = 2 \mapsto 2 + 1 = 3 \mapsto 3 \times 2 = 6 \mapsto 6 + 1 = 7$ then you can also get from $7$ to $1$ in $4$ dual operations ($\pm1$ and $/2$) as follows: $7 \mapsto 7 - 1 = 6 \mapsto 6 / 2 = 3 \mapsto 3 - 1 = 2 \mapsto 2 / 2 = 1$.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 If we go from x to y, can we also get the right answer? I've seen similar problems with subtract by 1 and multiply by 2 operations allowed only. The solution is also go backward from y to x. Going forward from x to y gives wrong answer.
•  » » » » » » 3 years ago, # ^ |   +26 The cool thing about going from large to small (same with your example problem) is that the operations are more constrained. You can only divide by 2 if the current value is even, and you can only do "subtract 1, divide by 2" if the current value is odd.In contrast, you can add 1 or multiply by 2 anytime, so there is more branching.If you think about it like a rooted tree traversal, it's like how going to the parent repeatedly is much more straightforward and faster than exploring all the children.
•  » » » » » » » 3 years ago, # ^ |   +13 I see, thanks for the explanation!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Nice Editorial UPD : I looked for general proof , but i found it's on lines similar to the example given. Also could you tell your lane of thought while solving this during contest ?
•  » » » » 3 years ago, # ^ |   +3 I mean why something like subtracting 1 from y few times and then dividing by 2 not optimal sometimes ? This was answered here.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Yeah , I know i was looking for general proof .Like subtracting few times , then dividing by 2 and so forth . But i think it can be explained on similar lines , because number of times we need to subtract will decrease if we do all possible division by 2 first and then subtract later on.For example : suppose we need to convert 62 to 15 . Then if we do 62-1-1 , 60/2 , 30/2 then it's total 4 operations . But if we do 62/2 , 31-1,30/2 then it's total 3 operations . Because number of times we need to subtract will go down by around power of 2.
•  » » » » » » 3 years ago, # ^ |   +3 I think it works as a general proof. You can formalize it with induction if you want.
•  » » » » 3 years ago, # ^ |   +3 The thought process is available in the YouTube video
 » 3 years ago, # |   +1 thx
 » 3 years ago, # |   +1 Your logic for F is nice , I got stuck with increment operations and was trying to solve from x to y which confused me much. Thanks for your short and sufficient editorial.
 » 3 years ago, # |   0 your F solution is very nice. Also, Solution passed in only 6ms.
 » 3 years ago, # |   0 hi i need some help in D my approach -> i tried to store each day's individual cost using a hashmap and then check each day cost individually, if it is more than given C than add C else add that costmy code works fine for smaller test cases but gives TLE/error in large test cases it is giving 2213ms (just a little over given time limit) for larger test casesmy submission — https://atcoder.jp/contests/abc188/submissions/19345764can you suggest any improvement in my logic and way of storing individual day cost?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Unfortunately, your solution works much slower than 2s, but the grader stops it soon after TLE to avoid spending too much server time and resources.
•  » » » 3 years ago, # ^ |   0 okay so what can i do to improve it?
•  » » » » 3 years ago, # ^ |   0 Unfortunately, there is nothing you can do to make it AC because the loop for(ll i = minday; i <= maxday; ++i) on line 22 can take up to $10^9$ primitive operations already, which is usually equivalent to 1 second, but then you make at least 20 primitive operations per iteration of the loop, with all operator[] calls, +=, >=, !=, etc.
•  » » » » » 3 years ago, # ^ |   0 I see...thanks for replying. Can you suggest what is the optimal way to calculate each day's individual cost in this question? I tried to read your code for D but to be honest I really couldn't understand much
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Actually, you can use a technique called 'coordinates compression' to make your solution work in $\mathcal{O}(\#\text{events})$, but it is equivalent to processing events in sorted order. Try solving https://leetcode.com/problems/merge-intervals/ to get familiar with my technique
 » 3 years ago, # |   +8 Nice explanation of F. I think my solution was equivalent to yours (I formulated it using Dijkstra, which is a bit messier), but I didn't actually bound the runtime -- I liked your explanation.
•  » » 3 years ago, # ^ |   0 Thanks :)
 » 3 years ago, # |   +8 Please add your YouTube Channel Link somewhere in your Github Bio. It will help a lot.
•  » » 3 years ago, # ^ |   +3 Added it as a website link
•  » » » 3 years ago, # ^ |   0 For problem $E$ — It's given that "Here, it is guaranteed that $X_i •  » » » » 3 years ago, # ^ | 0 Yes.  » 3 years ago, # | 0 Can we prove that at any layer there will be at most 2 distinct numbers? I tried a few examples and it seems to be working •  » » 3 years ago, # ^ | +3 We can prove by inductive argument.If$y$is even , then first layer will have only one number$y/2$. If$y$is odd , then first layer will be$(y-1)/2,(y+1)/2$and difference between them is$1$. Hence they will be also consecutive .Now suppose any layer contains only single number say$y_1$, then by previous argument layer next to it will contain at most 2 consecutive numbers.If layer contains two numbers say$y_1$,$y_2$and both are consecutive and let's say$y_1$is odd , then next layer will have$(y_1-1)/2$,$(y_1+1)/2$(it's equal to$y_2/2$) and thus only two consecutive numbers. •  » » » 3 years ago, # ^ | 0 nicely explained!! thanks  » 3 years ago, # | 0 The following code, for problem F, is giving me TLE. How can i improve it? Please help. public static long findAnswer(long x, long y) { if(x >= y)return x - y; if(y % 2 == 0) return Math.min(1 + findAnswer(x,y/2), y - x); else return 1 + Math.min(findAnswer(x, y + 1), findAnswer(x, y - 1)); }  •  » » 3 years ago, # ^ | +1 its like fibonacci without memoisation, you are calculating for a state (lets say 10) multiple times, (20 -> 10 or 19 -> 20 -> 10), consider memoisation instead which stores the result of some visited state, and there will be O(log(1e18)) such numbers •  » » 3 years ago, # ^ | +1 Create a map for y and its value used as a storage in memorisation .Just put in map when u calculate it and use it if need in fututre  » 3 years ago, # | +8 What is handmade_03.txt in problem F? I got one WA on this test and don't understand what the error is. •  » » 3 years ago, # ^ | 0 Good question! I don't know about handmade_03.txt specifically, but I tested your latest submission against mine, and your fails on$x = 1$,$y = 39$with$8$operations compared to my$7$. I think that problem with your logic is that you either always add$1$to odd numbers or always subtract, and I see no reason for this to be optimal. In the example above your operations are$39 \mapsto 38 \mapsto 19 \mapsto 18 \mapsto 9 \mapsto 8 \mapsto 4 \mapsto 2 \mapsto 1$and optimal solution is$39 \mapsto 40 \mapsto 20 \mapsto 10 \mapsto 5 \mapsto 4 \mapsto 2 \mapsto 1$, where both$+1$and$-1\$ for odd numbers are used.
 » 3 years ago, # |   0 Does anyone had Solved D. Snuke Prime using Coordinate Compression?. Please Share your submission.