Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Akikaze's blog

By Akikaze, 5 weeks ago, In English,

All themes written by Akikaze (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, Akikaze
Editorialist: xuanquang1999, Akikaze

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

1293B - JOE is on TV!

Author: Akikaze
Development: Akikaze
Editorialist: Akikaze

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

1292A - NEKO's Maze Game

Author: xuanquang1999
Development: xuanquang1999, Akikaze
Editorialist: Akikaze

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

1292B - Aroma's Search

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

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

1292C - Xenon's Attack on the Gangs

Author: xuanquang1999
Development: xuanquang1999
Editorialist: xuanquang1999

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

1292D - Chaotic V.

Author: Akikaze
Development: Akikaze
Editorialist: Akikaze

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

1292E - Rin and The Unknown Flower

Author: low_ (Sooke Remix)
Development: low_, Sooke, Akikaze
Editorialist: low_

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

1292F - Nora's Toy Boxes

Author: xuanquang1999 × MofK
Development: xuanquang1999
Editorialist: xuanquang1999

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

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

When the codes will be available for tutorials?

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain C for div2 ?

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast tutorials and the music games!

»
4 weeks 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 weeks ago, # |
  Vote: I like it +146 Vote: I do not like it

image after the round

»
4 weeks 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, Sooke 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 11235813213455'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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the useful editorial

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

Anyone noticed ? Blog was written 6 days ago.

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty nice set of questions!! Looking forward to the next round

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

Any alternative approach to solve Div2 D?

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

can anyone explain logic behind total no of points we need to find out that we can cover before t in Div2D?

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

In problem C, i tried looping for i ~ i+k+100 then checking the begin and end of the array then checking if either the floor (s-i) or the floor(s+i) doesn't exists in the array of close restaurants. but it got WA on test 2, can anyone help me fix the logic? :/

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

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

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

1292A — NEKO's Maze Game CAN ANYONE HELP ME SOLVE THIS QUESTION ,IM STILL A NOOB AT CODING TLE IS KILLING ME HERES MY APPROACH https://codeforces.com/contest/1292/submission/69254469

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

Can anyone please explain me how to implement the idea of question C (NEKO's Maze Game)? I did this https://codeforces.com/contest/1293/submission/69209978 but got TLE. Please help.

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

      thank you but I understood a solution at last

    • »
      »
      »
      4 weeks 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your linked submission says accepted, not wrong answer

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

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

          • »
            »
            »
            »
            »
            »
            4 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Who's Joe?

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

Will somebody help me understand why my code is incorrect? (https://ide.codingblocks.com/s/170178)

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

I did nekos maze game in O(q) check out my solution

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

Sorry If it Sounds silly. How the first observation is made out in Div2E(Div1C)? xuanquang1999

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

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

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

      oh i dont read the tuto clear. But i think this explaination would be a bit easier to understand cuz that number 1000

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

Can someone please tell how I can solve 1292A - Игровой лабиринт Неко by DSU?

»
3 weeks 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

  • »
    »
    3 weeks 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).

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

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