Codeforces Round #614 Editorial

All themes written by AkiLotus (I am the only one in the team playing Cytus II anyway :D).

1293A - ConneR and the A.R.C. Markland-N

Author: xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: xuanquang1999, AkiLotus

1293B - JOE is on TV!

Author: AkiLotus
Development: AkiLotus
Editorialist: AkiLotus

1292A - NEKO's Maze Game

Author: xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: AkiLotus

1292B - Aroma's Search

Author: AkiLotus feat. xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: AkiLotus

1292C - Xenon's Attack on the Gangs

Author: xuanquang1999
Development: xuanquang1999
Editorialist: xuanquang1999

1292D - Chaotic V.

Author: AkiLotus
Development: AkiLotus
Editorialist: AkiLotus

1292E - Rin and The Unknown Flower

Author: low_ (Sulfox Remix)
Development: low_, Sulfox, AkiLotus
Editorialist: low_

1292F - Nora's Toy Boxes

Author: xuanquang1999 × MofK
Development: xuanquang1999
Editorialist: xuanquang1999

• 4 years ago, # ^ | After system testing. I want to be sure the solutions worked correctly (even though I tested them quite thoroughly on Polygon).

• 4 years ago, # ^ | You already knew how fast the editorial of #538 was out right? :D

• 4 years ago, # ^ | ← Rev. 2 →   0 There are two cases in which it will not be possible to reach from 1,1 to 2,n, it will be if a diagonal or a straight vertical line is all lava, so keep track of current lava, and each time you get a new query chech if it creates or removes any diagonals. Maintain a count variable that will keep a track of such diagonals and vertical blockages. Here is my solution https://codeforces.com/contest/1293/submission/69125834

• 4 years ago, # ^ | maybe you define a variable and have not set it to zero and it takes a random value from memory and memory of your system and codeforces are different !

  • 4 years ago, # ^ | Thanks a lots

4 years ago, # | after the round

• 4 years ago, # ^ | *angry cyan sounds*

• 4 years ago, # ^ | ← Rev. 2 →   +16 N=4N=4 can be solved by bruteforcing decision trees, maybe with pruning branches that obviously don't work if it's too slow. I have a solution that works for N≥5N≥5 too: ask for CC, if it exists then finish the rest of the string with cost ≤2∑∞i=3i−2≤2∑i=3∞i−2 ask for HCO, HCH, OCH, OCO; if one of them exists then finish the rest of the string with cost ≤2∑∞i=4i−2≤2∑i=4∞i−2 now there's no C except maybe on the border of the string, ask for HH and OO and if one of them exists, the middle of the string is completely known and only 2 more questions are needed, with cost N−2+(N−1)−2N−2+(N−1)−2 the last case is when there's no CC, HH, OO, so the string has to look like (C|H)OHOH...H(C|O), (C|H)OHOH...HO(C|H) + strings generated from them by swapping H, O; ask for OHOH, HOHO and if neither exists, it has C at both ends; either way, one more question is enough, with total cost 1/4+4/9+2/4+2/16+N−2<1.361/4+4/9+2/4+2/16+N−2<1.36

• 4 years ago, # ^ | if((s-i)>=1) { if(se.find(s+i)==se.end()) { cout<<i<<"\n" ; break; } } Copied from your code. Find out what's wrong here.

  • 4 years ago, # ^ | got it..thnx

• 4 years ago, # ^ | But how do you construct the tree structure for the reduced set without factorizing all numbers below kiki anyway? It would certainly be nice to have access to persistent maps/multisets...

• 4 years ago, # ^ | ← Rev. 2 →   +18 My alternative solution using a virtual tree. (To avoid confusion, I'll use KK to denote MAXKMAXK in what follows.) Note that 1!,2!,…,k!1!,2!,…,k! is a dfs-order(a.k.a Eulerian order) of the tree. Thus, computing the LCA of k!k! and (k+1)!(k+1)! can be done by finding the number of k!k!'s prime factors that are not less than (k+1)(k+1)'s largest prime factor, where a BIT works. After factorizing 11 ~ KK and maintaining the BIT, we can build the virtual tree in O(K)O(K), since the virtual tree has at most 2K2K nodes. Then we just add weights to the nodes according to the input. The weighted centroid of the virtual tree is the proper node PP. The bottleneck is factorizing 11 ~ KK. In worst case it takes O(KK−−√)O(KK) time, but in practice it runs rather fast. A small question

  • 4 years ago, # ^ | Very good solution! I think you can offline factorize 1∼K1∼K in O(KloglogK)O(Klog⁡log⁡K)?

    • 4 years ago, # ^ | Oh I see! Using Eratosthenes's Sieve works, I suppose. (I must be a fool this morning...

• 4 years ago, # ^ | Update : After carefully reading the standard program, I realized my solution is just a tiny optimization of the official solution, but it indeed optimized. Combining 1.618's solution (virtual trees) and my "prime gap" observation, I think we can get an O(N+KloglogK)O(N+Klog⁡log⁡K) solution? (logloglog⁡log comes from Eratosthenes's Sieve, and the number of prime factors of k!k!(factorial of kk), check Wikipedia : Prime omega function for more information)

           if ((1 <= (s - x) && (s - x) <= n)){
                auto it = find (lstk.begin(), lstk.end(), s - x);
                if (it == lstk.end())
                {
                    cout << x << endl;
                    break;
                }
            }

            if ((1 <= (s - x) <= n)){
                auto it = find (lstk.begin(), lstk.end(), s - x);
                if (it == lstk.end())
                {
                    cout << x << endl;
                    break;
                }
            }

• 4 years ago, # ^ | the compiler will calculate 1<=(s-x) first and the result is either 1 or 0 and then calculate1<=n or 0<=n so this condition is always true.

• 4 years ago, # ^ | Yes. I have a weird habit of preparing things early, then publishing at the right moment.

• 4 years ago, # ^ | For three arbitrary points on the same line, namely p1p1, p2p2, p3p3, we can easily see that the Manhattan distance from p1p1 to p3p3 is the sum of distances from p1p1 to p2p2 and from p2p2 to p3p3. Applying for a whole segment of points will result in the same outcome, i.e. the total distance to move from point ii to i+1,…,ji+1,…,j will be the same as moving straight from ii to jj.

• 4 years ago, # ^ | ← Rev. 3 →   0 While adding t / i to s in your code, you should cast to long double first. Should be s += (long double) t / i;

  • 4 years ago, # ^ | t is already long double,no need to cast it

    • 4 years ago, # ^ | ← Rev. 3 →   0 But i isn't Just do it the way I mentioned above and it will work. OK I think I get your confusion, I'm casting the whole calculation and not just t. Link to submission here

      • 4 years ago, # ^ | it cannot work,i tried cast t to long double and the whole calculation,both wa,you can submit it

        • 4 years ago, # ^ | I linked my submission above

• 4 years ago, # ^ | as i don't know how to write summation symbol so i'm giving a piece of code: sum = 0; for(i = 1; i <= n; i++) { sum += 1.0/(n-(n-i)); } hope you got the answer ^_^

  • 4 years ago, # ^ | Thanks for replying, but I guess you didn't get my question.I wanted a mathematical proof for the inequality I have written above, not the code for it.

• 4 years ago, # ^ | For every i≤ni≤n, it is true that 1/i≥1/n1/i≥1/n Then, 1/2≥1/n1/2≥1/n 1/3≥1/n1/3≥1/n ...... 1/n≥1/n1/n≥1/n If you sum them, you have 1/2+1/3+...+1/n≥(n−1)/n1/2+1/3+...+1/n≥(n−1)/n. Finally, add one on each side (n−1)/n+1≤1/n+1/(n−1)+...+1(n−1)/n+1≤1/n+1/(n−1)+...+1

  • 4 years ago, # ^ | Thanks, I got it.

• 4 years ago, # ^ | view it this way to get 1 we need for sure to output 1/1 so if n=4 I could do 4/4 from the first round but if I kept decreasing 4 to 3 then two then one I will find out that the best solution is to always decrease n and I will end up with 1/1 in the end that's of course not a very mathimatical prove but more of a greedy prove but if you think it in reverse you can some how recursivly prove it .

  • 4 years ago, # ^ | Thanks..this is quite intuitive.

• 4 years ago, # ^ | 1e17 fail because 1e17*200 exceeds long long limit 1e16 fail because you can get to points like (1e16,2e16) if t=1e16 and (x,y)=(1e16,1e16)

  • 4 years ago, # ^ | Ahh okay. Understood my stupidity. So an upper limit just above 2e16 works. Thanks for your help!

• 4 years ago, # ^ | ← Rev. 2 →   +3 It's probably because 1017⋅1001017⋅100 would overflow a 64-bit integer.

  • 4 years ago, # ^ | Understood. Thanks!! :D

• 4 years ago, # ^ | Interesting enough, both my solution and yours run faster in Python 3 than in PyPy 3. However, my advice would be ditching out the dict (since a frequency 2D array can be constructed, using dict might be an overkill and waste a few more resources than needed).

• 4 years ago, # ^ | ← Rev. 6 →   0 Here's the solution I thought of first: Assume that we start on the zz-th data node. It is always optimal to first collect nodes in decreasing order, then if we reach node 00 and still have time, to backtrack and collect from node z+1z+1 onward, because it can be proven that 2⋅dist(nodez,node0)≤dist(nodez,nodez+1)2⋅dist(nodez,node0)≤dist(nodez,nodez+1). For the case where we don't start at a data node, we can brute force all reachable data nodes as the first node to collect, then proceed as above with tt reduced accordingly. Total complexity O((logt)2)O((log⁡t)2), with the possibility of further reduction to O(logtloglogt)O(log⁡tlog⁡log⁡t) via binary search, but that's overkill.

  • 4 years ago, # ^ | I also thought the same way as you did at first, but I am getting wrong answer on test 44 from that approach. Can you tell me why?69440793

    • 4 years ago, # ^ | Your linked submission says accepted, not wrong answer

      • 4 years ago, # ^ | I am really very sorry mate. I meant this submission: 69438965

        • 4 years ago, # ^ | Two potential issues: while(x0<xs+t){ x0=ax*x0+bx; y0=ay*y0+by; v.pb({x0,y0}); } If I'm reading this right, you're generating points as long as x0 is less than xs+t, but I see no similar check for the y axis. Is it possible that the y-axis overflowed and produced bogus points? for(i=0;i<sz(v);++i){ ll sex=abs(v[i].f-xs)+abs(v[i].s-ys); if(sex<dist){ dist=sex; ind=i; } } This one seems to pick the closest point to (xs,ys)(xs,ys) as the data node to collect first, however I am uncertain that this is optimal. Due to the small number of reachable nodes, I simply brute force all of them as the first collected node.

• 4 years ago, # ^ | AROMA'S SEARCH approach : Just generate the list of points first from x0 and y0 and these points are very less around <=60. Now just from xs,ys go to certain xi,yi pt in list and keeping going left from i to 0 and for every i keep a j that goes from i+1 to list end ... in such way u will cover all possible answers.. so just maintain a maximum of every answer.. Here is my solution for reference https://codeforces.com/contest/1293/submission/79121522

  • 4 years ago, # ^ | ← Rev. 2 →   0 In DIv1 B / Div2 D can you explain this line Since ax,ay≥2, there are no more than log2(t) important nodes (in other words, k≤log2(t)). ?

    • 4 years ago, # ^ | Assume that there is ceil(log2(t))+1ceil(log2(t))+1 important nodes, the distance between the first and last node will be at least 2ceil(log2(t))2ceil(log2(t)), which is higher than tt in almost every case, and thus, the last node is not an important one any more (proof by contradiction).

  • 4 years ago, # ^ | ← Rev. 2 →   0 pls ignore i got it

for(int i = max(1, s-1000); i <= min(lim, s + min(n-s, 1000)); ++i)
    {
        if(restaurant_at_floor[i] == 1) continue; // map it first
        else minfloor = min(abs(s-i), minfloor); // set minfloor = 1e9
    }

cout << minfloor << endl;

• 4 years ago, # ^ | Isn't it completely identical to the tutorial shown above?

• 4 years ago, # ^ | Errichto himself used set in his tutorial video too. People are more used to arrays tbh, and also they're usually quite keen on execution time (sometimes even a log).

• 4 years ago, # ^ | Your sorting made it O(klogk)O(klog⁡k) unfortunately.