Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ch_egor's blog

By ch_egor, 6 months ago, In English

Thanks for the participation!

1501A - Alexey and Train was authored by Aleks5d and prepared by 4qqqq

1501B - Napoleon Cake was authored and prepared by KAN

1500A - Going Home was authored and prepared by wrg0ababd

1500B - Two chandeliers was authored by jury and prepared by Siberian

1500C - Matrix Sorting was authored by Endagorion and prepared by NiceClock

1500D - Tiles for Bathroom was authored by meshanya and prepared by KiKoS

1500E - Subset Trick was authored and prepared by isaf27

1500F - Cupboards Jumps was authored and prepared by Akulyat

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • -273
  • Vote: I do not like it

»
6 months ago, # |
Rev. 3   Vote: I like it -22 Vote: I do not like it

Thanks for the round and the fast editorials!

UPD: It seems that many participants hate this round because of unclear statements, weak pretests or main tests, too hard time limits and so on. But I think these problems are interesting and challenging, aren't they?

»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Thanks! :)

»
6 months ago, # |
  Vote: I like it +69 Vote: I do not like it

1A can be solved using FFT. 109885329

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

    can anyone explain that how does n^2 sol pass in div 2-C. as,(4≤n≤200000) thanks in advance :-)

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

      time limit is 2 secs

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it -30 Vote: I do not like it

      since, 10^8 operations can be done atmost in 1sec. so, in 2sec we can do 2 * 10^8 operation so n^2 is probably not gonna work how then n^2 is working. Also I had submitted the n^2logn approach and it got accepted but How?

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

        So, there is 10^16/10^8 = 10^8 "1sec" in one "2sec".

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

          sorry, I dint get you.

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

            Okay, if we are talking about seconds, 2 seconds = 2 * 1 second, 1 second two times. So if we can do n operations in 1 second, it is 2 * n in two second, not n^2. 10^8 * 2 != 10^16, it is much smaller. 10^16 = 10^8 * 10^8 = 10^8 * (2 + 99999998) = 10^8 * 2 + 10^8 * 99999998.

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

              Exactly, I was wrong with my calculations. It will be 2 * 10^8 operations atmost.

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

        Wow

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

          try using those new variables (ds, sum) in some calculations and you will get the TLE you're looking for. I think that the compiler saw that you didn't use them so it didn't bother to run those loops. I didn't some experiments before on those types of loops and if the optimizations flags are set on, the compiler will ignore any loop if it's obvious that the rest of the code is not using anything related to those loops. i hope you understand what I mean, and I you you're looking for more information about this topic, you can try googling about optimization flags.

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

      There are a total of n*(n-1)/2 pairs of two numbers possible. So there can be maximum n*(n-1)/2 different sums possible. And from the constraint a[i]<=2.5*10^6, then answer always exists. So, when n>4000, then there always exists an answer, hence not giving TLE.

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

Why are solutions of other people not visible.

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

What does "C" denote to in going home editorial ?

»
6 months ago, # |
  Vote: I like it +159 Vote: I do not like it

Two logarithms in B and logarithm in C and these TLs? Are you crazy? ;_;

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

    Isn't there a linear algorithm for B, My code[submission:109895054]passed tests but I don't know if its correct considering many smart people didn't get this algorithm

»
6 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Div 2 C was hard :(

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

min(n^2,n+C)......I think too much.

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

    How is O(n2) solution working when 4 <= N <= 200000 ?

    I know the time complexity given above is O(min(n2, n+C)). Where is this (n+C) coming from ?

    When the answer is "NO" we are iterating over all the possible pairs O(n*(n-1)/2). So when the value of N = 200000, shouldn't it give TLE ?

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

      The answer will not be "NO" when $$$n$$$ is big enough.

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

      You can think of the pigeonhole principle.

      Remember that there are always four distinct indices $$$x, y, z, w$$$ such that $$$a_x + a_y = a_z + a_w$$$ ($$$ = S$$$) when there are at least four distinct pairs of indices $$$(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$$$ (indices may be repeated across them) such that $$$a_{x_1} + a_{y_1} = a_{x_2} + a_{y_2} = a_{x_3} + a_{y_3} = a_{x_4} + a_{y_4} = S$$$.

      Let's imagine we are running our $$$\mathcal{O}(n^2)$$$ bruteforce and trying every pair; for every pair $$$(i, j)$$$ we compute its sum $$$a_i + a_j = S$$$ and increment the count on how many times we have seen the sum $$$S$$$.

      Given that the maximum sum of any pair is $$$2*C$$$, the "longest" it would take the bruteforce to see one sum $$$S$$$ occurring four times is around ~$$$3 * (2 * C) = \mathcal{O}(C)$$$. Therefore, if a solution exists, it will be found in time $$$\mathcal{O}(C)$$$. If there's no solution (we tried all pairs), it was the case that (roughly) $$$n^2 \le 3 * (2 * C)$$$ (or something close to this).

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

        Sir,can you kindly say what is this C?

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

          $$$C = 2.5⋅10^6$$$ is the maximum value an element can take.

»
6 months ago, # |
  Vote: I like it +88 Vote: I do not like it

Can I see the model solution to B, with complexity O((n+m)⋅log(n+m)⋅log(k⋅(n+m)), that passes the constraints? How was the TL set? Thanks

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

    +1

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

    I'm curious about the running time of the author's code and if he had done strict optimization on constant.

    Or maybe the author thought 1 second equals to 1e9 complexity on codeforces?

    I'm considering adding "#pragma GCC optimize("Ofast")" into my default header, though my code used 1544ms this time without this ;_;

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

      I can't imagine that complexity passing even with some constant optimizations. Even if it passed, it would be bad to set TL based on a heavily constant optimized solution with terrible complexity. At least you passed, I couldn't fit my O((n + m)log(i64)) into TL, but that might be just because I'm weak :D. (also I don't have any lib so I copied from cp-algo and apparently it's slow xd)

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

        Actually I too can't imagine this complexity can pass the test in this TL. And I think the TL of this problem is undoubtedly inappropriate, and it seems like a naive mistake.

        Yet I'm simply curious about what had happened when this limit was being set. As far as I know, some authors would just set the TL by the running time of his/her code times 2 or even 1.5 without thinking twice.

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

        BTW, My complexity is also O(n+m)log(1e18), no two logarithm but still not too far from the TL.

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

    My solution passes, but I have log(n)^2.109863770

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

    There is a linear algorithm right?Why not explain that in editorial?(My linear algorithm submission:109895054)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is my linear time solution 123079734

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Div.1C has some similarities with Bucket Sort.

»
6 months ago, # |
Rev. 5   Vote: I like it +15 Vote: I do not like it

I decompose 2C into several cases:

1) We have 4 copies of a value X (e.g. 1 1 1 1 2 3) => YES

2) We have 2 or 3 copies of a value X; and we have several such X (at least 2), (e.g 1 1 2 2 2 5 10) => YES

3) We have 2 or 3 copies of a value X; and there is exactly one X like that (e.g. 1 2 2 2 100 7 9) => two pointers for checking whether we have u and v such that u < X < v and u+v = 2*X => YES/NO.

If YES, it is ok. Otherwise, we remove duplicated elements and continue with case 4.

4) We have only distinct values (e.g. 1 2 5 9 11 13 ...)

If N*(N-1)/2 > 5*10^6: we will have two different pairs (x,y)and(z,t) that meets the condition; because of the Dirictle lemma. Just check bruto-force the first sqrt(10^7) elements.

Otherwise, perform O(n^2) algorithm to check.

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

    Can you elaborate on Dirictle lemma?

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

      It is something like : if you put N items into M boxes with N>M; you will have a box with at least 2 items.

      So, given that we have an array of size N with distint non-negative values and we have n*(n-1)/2 pairs (u+v), and if n*(n-1)/2 > 5,000,000; we should have a YES answer.

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

        Is it same as pigeon hole principle?

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

          Yes, it is the same. I just do not remember the name you mentioned.

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

        Great explanation! it helped me to completely understand why brute force sol. works.

        Thanks.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This doesn't work in below case

        n=5 and 1<=a<=4. so by your definition 5*(5-1)/2>8 i.e. 10>8 so the answer must be YES but it will fail when array is [1,1,1,3,4]

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

    Why do we have to check only sqrt(10^7) no.s , Here we are on addition so shouldn't we check till 2.5*10^6 , for each loop

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

      it is since using the first sqrt(10^7) elements of A, you create more than 5*10^6 values of form A[i]+A[j] with i<j.

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

    thanks, great exp.

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

Can you unhide the main tests? I can't wait to find why I FSTed:(

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

Div1 B can be solved in O(n log k). Crt and Gcd is not necessary .

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    code:

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

      Any tutorial?

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

        Find the loop section and binary search

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

          I don't understand. Do you mean precalculate length lcm(n,m) and find answer to k using binary search? I am a little dumb here becuz the loop section's collision might need O(nm) to find if n and m are coprime.

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

            You can see the "while(!vis[now])" part in my code , it found all the loop section.

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

    I might be wrong but I believe if one uses CRT, but not BS on the answer, it is O(NlogN). We compute the values mod mmc(N,M) that have the same color.

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

    It could be solved in O(N + M) to. Binary search is not necessary, one could just "simulate". In case someone is interested: code

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

      your submission hype link is broken and no one found lol

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

    If my math is correct, it can be solved in O(N) (or smth like O(N+M+log(N+M)), but linear in general)

    126387236

»
6 months ago, # |
  Vote: I like it -53 Vote: I do not like it

This editorials is so fast that I'm be so surprised of it!

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I have a randomised solution for div2C/div1A and I'm not sure if I cheesed system tests or if it's supposed to pass. Can someone take a look at it and hack if possible? Otherwise, if it's supposed to pass, can someone tell me the probability of failure?

Submission: 109876872

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I got a FST in Div1B.

But when I submit the code again after contest , it accepted (but 1981ms).

And when I submit the same code again with C++17(64) , it accepted and only ran 1653ms.

What a pity...

My submisson during contest:109857178

Submisson after contest:109891513

With C++17(64):109891826

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

I found the GFG page, but looking at it I thought it wouldn't pass. After the contest and reading some comments here, I thought it just might.

I tried, and it got AC. Smile in pain. Hehe.

GeeksForGeeks article

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

Please can someone explain me this : During the contest I submitted ABC and there it said pretest passed and now it is showing -1 in A and C, saying WA in tc 6(for A) and TLE in C problem. How does this happen?Should not they show this during the contest, that i have done 2 questions wrong ?? Please if someone could help me understand what happened ? I am really frustrated rn

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

    Since it would take too much time to run over all the testcases during the contest, Codeforces divides the testcases to be "pretests" and "system tests".

    Passing the pretests doesn't mean that you solved the problem (though it should...).

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

      I am so angry by this, i went from 1000 rank to 6000.

»
6 months ago, # |
  Vote: I like it +208 Vote: I do not like it

Good contest with strong pretests, especially in problem B and problem C.

What's more, the tl of problem B and the ml of problem D are very friendly. No one can get TLE or MLE on them.

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

    I think that you should say clearly that it's a sarcasm, it might be hard to get it.

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it +53 Vote: I do not like it

    Can't speak for D, but, unless my solution is very wrong and tests are extremely weak, binary search in div1B isn't needed at all. In fact, I solved it in $$$O((n + m)\log(n + m))$$$, where the $$$\log$$$ comes from a single sorting of a vector with up to $$$\min(n, \, m)$$$ elements.

    Sketch of solution. Iterate over the colors and make a vector $$$s$$$ of all solutions to the system that you find (if for some color there are no solutions, ignore it). Then sort the vector. Now set $$$ans$$$ to $$$\displaystyle \text{lcm}(n, \, m) \cdot \left\lfloor \frac{k}{\text{lcm}(n, \, m) - \text{size}(s)} \right\rfloor$$$ and reduce $$$k \mod (\text{lcm}(n, \, m) - \text{size}(s))$$$. Finally, iterate over the elements of $$$s$$$ and stop at the first index $$$i$$$ such that $$$s[i] - i \ge k$$$. Then it is easy to update $$$ans$$$ to the correct value.

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

How to solve Div1B/Div2D ?

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anybody please explain why this solution for div2 A is giving wrong answer https://codeforces.com/contest/1501/submission/109849523

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

109860426

Who wants to hack my randomized div1A?

For n <= 150, I use a quartic brute force.

For n > 150, I use MITM, where I partition the array into two halves, and randomly select 10^6 pairs from each half, and check for any common sums.

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

ML in D was brutal. If only $$$q \le 9$$$ instead of $$$10$$$ or number of colors was up to $$$2\cdot 10^6$$$ instead of $$$2.25 \cdot 10^6$$$ it would really be easier xd

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

Div-2 C solution in gfg:

some modifications will do

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Shitty Round especially statement of problem DIV2A.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

109889803
For 1500C - Matrix Sorting , the $$$O(nm^2)$$$ approach could be optimized to $$$O(\frac{nm^2}{w})$$$ using bitset, which could pass the tests.

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

    Yes, that's what I did in the contest. I really think it's a good problem, but the limit seems quite tight. I douted whether it would pass before submitting (it passed though).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$O(nm^2)$$$ can be pass the tests too. So Incredible! 112190603

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

I had figured out a $$$O(nm^{2})$$$ solution for 1C, but now I don't even understand how the editorial reaches $$$O(nm^{2})$$$, let alone understanding optimising it to $$$O(nm)$$$. The editorial is hard to understand.

I think the optimising part made it too difficult a problem for its position as 1C ?!

In particular, can someone please explain this part:

If two rows are in the same class, then the columns that we applied had the same values. Then, we need to find a column that does not break the sequence between the rows inside each of the classes. Let's iterate through such a column every time.

What values are we talking about?

»
6 months ago, # |
  Vote: I like it +37 Vote: I do not like it

An alternative approach for Div1A.

Let us prove that if $$$n > \sqrt{8\max a} + 2$$$ then we can always find such a quadruple. Indeed, sort $$$a$$$ in ascending order and consider the differences $$$a_2 - a_1, \, a_4 - a_3, \, \dots, \, a_{2k} - a_{2k - 1}, \, \dots$$$ These are $$$\left\lfloor \frac{n}{2} \right\rfloor$$$, so there are two of them which are equal. If that weren't the case, we would have

$$$\displaystyle a_n \ge \sum_{k = 1}^{\left\lfloor \frac{n}{2} \right\rfloor} (a_{2k} - a_{2k - 1}) \ge 0 + 1 + \cdots + \left(\left\lfloor \frac{n}{2} \right\rfloor - 1\right) = \frac{\left\lfloor \frac{n}{2} \right\rfloor\left( \left\lfloor \frac{n}{2} \right\rfloor - 1 \right)}{2} > \max a.$$$

Let $$$i, \, j$$$ be such that $$$a_{2i} - a_{2i - 1} = a_{2j} - a_{2j - 1}$$$. Then $$$x = 2i$$$, $$$y = 2j - 1$$$, $$$z = 2j$$$, $$$w = 2i - 1$$$ is a solution.

Now we proceed as follows. We sort $$$a$$$, iterate over the even values of $$$k$$$ and check if two differences $$$a_{2k} - a_{2k - 1}$$$ are equal. If this is the case, we are done. Otherwise, $$$n < \sqrt{8\max a} + 2$$$ and we can bruteforce the answer in $$$O(n^2)$$$.

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

    sorry but I can't figure out how $$$n > \sqrt{8\max a} + 2$$$ is calculated, could you please give an explaination?

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

      You gotta solve the equation $$$\frac{\left\lfloor \frac{n}{2} \right\rfloor\left( \left\lfloor \frac{n}{2} \right\rfloor - 1 \right)}{2} > \max a.$$$ to get this. The inference makes sense, however, I don't quite understand how you bruteforce the answer in $O(n^2)$。

      UPD: I now understand, use the method as editorial. But then you don't need to do those survey beforehand :<

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

        Exactly as in the editorial solution. Actually, I realize now that the first part isn't needed at all. Because of the proof in the editorial, the second part alone (bruteforce) is sufficient to solve the problem with the given constraints.

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

        Thx for the explaination and I also wonder how to bruteforce in $$$O(n^2)$$$

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

1500A going home. I notice that ai<=2.5*10^6 but didn't investigate into that.. Indeed, $$$1<=ai+aj<=5*10^6$$$ for arbitrary i,j. And if we have n distinct elements, we will have $$$\frac{n*(n-1)}{2}$$$ pairs of different pair of (i,j). If $$$\frac{n*(n-1)}{2}>5*10^6 => n>=3162$$$ you are guaranteed to find an answer. Well, doesn't help to solve this problem.

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

I feel like this approach for div1A/div2C is right but it FSTd. Can someone tell me why?

So first i rewrite the eqn as ax-az = aw-ay. Now I just need to find 2 pairs of indices such that their differences are the same.

For this, I store all elements in a frequency array and iterate over all differences.

for(int i=0;i<N;i++)
    for(int j=0;j+i<N;j+=i)
        //check if j and j+i are present in the freq array
        //Find 2 such pairs and that would be our answer

My submission

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

    Did you make sure to not repeat some index? Maybe that is the case

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

      Yes, if i take the pair {j, j+i} at one iteration, and if freq[j+i]==1, I make sure to not take it again, or else i consider the possibility that it can be taken again

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

    4 2 7 11 16

    o/p : YES 1 4 2 3

    your code's o/p : NO

»
6 months ago, # |
  Vote: I like it -27 Vote: I do not like it

PROBLEM( B + A ) LINK : https://www.youtube.com/watch?v=MUnsGm0K8Qw

HAPPY CODING

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

div-2D/1B can be solved in linear time. We just need to calculate for each starting position in 1st array, how many matches will be with 2nd array in next m indexes. Here's my AC: 109899040

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

    Yup I used a similar approach. Code

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

      Yes, it is too similar lol.

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

        Can anyone of you explain your submissions as it seems that some mathematical principles are hidden in some beautiful lines written out there. Thanks.

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

          First I made the 1st array greater than 2nd by swapping.

          I have made an array named 'c' of size n, such that c[i] represents the no. of dismatches (a[i]!=b[j]) in the next m days if we start from a[i].

          Mathematically, c[i] = no. of j's such that a[(i+j)%n]!=b[j] and j=0 to m-1

          Initially all c[i]=m (we assumes all dismatches). Now we can iterate the 'b' array.

          If b[i] is not present in array 'a', then b[i] won't cause any match irrespective of starting index (won't effect any c[j]). We will simply continue.

          otherwise if b[i]==a[j] (you can use an additional array/map to find that), we should decrease c[(i-j)%n] by one because we will find a match when we start from (i-j)%n after j indexes.

          Thus we obtain c array. Let x=0. Now we can just push_back c[x] in a vector and change x to (x+m)%n until it again reaches x=0 ( cycle formed)

          after that it's just trivial.

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

Can anyone explain why brute force worked in C (going home) even though the constraints are 4≤n≤200000? 2*10^5 should require an O(n) or O(nlog(n)) solution so how O(n^2) worked?

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

    Because since 2.5*10^5 is the upper bound on every element the maximum sum of 2 elements can be 5*10^5. Now if you just iterate to get all possible sums they will all be below 5*10^5 and in 1 iteration you get 1 new sum, otherwise you break. So you will never TLE.

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

      *upper bound on every element is 2.5*10^6

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

        Alright, but it's still more than enough. The solution is actually O(n).

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

          now i am more confused....

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

            Read about pigeonhole principle you will get the idea.

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

            Ok imagine you have a million elements but upper bound is say 10, do you need to do O(n^2) over a million elements to confirm that you will get a repeating sum? No, as maximum possible sum of 2 elements is only 20 you will only have at maximum 20 different values of sum possible, this is the whole basis of this problem. As another user suggested this is known as pigeonhole principle.

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

What is the variable "y" in 1B's tutorial?

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for fast and clear editiorials!

I quickly(I hope so) solve two problems, when I come to think about C, I had a challange. But finally I solve it. And the great thing is I have a rank of 239! I'm really excited about that:-)

The problems are really great and I enjoyed it a lot, thanks!

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

In Div2 C ( Div1 A ) why the brute force using map and checking sum of 2 pair of indices passes the time limit. Its time complexity is O(n^2) still it passes. Code: https://codeforces.com/contest/1501/submission/109901974

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

    I Misread...

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

      Actually i was trying to show that even using map, brute force O(n^2) is getting passed .. my question was- why is this getting passed through the time limit ?

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

        Because maximum element is 2.5*10^6 so maximum sum of 2 elements is 5*10^6. So you can get at max 5*10^6 different values of sums before encountering a repetition. So once you find a sum again for different indices you can just break the iteration. That's why time complexity is given as min(O(n^2), O(n+C)).

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

    What the heck, my code gets TLE 109955669 and it is similar to your code. I don't know why and I try to submit your code, it gets TLE too 109956382.. What happens?

    I passed by replacing map with vector mapping. But still not knowing how you pass the time limit..

»
6 months ago, # |
  Vote: I like it +53 Vote: I do not like it

My code for div1B got TLE result. submission

After using fread,it accepted. submission

The complexity of the code is $$$O((n+m)log(nm))$$$

So , why is the time limit so hard ?

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

again my A FST. is it weak pretest or my blunder? A Submission

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

Can anyone explain the editorial solution of Div1B/Div2D , why solving those two equation gives us the answer ? ( also it seems there is a typo in the second equation it should be pos≡x(modm) instead of pos≡y(modm) . )

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

For DIV2_C, I intuitively felt that if the answer is "NO", then the number of elements in the array should be pretty small. Let's try to make such an array. Let's say the array contains 1, 2, 3, here the difference between any two elements is given by Diff = {1, 2}. Now the next number sould be such that its difference with any of the existing elements should not be present in Diff (except for the case when one element is common). Therefore, the next number can't be 4 (since 4-3 = 1 and 1 is already present in Diff). Therefore, the next number in the array increases rapidly (you can try to add more elements), and for the answer to be "NO", the array can contain around 3000 elements under the given constraints. And probably this is why O(n^2) works. Can someone please verify this for me ?

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

PROBLEM( B + A ) LINK : https://www.youtube.com/watch?v=MUnsGm0K8Qw

HAPPY CODING

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

will someone tell me what is wrong with this code https://codeforces.com/contest/1501/submission/109882653 ? it is showing runtime error on test 8.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why aren't results for div 2 out yet?? I see div 1 results are already out.

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

[TWO CHANDELIERS] Can someone explain me over what variable you can do binary search? I don't get the solution at all :(

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

nc cnts

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

This could just be my own perception, but since restrictions on contest writers were tightened, I have found the contests much more difficult. Today I couldn't solve a single question in Div 1. I think that's the first time that's ever happened, but in general the recent contests have been tough.

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

    :< Dude you are really hardworking. This used to be a complaint but it is now a comfort from me after checking your profile.

    Keep up and do some problems that you never hear of. Wish you luck.

»
6 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Very beautiful, careful and short solution by olympiad participant cat998__. May help to understand the solution.

https://pastebin.com/uhhe3c4v

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

    What exactly does vector<int> cut keep track of? Seems like it stores some kind of property for the rows?

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

      In the final state of B, the equivalence classes are sub-arrays, so we store did we cut our classes or not.

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

Sadly ch_egor have not authored any problem but suffered downwotes for managing the contest and problemset. It is not fair.

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

    The problems were pretty good too. They didn't require any hard observations/math stuff. I don't know why people disliked them

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

In Div2 C, I used an intuitive approach to solve that worked. Basically, I iterated over differences (ax — az) from 0 to k*C/N, where C = 2.5*10^6, N is the input size, and k is some constant (say 2) and then I checked whether four such indices exist or not. My question is how to prove that only checking first k*C/N differences works? Also, what is the tight lower bound for such k?

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

How are we expected to know that the actual value of n used in the main tests is much smaller than the given constraint in div2-C question? An O(n^2) solution should not be accepted according to the given constraints but many people got away with it due to weak test cases. This should be rectified somehow

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

    Did you read the editorial? Time complexity is min(O(n^2,n+C)).

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

I have trouble understanding problem div1 A / div2 C

Why is the condition in the editorial sufficient? If we have 4 pairs such that their sum is equal then there is a solution. However, that doesn't imply that there will always be 4 such pairs if there is a solution to the problem.

In other words, what is the proof that there exists a solution to the problem if and only if there are these 4 pairs that are described in the editorial?

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

what the fuck was div2a problem statement supposed to mean? These contest wasn't it.

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

Is the round unrated now??

I can't see any rating changes in anyone's profile including mine :+ Thank you in advance

»
6 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Here is the normal solution of d1a instead of the authors' unobvious solution:

If $$$n<10000$$$ run the $$$n^2$$$ solution, else sort the numbers and find the pair of pairs of adjacent numbers with the same difference, also the indices should be different. It always exists because $$$10000^2 > 2.5 \cdot 10^6$$$.

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

I submitted the code when the overall evaluation failed in the competition and passed it directly after the competition. The machine was too slow during the overall evaluation, which led to unfair treatment. Please restore it to me!!!!!

during

http://codeforces.com/contest/1500/submission/109859256

after

http://codeforces.com/contest/1500/submission/109932270 http://codeforces.com/contest/1500/submission/109931959 http://codeforces.com/contest/1500/submission/109931910

Quite the same

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

Can anybody give me some problems like problem C (div 2)?

The problem that you implement O (N ^ 2), but in total you just do it in O(N).

<3 <3 <3

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

How to construct a sequence of number for n = 1570 whose answer is "NO" for div1A/div2C ? I found that 4-th example is that situation, however, I can't construct it. Can someone give me an idea ?

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

DIV2 C question was hard to think how it works in N^2 approach even N was in that range which generally doesn't fit in N^2 approach .. many of those (not all of them) get accepted to that question without knowing proper reason.. LOL..

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

    Even absolute newcomers with just a little idea of complexity won't write O(N^2) solution at this constraints without reasoning. So, what are you talking about? They at least got the intuition and getting it isn't hard. It's just getting the fact that if you have large N, then you would have duplicates in sum simply because of so much options to choose sum and limited options for sum.
    So, not actually many of them, only like 1-2% at most without knowing reason tried out O(N^2).

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

Problem C. Going Home. In statement n is <= 200000. So why O(min(n^2,n+C)) doesnt have TLE?

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

In the problem B, the numbers are distinct which isn't stated in the statements. That's a major issue.

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

Can someone explain what is wrong with my solution in Div2C?

I got FSTed. I used four pointers.

https://codeforces.com/contest/1501/submission/109878799

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

    This approach is not enough.

    When d>0, you have an option to increase z.

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

      Therefore, you have >= 2 options for d>0 (and also for d<0); and it makes the proposed pointer-based approach unworkable (since you do not know when you should increase z or decrease w).

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

what is "y" in the editorial of div1B/div2D?

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

They added few more test cases in Div 2 Problem C. Why my previous AC code is giving TLE on Test Case 73?

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

PROBLEM( B + A ) LINK : https://www.youtube.com/watch?v=MUnsGm0K8Qw

HAPPY CODING

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

I haven't seen anyone else do this, but div. 2 B can be solved with Fenwick. 109919812

The idea is basically to keep a BIT of the number of layers of syrup on each layer of cake.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm going crazy. Can anyone tell me why my solution gives WA on test 12? problem div2.D and my code, Thanks.

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

How is C:Going Home Accepted in quadratic time?

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

can anyone please tell me why my solution gives runtime error on test case 11 of problem D here is my solution solution

thanks in advance

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

div1A I got ac,but my code 110017025 was wrong wrong test: 5 1 1 1 1 4

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

[Div-1 'B']

If n and m are not coprime, participant can make transition (n,m)→(ngcd(n,m),mgcd(n,m)), solve new equations, and then make reverse transition

How to do that?

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

In Going Home question the constraint for n is 2x10^6 and all the solutions are getting A.C on O(n^2) should it not give the TLE. Why it is not giving TLE can somebody tell me?

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

Can somebody please tell me why my code:110064321 TLEs in Div.2D and any possible optimization I can do? Thanks.

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

My solution for d works in O(max(n, m)) time. So first you check if the solution will be found after n*m days(because that will 100% get both sequences lined up again). To do so you take the smaller array and find how many same numbers it will have in every cycle(1 cycle is min(n, m) days) in bigger array. For example if you have 3 2 1 0 and 3 1, at cycle 0 (3 2 : 3 1) you will have 1 same occurance, at cycle 1 also(2 1 : 3 1) and in others 0.To do so fast you find where every element from smaller array belongs in bigger and to get the position of cycle subtract the index of element in smaller array(so 1 is on index 2 in bigger array but because it is second element in smaller it will belong to 2 — 1 = 1 cycle). After that you just n times add number of different elements in cycles (to do so you just have i — cycle you are currently at which is 0 at start and with every iteration it will become (i + m) % n because 1 cycle is m days so you move m elements on bigger array). After you add all the values(lets say into SUM) of numberofdifferentoncyclei you can check if that number is bigger than k and if it is you add to your answer(int)(k / sum) * n * m and subtract from k (int)k / sum * sum so we now know that k < sum. After that we can just do one more iteration over cycles to find at whichn our sum will become greater than k and get our answer. Check the code for better understanding.110062516

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

DIV2A was so hard to understand it made me punch the wall.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For 1500A - Going Home, I found the editorial's solution really hard to optimize to fit into the 2s time limit. However, if we first do an $$$O(n)$$$ pass to filter out the test cases where there is a value with frequency $$$\ge 4$$$, or at least two non-unique values (in those cases, a solution can be easily constructed), we could then know that the solution, if it exists, must involve four distinct values. Thus we only need to store up to one pair for each sum (finding the second disjoint pair will allow us to construct the solution) This significantly improves the constant factor for the solution, and easily passes in Kotlin.

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

Matrix Sorting's tests can be passed using O(n*m*m) solution.

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

can somone explain nicely 1500 A ????

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

little suggestion: cf would be better if we can copy the test case we WA when debugging, some of test cases are too long, allow us to copy that would really help a lot

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

TL for Div 1 E is tooooooo tight !!!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain why my solution is wrong.?

My_Solution

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

.

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

Please share the code for the napoleon cake problem; I am unable to understand it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

alternative solution for div2C: after sorting a, assume a[x]<a[y]<a[z]<a[w] a[x]+a[w]=a[y]+a[z] => a[x]-a[y]=a[z]-a[w] if the array contains two pairs of number, which has same difference, answer is yes. now we can choose two pairs and check if a-b=c-d (two pairs with same difference exists) in O(n^2logn) complexity using a map, which will give TLE.

say all the distinct pairwise adjacent difference are unique (so that answer is NO) , then array will be like — 1 2 3 5 7 10 13 17 21 ... (2-1 = 3-2 can apprear, as they both contains 2, which won't lead to any answer. differences 1,2,3,4... each can appearch at most 2 times). kth term of the sequence = floor(k^2/4) + 1

this implies a[i]_max = floor(k^2/4) +1 = 2.5 * 10^6 => k=3161.277 ~ 3162 there can be atmost 3162 terms without having same adjacent difference between two distinct pairs. so if n>3162, we can only check if there exists two same adjacent difference which can be done in O(nlogn) and if n<=3162, we can do a O(n^2) brute force.

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

Can anyone help me with DIV2 B PLEASE.........

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

How can I know that a problem like going home is doable in n^2 when the input is of the order 10^5? I thought n^2 could only handle 10^4...