Problems, my solutions, YT link
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\}$$$.
why?
Good question! $$$(x+1+1)/2$$$ is three operations, but you can achieve the same result with $$$x/2 + 1$$$, which is two operations.
Indeed. And thanks for the editorial!
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.
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$$$.
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.
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.
I see, thanks for the explanation!
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 ?
This was answered here.
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.
I think it works as a general proof. You can formalize it with induction if you want.
The thought process is available in the YouTube video
thx
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.
your F solution is very nice. Also, Solution passed in only 6ms.
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 cost
my 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 cases
my submission — https://atcoder.jp/contests/abc188/submissions/19345764
can you suggest any improvement in my logic and way of storing individual day cost?
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.
okay so what can i do to improve it?
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 alloperator[]calls,+=,>=,!=, etc.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
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
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.
Thanks :)
Please add your YouTube Channel Link somewhere in your Github Bio. It will help a lot.
Added it as a website link
For problem $$$E$$$ — It's given that "Here, it is guaranteed that $$$X_i<Y_i$$$ " This statement itself tells that graph will be acyclic right?
Yes.
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
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.
nicely explained!! thanks
The following code, for problem F, is giving me TLE. How can i improve it? Please help.
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
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
What is handmade_03.txt in problem F? I got one WA on this test and don't understand what the error is.
Good question! I don't know about
handmade_03.txtspecifically, 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.Does anyone had Solved D. Snuke Prime using Coordinate Compression?. Please Share your submission.