998batrr's blog

IZhO 2021
By 998batrr, history, 6 years ago, In English

First: We apologize for any inconvenience caused. On the second day, we'll try to correct all today's mistakes.

We still hope that you enjoyed the contest.

You can upsolve here

Let's discuss the problems.

Upd: Day 1 unofficial results here

Upd: Day 1+2 unofficial results here

Upd: Day 2 now available to upsolving.

Upd: Editorials.

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

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

Can you say how to solve A?

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

    Let's assume that we are at point $$$p$$$ now. We have two options.

    1) Go to $$$t$$$ directly, paying extra $$$|p - t| * a_p$$$ money;

    2) Go to another "optimal" point. There are two choices for that. Either it is minimum $$$r$$$ such that $$$a_r \lt a_p$$$ and $$$r \gt p$$$, or maximum $$$l$$$ such that $$$a_l \lt a_p$$$ and $$$l \lt p$$$.

    So run Dijkstra, maintaining minimum distance. Update answer by the first option. Or go to the next optimal point paying $$$a_v * dist$$$ ($$$r - p$$$ or $$$p - l$$$) money. We are multiplying $$$a_v$$$ because each time we are going to the index with a lower value.

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

      I also did djikstra, but there is no need for it. The graph you get is a DAG, so simple dp is enough.

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

    If I'm not wrong, it can also be solved by the Convex hull trick. The naive solution will be using DP. Let's say $$$dp_i$$$ is the minimum time needed to reach the point $$$i$$$. Recurrent relation will look like $$$dp_i = dp_j + |i - j| \cdot a_j$$$. It is easy to notice that the next point's value will be always less than the current's (i.e $$$a_{cur} \gt a_{next}$$$). So the $$$a's$$$ will be decreasing.

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

      I also solved it with a convex hull trick. I used two convex hulls. One for queries for the left (i < j) decreasing "ladder" from the start, the other for the right (i > j).

      → Reply
»
6 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

Can you say how to solve B?

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 5  
    Vote: I like it +10 Vote: I do not like it

    To solve in n^2logn, we can notice that actually if we reassing our element from L to R, their id to from 1 to R — L + 1, it is easy to notice that actually after each separation their indexes goes left shift. So having M different groups, we can answer the sum with the formula. Then we can notice that 1 to R — L + 1, does not matter and we can just add their initial ID. So with that we can do MO in Nsqrt(N)log(N), but it will also be TL. Then we can notice that it is enough to keep the last Position where such division starts, so just by fixing R we can answer L easily with that information. My realization was with Trie and Fenwich. Nlog^2

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

      I Don't understand what you mean by "such division starts". I had trie and Mo's algo but I still got wa-s(and also TLE :P). Here's what I did, it's probably the same thing. You are splitting the array into multiple subarrays based on prefixes in base 2. For 2 equal values you are trying to get to the point where the prefixes of the indexes differ. Another thing is that if A and B have a common prefix of some length, A — X and B — X will also have a common prefix of the same length. In my VALMAX trie I added indexes from the original array(thanks to the observation it still works) based on the value of respective index. I counted all the nodes that have at least 2 paths going through them, because that means you have to split up to that point(maybe even further down). I also had an unordered map which included all the points in which I have to split. From multiple values would've collided. It still got WA, so it's probably wrong.

      → Reply
»
6 years ago, hide # |
 
Vote: I like it +45 Vote: I do not like it

Can you say how to solve C?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +63 Vote: I do not like it

Can you say how to solve D?

→ Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +52 Vote: I do not like it

Is the second problem reference to this post?

→ Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +69 Vote: I do not like it

Will be official results published today?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

Are all the participants official in the standings?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Lol who was responsible for the 6th subtask of 3rd problem? It genuinely costed me 20 minutes :P

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

How to solve day2 A for n <= 30 and n <= 2000?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +66 Vote: I do not like it

Do you know the cutoff for the medalists?

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

Dies from cringe(

→ Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it -28 Vote: I do not like it

Why its not working in C on n <= 1e3?

Code
→ Reply
»
6 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

Will there be editorial or author's solutions?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +41 Vote: I do not like it

Day 2 upsolve?

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

Isn't there an easier solution for day 2 B (rooms)?

→ Reply
  • »
    »
    20 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You can think of the problem as we start at position x and we want to always go to the left (and exit at door 1) we can create segment for each i where L = i + 1 and R is equal to what rooms is it optimal to visit on the right before visiting room i (supposing room i + 1 is the starting room) then using these segment for each i we can simply binary search to find the rightmost position j j <= i such that we would've already used the values in the range [i, n — 1] (i.e. left the array through the right door) trying to unlock the values [j,i]

    → Reply