nika-skybytska's blog

AtCoder Beginner Contest #188 Livesolve + Editorial
By nika-skybytska, 4 years ago, In English

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\}$$$.

  • Vote: I like it
  • +98
  • Vote: I do not like it

Comments Comments (37)
| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

(...) then it is reasonable to make at most one ±1 operation before each /2 operation

why?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Good question! $$$(x+1+1)/2$$$ is three operations, but you can achieve the same result with $$$x/2 + 1$$$, which is two operations.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Indeed. And thanks for the editorial!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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$$$.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +26 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +13 Vote: I do not like it

              I see, thanks for the explanation!

              → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I mean why something like subtracting 1 from y few times and then dividing by 2 not optimal sometimes ?

        This was answered here.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            I think it works as a general proof. You can formalize it with induction if you want.

            → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The thought process is available in the YouTube video

        → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

thx

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

your F solution is very nice. Also, Solution passed in only 6ms.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay so what can i do to improve it?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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 all operator[] calls, +=, >=, !=, etc.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Please add your YouTube Channel Link somewhere in your Github Bio. It will help a lot.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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));
			
   }
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is handmade_03.txt in problem F? I got one WA on this test and don't understand what the error is.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone had Solved D. Snuke Prime using Coordinate Compression?. Please Share your submission.

→ Reply