chokudai's blog

By chokudai, history, 6 weeks ago, In English

We will hold ZONe Energy Programming Contest.

The point values will be 100,200,400,300,500,600.

Attention This contest is equivalent to AtCoder Beginner Contest. Please pay attention to the point values bellow. Problem C is 400 points. We are looking forward to your participation!

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

»
6 weeks ago, # |
Rev. 3   Vote: I like it +36 Vote: I do not like it

Hints for problems : A. Check for every 4 length substring of original string. Time complexity is O(N*4).

B. Do a binary search within given accuracy to get such a minimum answer such that (H-ans)/D > max((hi-ans)/di) over all i's. Time complexity is O(N*log2(accuracy)).

C. We can basically binary search on the answer. Inside a binary search, let's check if it's possible for the answer to be more than equal to the middle element of the binary search. For each person find mask of powers which are more than considered middle element of binary search. Now we need to take any 3 masks from given array of masks such that total overlap is (2^5 — 1) or the complete power set mask. Repeating a mask is also a possibility. Time complexity is O(log(A)*(32*4*N))

D. We first need to get the string after 'R''s are removed. We can notice that if number of blocks of strings between 'R's are S1 R S2 R ..... SK R SK+1, 2 possible cases arise : - if K is even, final string is SK' SK-2' .... S2 S1 S3 .... SK-1 SK+1 - if K is odd, final string is SK' SK-2' .... S1 S2 S4 .... SK-1 SK+1 where S' is the reverse of a string S. After obtaining this string, we can build the answer string using a stack based solution where we push a character only if stack is empty or it's top is not equal to my current character to get the minimized answer string. Note that there won't be any possible operation possible after 1 reversal sequence and 1 reduction sequence. Time complexity is O(N).

E. For each cell create a dummy node, and add adge (i,j) -> (i,j,dummy) with weight 1 and also (i,j,dummy) -> (i,j) with weight 0. Also add edges corresponding to "i" in "1+i" transition from (i,j,dummy) -> (i-1,j,dummy) with weight 1. Now between all the normal nodes(cells), add rest of the edges from the first 3 transitions given. Answer will be shortest path between (1,1) to (R,C) in this graph. Time complexity is (O(R*C*log(R*C)).

F. Since we cannot make a transition from a node with value from given value set, let's find the remaining value set, ie, complement value set from {0,1,....n-1}. Now from each node, it is easy to see we can make a transition to other node if and only if their xor is some subset xor of this complemented set. To find how many subset xors are possible, let's build the basis of this set, also keeping the minimal elements added(this will help us build the tree) to the basis. If basis has k elements, then total possible elements in connected component of any node is 2^k including itself. If n is not equal to 2^k, we cannot build an answer. Otherwise we can. Add an edge from each node i to it's xor with each of the original element that was inserted into basis. There are log(n) such elements for each i. Hence graph has nlog(n) edges. Now we can find any spanning tree of this graph and print it. Time Complexity is O(nlog(n)).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    For E, what is the use of the dummy node? Shouldn't just adding normal edges from $$$(i,j)$$$ to all $$$(<i, j)$$$ work, the total number of edges would be of order $$$O(N^3)$$$

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh my bad, I had constraints differently in my mind.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah, that's what I did, and it passed in 200ms (though it TLE'ed on TC26 when I forgot that I can output the answer before calculating every path)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think some heuristic like this is supposed to be done with the solution has intended complexity. Test case 26 was special but could be passed if for the same weight you give the lower node a higher priority, that is the reason why most of the people who used $$$greater<>$$$ in priority queue with $$$O(N^3)$$$ implementation passed whereas those using $$$-dist$$$ TLEd. Apparently $$$O(N^3 * log(N^3))$$$ might be still too much for 2 secs cause the editorial had a quadratic solution.

        On a side note if the quadratic solution was expected then N should have been set higher, whole contest I thought I had a bug in my Dijkstra :(

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you, that was my mistake for case 26 too!

        I also used another optimisation, when iterating on the $$$r \rightarrow r-i$$$ move I stopped iterating $$$i$$$ if $$$ new cost > old cost $$$. That way i even got it down to 80ms (Optimisation on line 124/125). Without this optimisation I got 200ms. The solution with dummy nodes is at 160ms for me.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hmm... that's a smart optimization! Interesting that it's faster than the intended solution even though it has a (technically) worse complexity. Maybe that means the tests were weak?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    For D , I used deque and maintained a bool variable to keep track of reverse operations. https://atcoder.jp/contests/zone2021/submissions/22239816

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh nice solution. Just after reading the problem, I wanted to use treaps for it but went ahead with the original one to avoid any TLE.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      MY solution with Deque
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C, "we need to take any 3 masks from given array"

    How does this work in less than O(n^3)?

    I implemented it otherwise. In the binary search, brute force find a pair of two people with at least 4 of the 5 powers > mid. If found, quick find one person for the last of the 5 powers.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      You can use DP.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you elaborate ?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You are given n bitmasks and you need to check wheter you can pick 3 of them so that thier OR is 31 (this is the part of the problem where we check wheter we can obtain team's total strength >= d in binary search). So it suffices to go from left to right and define dp[i][j][k] is true if and only if you can obtain bitmask J if you considered only prefix of length i and you took exactly k masks. So the answer will be dp[n][31][3].

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
            Rev. 5   Vote: I like it 0 Vote: I do not like it

            Can you explain what will be the transitions ?
            Can you also give the link to your submission

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
              Rev. 3   Vote: I like it -8 Vote: I do not like it

              https://atcoder.jp/contests/zone2021/submissions/22207745

              If you want to use DP without binary search I would do something like that: Go from left to right and decide for current guy whether he is in the team, and if yes what subset of parameters he is contributing to the team. So the complexity would be sth like n * (3 ^ m) where m is the number of parameters (5 in our case) and you will need to remeber similar thing for the dp: prefix of considered guys, how many of them are already taken and which subset of parameters comes from them.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      As I said repetition of masks is allowed. So we only need to consider if at ith level we wanted to build a mask using previous mask m from level i-1 and current array element mask m1. There are 3 levels, for each level we do O(previous mask * N) iterations where number of previous distinct masks are less than equal to 32 or 2^5. PS : infact you can improve the runtime from O(32*N) per level to O(32*min(N,32)) per level.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I had a similar approach but there was no need for binary search? submission

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    E, simple dijkstra with a priority queue also works. Not sure if this is caused by weak tests. submission

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I have also used the same method on upsolving.

      Just want to make sure that will this approach not get TLE? Does it pass because of weak testcases??

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please clarify why this is giving tle for the task D

Code
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are using string concatenation for adding each character to your ans string. On each concatenation a new copy of the string is created which has complexity of O(current length of string), so that the overall complexity is O(n^2)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem B? I think it's geometry problem and anything to do with trapozoids.But could not get any idea though

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Binary Search Solution :

    Let's say we have a minimum height h that you must have to climb.

    The proposition is that if you can do it in h, then you can do it in all h_new >= h.

    So basically we can Binary Search the minimum h that is possible.

    Submission : https://atcoder.jp/contests/zone2021/submissions/22208123.

    Now what you have to do : make an assumption for some h and connect a line from (0, h) to (D, H) and then find if all the N points lie below this or not.

    Either way reduce the search space to 1/2.

    TC : O(log(1/accuracy) * N).

    Alternate Solution :

    Lets say that for some point (d[i], h[i]) we have to make sure that the height h lies above or equal to when this line cuts the y-axis (or at x = 0).

    So the equation of the line can be written as : y - h[i] = ((D - d[i]) / (H - h[i])) (x - d[i]).

    At x = 0, we have y = h[i] - d[i] * (slope).

    Answer is max(0, h[i] - d[i] * (slope) for all 1 <= i <= N.

    TC : O(N)

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Can someone explain to me the 3D DP solution of Problem C , which is mentioned in the editorial .

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    dp[people==3000][levels==3][bits==32].For each candidate we need to decide what mask should I take. If in the final answer if we are considering the particular mask of a person then obviously the lowest valued power of that particular person will come out in the final answer.

    Second thing we have to do is calculate the max value of a particular mask+level along the iteration. We also have to keep in mind if you are replacing some mask value of with another mask , if some information that might be used further is not lost (basically if our transition is not losing any information that can be use further).I would encourage you to simulate whole process with same problem diff constraints , i.e we have to choose 2 person and each have 3 powers only(power > # of people to choose).

    https://atcoder.jp/contests/zone2021/submissions/22254672

»
6 weeks ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

F: Random solution passed the tests, just take vertices randomly vertices and take all edges incident to them and find any possible spanning tree. This way by taking around 40*n edges passed the time limit. Code

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The time complexity of this code is O(40*n*(n-m)) Since 40*n times getting the random variable. and (n-m) valid elements with which we take xor to get the adjacency list. Can you try explaining why it still passes.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      No i am taking 40*n edges only, like start taking random nodes and take all possible edges of this node and whenever total edges cross 40*n stop everything.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    This is so brilliant.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F, "from each node, it is easy to see we can make a transition to other node if and only if their xor is some subset xor of this complemented set."

Actually, I still do not see why this is. Can somebody explain with simple example?

Let $$$B=(1,2)$$$, and $$$v_1\oplus v_2 = 1$$$ and $$$v_3\oplus v_4 = 2$$$

Then how can we see that $$$v_1$$$ is somehow connected to $$$v_3$$$ ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    i and i ^ j are connected if j isn't part of A ie part of B , lets say you want reach some X that be represented as the xor sum of some subset of B xor-ed with i, call the elements of this subset x1,x2,..,xk then simply connect i to i ^ x1,i ^ x1 to i ^ x2 ^ x3 , i ^ x1 ^ x2 ^ x3 to i^ x1 ^ x2 ^ x3 ^ x4 ... so on and so forth

»
6 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

chokudai, tatyam, why not just switch C & D instead of having the point values out of order and adding a note? Just curious.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In fact, in the Japanese version there is a story attached with each problem statement. The stories were more natural to be in the order of 400-300, so they were swapped.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain why the following editorial code for F works ,taking y as min of its xor with elements of elim,I tried randomly permutating elim when considering a new x and it fails the sol surprisingly so order matters

int y = x;
for(int b : elim) chmin(y, y ^ b);
if(y){
      base.push_back(x);
      elim.push_back(y);
 }
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, why it is realated to binary search and why we use it ? I read the editoral but cannot get the idea. Thanks so much.