When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

AkiLotus's blog

By AkiLotus, 4 years ago, In English

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

1293A - КоннеР и A.R.C. Markland-N

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

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1293B - JOE на телевидении!

Author: AkiLotus
Development: AkiLotus
Editorialist: AkiLotus

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1292A - Игровой лабиринт Неко

Author: xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: AkiLotus

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1292B - Арома и её поиск

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

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1292C - Атака Ксенона

Author: xuanquang1999
Development: xuanquang1999
Editorialist: xuanquang1999

Tutorial
Solution (xuanquang1999, C++)
Solution (xuanquang1999, Java 8)
Solution (pajenegod, PyPy3)

1292D - Хаотичная В.

Author: AkiLotus
Development: AkiLotus
Editorialist: AkiLotus

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, PyPy 3)

1292E - Рин и неизвестный цветок

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

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1292F - Игрушки Норы

Author: xuanquang1999 × MofK
Development: xuanquang1999
Editorialist: xuanquang1999

Tutorial
Solution (xuanquang1999, C++)
Solution (xuanquang1999, Java 8)
Solution (xuanquang1999, PyPy 3)
  • Vote: I like it
  • +202
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

When the codes will be available for tutorials?

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

    After system testing. I want to be sure the solutions worked correctly (even though I tested them quite thoroughly on Polygon).

»
4 years ago, # |
  Vote: I like it +109 Vote: I do not like it

If you play Music Game well, you must have quick hands.

If you have quick hands, maybe you'll publish the fastest editorial!

Thanks for the fast editorial!

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

    You already knew how fast the editorial of #538 was out right? :D

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

Can someone explain C for div2 ?

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I run my code and the result on test 1 is 3 but codeforces gives my result is 34 Can someone help me? Sorry for my bad english

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast tutorials and the music games!

»
4 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

As a rhythm game enthusiast, I was happy to see a round having rhythm game concept. Thanks for the round and fast editorial too!

»
4 years ago, # |
  Vote: I like it +146 Vote: I do not like it

image after the round

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Sidenotes: For problem D1E, the key to solve this problem was to write a lot on scratch paper and try everything that comes to your mind possible, even if it sounds stupid. That's the key for most constructive problems xD

My initial idea was that the limit for all queries is 5/3, Sulfox said that it can be lowered to 3/2, but then in the middle of the night (6 months ago), I came up with a solutions that works for 1.4! But then we had to scrap the initial limit for n, which is [3, 100].

»
4 years ago, # |
Rev. 3   Vote: I like it +45 Vote: I do not like it

There is a simple, elegant solution for Div1E when n is at least 5. Unfortunately, I could not find a way to make it work when n = 4.

First ask CC, CH, and CO. This way, all C's are revealed except for (possibly) a C as the last letter.

Then ask OH and HH. Combined with the information we get from the CH query, this allows us to identify the locations of all H's except for (possibly) a H as the first letter.

We have now found all C's and H's in the interval [2, n-1]. Everything else in the interval is an O. Now we have to find the first and last letters.

At this point, if the first letter is still unknown, it can only be a H or an O; if the last letter is still unknown, it can only be a C or an O. Therefore there are up to 4 possibilities for these 2 letters (first and last). We ask any arbitrary 3 of these possibilities using queries of length n. If we still do not find the answer after these 3 queries, the answer has to be the remaining possibility that we did not ask.

The total energy used is 5/4 + 3/n^2, which is acceptable when n is at least 5.

UPDATE: Solved the n=4 case. The approach I used was to query CH, CC, CO, OH, HHH, OOO, then whenever we find some characters that match (or finish these 6 queries without finding any), we switch to brute force, searching for strings that are consistent with the results of previous queries. The energy usage analysis is too complex for me to provide in full here.

My submission: https://codeforces.com/contest/1292/submission/69161739

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

    $$$N=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 \ge 5$$$ too:

    • ask for CC, if it exists then finish the rest of the string with cost $$$\le 2\sum_{i=3}^{\infty} i^{-2}$$$
    • ask for HCO, HCH, OCH, OCO; if one of them exists then finish the rest of the string with cost $$$\le 2\sum_{i=4}^{\infty} 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)^{-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} \lt 1.36$$$
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone tell me why my solution is giving TLE for problem A https://codeforces.com/contest/1293/submission/69109563

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

For Div. 1 D — Chaotic V., I have a better solution:

Consider find the branch with most occurences once, from node $$$1$$$.

Because we have $$$\max p [p | x!] = \text{the biggest prime number less than or equal to } x$$$ for $$$x \ge 2$$$, so two number $$$a, b$$$ are in the same branch iff their previous primes(including itself) are the same.

That is, $$$a$$$ and $$$b$$$ are in the same prime gap.

So we pre-work $$$\mathrm{last}[x] = \text{previous prime of } x$$$, and find the most occurences prime gap. Let's say, $$$[p_x, p_{x + 1})$$$, then the distinct numbers are reduced to $$$p_{x + 1} - p_x$$$.

Then we only use $$$k_i \in [p_x, p_{x + 1})$$$ to construct the tree structure, which is relatively small.

So we have the complexity of $$$\mathcal O (MAXK \ln \ln MAXK \cdot \text{largest prime gap in } MAXK)$$$.

Then according to A005250 and A002386, we can solve the problem even if $$$MAXK \le {10}^5$$$.

Possible optimization: use virtual trees, maybe can reduce the number of nodes.

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

    But how do you construct the tree structure for the reduced set without factorizing all numbers below $$$k_i$$$ anyway?

    It would certainly be nice to have access to persistent maps/multisets...

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

    My alternative solution using a virtual tree.

    (To avoid confusion, I'll use $$$K$$$ to denote $$$MAXK$$$ in what follows.)

    Note that $$$1!,2!,\dots,k!$$$ is a dfs-order(a.k.a Eulerian order) of the tree. Thus, computing the LCA of $$$k!$$$ and $$$(k+1)!$$$ can be done by finding the number of $$$k!$$$'s prime factors that are not less than $$$(k + 1)$$$'s largest prime factor, where a BIT works. After factorizing $$$1$$$ ~ $$$K$$$ and maintaining the BIT, we can build the virtual tree in $$$O(K)$$$, since the virtual tree has at most $$$2K$$$ nodes.

    Then we just add weights to the nodes according to the input. The weighted centroid of the virtual tree is the proper node $$$P$$$.

    The bottleneck is factorizing $$$1$$$ ~ $$$K$$$. In worst case it takes $$$O(K\sqrt{K})$$$ time, but in practice it runs rather fast.

    A small question
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Very good solution! I think you can offline factorize $$$1 \sim K$$$ in $$$\mathcal O (K \log \log K)$$$?

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

        Oh I see! Using Eratosthenes's Sieve works, I suppose.

        (I must be a fool this morning...

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

    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 $$$\mathcal O (N + K \log \log K)$$$ solution? ($$$\log \log$$$ comes from Eratosthenes's Sieve, and the number of prime factors of $$$k!$$$(factorial of $$$k$$$), check Wikipedia : Prime omega function for more information)

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

Thanks for the useful editorial

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

My solution for E (passed in upsolving):

First of all, once we know that $$$t$$$ is a substring of $$$s$$$ from position $$$pos$$$, we can find the entire string for $$$2\sum_{i=|t|+1}^{n}\frac{1}{i^2}$$$ just by trying to add all letters one by one to the left or to the right and checking if the resulting string occurs in the required position. If $$$|t| = 2$$$ then this value is approximately $$$0.7502654672430585$$$.

Let's ask about CO and CH. If at least one of these strings is present in $$$s$$$ as a substring, then we apply the algorithm above, using only $$$\approx 1.25$$$. Otherwise our string is of type [OH]*C*.

Let's find all occurrences of OH and HO (cost $$$1$$$ so far). If there are none then our string is (O*|H*)C*. We use that $$$n\geq 4$$$ and ask about CCC, if there is none then about OOC and HHC, if there is none then about HHH...H and OOO...O, otherwise we know the string. If there is CCC then we ask about OCCC and HCCC and find the string.

If there are OH or HO then we find the whole string before the last block of non-C letter. Then we just iterate over all possible counts of C in the end and each time ask about the whole string.

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

small doubt: (consider s-x is zero here) if i write my cpp code like

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

then the compiler does not go into the for loop but it if it is like:

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

and x is zero, the compiler goes into the if statement. anybody know why this is happening?

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

    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, # |
  Vote: I like it +5 Vote: I do not like it

Anyone noticed ? Blog was written 6 days ago.

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

    Yes. I have a weird habit of preparing things early, then publishing at the right moment.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Very nice problems! (except too weak pretests in Div2 D)

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

The complete solution set has arrived (except xuanquang1999's Python solution in Div1C, guess he's slept already so I'll contact him later).
Again, thanks for your participation.

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

in Editorail of D how it is known that if u Move from point i to j it will cover all node from i to j?

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

    For three arbitrary points on the same line, namely $$$p_1$$$, $$$p_2$$$, $$$p_3$$$, we can easily see that the Manhattan distance from $$$p_1$$$ to $$$p_3$$$ is the sum of distances from $$$p_1$$$ to $$$p_2$$$ and from $$$p_2$$$ to $$$p_3$$$.

    Applying for a whole segment of points will result in the same outcome, i.e. the total distance to move from point $$$i$$$ to $$$i+1, \ldots, j$$$ will be the same as moving straight from $$$i$$$ to $$$j$$$.

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

can someone explain why long double cannot solve div2B,even cannot pass the sample.it's right on my computer,but wa when i submit.https://codeforces.com/contest/1293/submission/69115420,https://codeforces.com/contest/1293/submission/69113841

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      t is already long double,no need to cast it

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

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          it cannot work,i tried cast t to long double and the whole calculation,both wa,you can submit it

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

For div2 B, Can someone please give a mathematical proof for why not defeating all (n-1) opponents at once would not produce better result?

Mathematically why, (n-1)/n +1 < (1/n + 1/(n-1) + ... + 1)

I tried but failed to prove it.

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it +2 Vote: I do not like it

    For every $$$i \leq n$$$, it is true that $$$1/i \geq 1/n$$$ Then,
    $$$1/2 \geq 1/n$$$
    $$$1/3 \geq 1/n$$$
    $$$...$$$
    $$$1/n \geq 1/n$$$
    If you sum them, you have $$$1/2 + 1/3 + ... + 1/n \geq (n-1)/n$$$.
    Finally, add one on each side $$$(n-1)/n + 1 \leq 1/n + 1/(n - 1) + ... + 1$$$

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

    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, # |
  Vote: I like it +63 Vote: I do not like it

I have a simpler solution for div1 E.

For n>=5, query "CC","OC","HC","HO" and "HH". After that, all 'C' except that in S[1] and all 'H' except that in S[n] will be discovered. So we know S[2..n-1], and S[1] and S[n] both only have two possible values. The total cost is no more than $$$5\cdot\frac14+\frac1{(n-1)^2}+\frac1{n^2}\leq1.3525$$$.

For n=4, at first query "CC","OC","HC" and "HO". If S[1] or S[4] is discovered, then do the remaining part of the above algorithm. The total cost is no more than $$$5\cdot\frac14+\frac1{16}\leq1.3125$$$. Otherwise, if S[2] and S[3] are both discovered, instead of querying "HH", we go to find S[n] and S[1] immediately. The total cost is no more than $$$4\cdot\frac14+\frac19+2\cdot\frac1{16}<1.2362$$$. Otherwise no positions are not discovered and we still query "HH". If we find "HH", S[4] must be discovered, so the total cost is still no more than $$$1.3125$$$. If not, S[2..3]="OO". Then we can determine both S[1] and S[4] by querying "OOO". The total cost is no more than $$$5\cdot\frac14+\frac19<1.3612$$$.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It's always nice to have editorials with multiple coding languages, really helps newbie's.

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can someone help me? my code for div. 2D is failing for test case 44. I am inserting first 55 nodes in an array and using binary search on it, for finding the element with lowest distance. code

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My submission for D is failing system tests because of the upper limit I have set while calculating the co-ordinates of the points. It passed when I set the upper limit as 3e16 but failed when I set it as 1e16+10 or 1e17. Can anyone please help me in finding a possible reason for this? I am unable to figure out how to set an appropriate limit as per the given constraints.

3e16 : https://codeforces.com/contest/1293/submission/69174932

1e17 : https://codeforces.com/contest/1293/submission/69174475

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahh okay. Understood my stupidity. So an upper limit just above 2e16 works. Thanks for your help!

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

    It's probably because $$$10^{17} \cdot 100$$$ would overflow a 64-bit integer.

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Really nice explanations and clean code, thanks for your effort! I've personally really enjoyed this round:D

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone tell me why i am receiving TLE veridict on C problem of Division 2.

My code is : https://codeforces.com/contest/1293/submission/69194019

My algo is also solving the problem in O(n+q).

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

please someone explain approach of Div-2 E in easy language?

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

can someone explain to me div 2 D (i understand how we got all of our ax,ay only)

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

    Here's the solution I thought of first:

    Assume that we start on the $$$z$$$-th data node. It is always optimal to first collect nodes in decreasing order, then if we reach node $$$0$$$ and still have time, to backtrack and collect from node $$$z+1$$$ onward, because it can be proven that $$$2 \cdot dist(node_z, node_0) \leq dist(node_z, node_{z+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 $$$t$$$ reduced accordingly. Total complexity $$$O((\log t)^2)$$$, with the possibility of further reduction to $$$O(\log t \log \log t)$$$ via binary search, but that's overkill.

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your linked submission says accepted, not wrong answer

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

          I am really very sorry mate. I meant this submission: 69438965

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

            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 $$$(x_s, y_s)$$$ 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, # |
  Vote: I like it 0 Vote: I do not like it

Who's Joe?

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

https://youtu.be/mhrvlor1qH0 — video editorial for 1292A - NEKO's Maze Game, including some incorrect solutions and mistakes.

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

Can anyone explain to me AROMA'S SEARCH problem I'm not getting the solution?

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

    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   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

      pls ignore i got it

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

In the A problem, the office is in floor s-th. The number of closed floors is k, k limit is 1000, so if we search from s-1000 to s+1000 the maximum complexity would be 2000000. Here is the for-function recipe:

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;

^^ hopefully oc idea

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

    Isn't it completely identical to the tutorial shown above?

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

[Deleted.]

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

lol, am I only one who solved C Div 2 using map<pair<int,int>,set<pair<int,int>>>?)) https://codeforces.com/contest/1293/submission/69836530

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

I have an O(n) solution for 1293A. 69928477

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

    Your sorting made it $$$\mathcal{O}(k \log k )$$$ unfortunately.

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

have someone solved D with trie?

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a better solution for Div1F and It's time complexity is $$$O(2^{\frac{max a_i}{6}} * n)$$$

72566459

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

I would like to see proof of 1292C - Xenon's Attack on the Gangs that it should be valley sequence.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me where did I get wrong in Div1-C ?
My idea is using greedy to select the best edge available.
Submission: 96498313