vaaven's blog

Codeforces Round 953 (Div. 2)
By vaaven, history, 4 days ago, In English

Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 953 (Div. 2), which will start on Jun/16/2024 12:05 (Moscow time). Note the unusual start time of the round. You will be given 6 problems and 2 hours to solve them.

This round will be rated for participants whose rating is below 2100. Participants with higher rating can participate unofficially.

The problems were authored and prepared by Artyom123, IzhtskiyTimofey, bashkort, TheEvilBird, 127.0.0.1, Tikhon228 and me.

The round is based on All-Russian olympiad in the name of Keldysh.

We would like to thank

Score distribution: $$$500 - 750 - 1250 - 1500 - 2000 - 2500$$$

UPD: Editorial

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

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

interesting score distribution

→ Reply
»
4 days ago, # |
  Vote: I like it -15 Vote: I do not like it

culver0412 orz

→ Reply
»
4 days ago, # |
← Rev. 6   Vote: I like it +14 Vote: I do not like it
Spoiler
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    A Question which I can't resist to ask you:
    → Reply
»
4 days ago, # |
  Vote: I like it -57 Vote: I do not like it

The contest time is unusual. But, I hope, the 'Dashboard' will be usual insha-Allah.

→ Reply
»
3 days ago, # |
  Vote: I like it +49 Vote: I do not like it

As a tester, I tested the round yesterday

→ Reply
»
3 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Thank you, and I wish everyone success!

→ Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Please notice the unusual time!

→ Reply
»
3 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Comeback Round

→ Reply
»
3 days ago, # |
  Vote: I like it +22 Vote: I do not like it

As a tester, do try all the problems.

→ Reply
»
3 days ago, # |
  Vote: I like it +89 Vote: I do not like it

what if instead of div2 it was freak2 and instead of solving problems everyone started violently edging

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    i think this is the sign i asked god for

    → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    we got the evolution of brainrot on codeforces before GTA VI

    → Reply
  • »
    »
    2 days ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    when i do silly comments i get downvotes but when someone else does it :(

    → Reply
  • »
    »
    44 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Let me tell you the story when the level 600 school gyatt walked passed me, I was in class drinking my grimace rizz shake from ohio during my rizzonomics class when all of the sudden this crazy ohio bing chilling gyatt got sturdy, past my class. I was watching kai cenat hit the griddy on twitch. This is when I let my rizz take over and I became the rizzard of oz. I screamed, look at this bomboclat gyatt

    → Reply
»
3 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Score Distribution is really good. Excited for tomorrow.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Eid Mobarak all Muslims

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I solve a,b and c .

→ Reply
»
3 days ago, # |
  Vote: I like it +18 Vote: I do not like it

If FynjyBath = tester, round = good

→ Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Hoping to reach pupil ;)

→ Reply
»
3 days ago, # |
  Vote: I like it +4 Vote: I do not like it

scoring distribution is asking me to solve abcd. I hope I can full fill its question

→ Reply
»
3 days ago, # |
  Vote: I like it -27 Vote: I do not like it

Clashing with Shanghai CPC, skipping this one

→ Reply
»
3 days ago, # |
  Vote: I like it -6 Vote: I do not like it

If I solve a,b,c in first hour I give my team eidia else Mohamed Hassan daeeeeef

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck, hoping for +delta

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    alr nvmd not doing this comp. I dont wake up till 8:00 AM EST.

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopping for +delta

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG Mikhango!!!!

→ Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Potential SpeedForces on the way!

→ Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

sounds like CodeForces Round 879 Div. 2

https://codeforces.com/contest/1834

→ Reply
»
3 days ago, # |
  Vote: I like it +14 Vote: I do not like it

bashkort orz . Just wanted to tell you that your pfp is my favourite pfp I have seen on codeforces. It looks cool af.

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Thank you! That's ooes, my favourite singer :)

    → Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Woowww score distribution so interesting

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

my rating is below 1000. should i participate in this?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am on the verge of becoming a specialist. Lets hope for the best !!!!

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's do it..

→ Reply
»
2 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Good start time for Chinese.And I hope I can become Expert in this contest!!!

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

excited for this ,lets goooooo

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
Spoiler
→ Reply
»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Pre-Eid Day Contest , Participating

→ Reply
»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

GLHF, hope I become expert today

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting good vibes for this round

→ Reply
»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Meow.

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, we thought too hard, the problems were pretty good and balanced in my opinion

→ Reply
»
2 days ago, # |
  Vote: I like it +3 Vote: I do not like it

WOW, this time the problems are more interesting but easier (I think) than normal div.2. This is my first time to AK in div.2 haha.

→ Reply
  • »
    »
    44 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's because it's based on Junior Russian Olympiad in Informatics, which is for lower grade students. So the problems shouldn't require any special knowledge. GG! :)

    → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good logic used today

→ Reply
»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

C would be enjoyable if we didn't have to print the permutation.

→ Reply
  • »
    »
    2 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Got an edge case where my permutation wasn't working..

    → Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    C would be A if we didn't have to print the permutation

    → Reply
    • »
      »
      »
      46 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      your solution to C is awesome !! I can't believe I overcomplicated it so much. Thank you.

      → Reply
  • »
    »
    47 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then C would have been a piece of cake :D Btw, I figured the logic easily but spent about 2 hours to print the correct permutation. Still I am happy since this is the first time I solved 2 div 2 questions in under 30 mins.

    → Reply
»
2 days ago, # |
  Vote: I like it -7 Vote: I do not like it

mathforces strikes again

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

darn I was an hour late! still fun contest tho

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It was super gang bang

→ Reply
»
2 days ago, # |
  Vote: I like it +30 Vote: I do not like it

div 2.5?

→ Reply
»
2 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Why did you not let the much harder segment tree solution pass in E? I mean TLE

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

submitted D with just 2 min left

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why my code for D fails?

Spoiler
→ Reply
»
2 days ago, # |
  Vote: I like it +44 Vote: I do not like it

D felt little easier than C.

→ Reply
  • »
    »
    2 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Huh? Really?

    I only came up with an idea for D at like the 115th minute, and I had solutions for all the remaining (and prepassed them all, except E) o.O

    → Reply
    • »
      »
      »
      2 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The idea of D is not that hard to come with, only separate when u analyze a candidate with maximum number of votants and the other case is very easy since u have to remove all candidates with index smaller always (and chose or not to remove a candidate with maximum number of votants).

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

        I'm still in the blank honestly. Can you clarify further? (I don't even believe the idea I was about to submit for D would be correct either)

        → Reply
        • »
          »
          »
          »
          »
          2 days ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          i mean, if the candidate that u r analyzing don,t have the maximum number of votants at the beggining, u have to remove all previous candidates, and if after that u don't have the maximum in that candidate u have to remove one of the candidates that in the beggining had the maximum number of votants so in the first case u print (index-1) and in the other (index).

          The other case is that u r analyzing a candidate that have the maximum number of votants since the beggining, in that case if the index of that candidate is the smaller between all the others that have the maximum number of votants u print 0, either case u print (index-1) cause u have to remove all previous candidates.

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

            Ah, got it eventually. Thank you. Now I feel doubly silly...

            → Reply
        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          So I went with the idea of prefix sum and maxElement on the right of index i.

          1) If the number fans of ith candidates are alone enough to win him the election then 0 candidates have to be removed.

          2) If the number of fans of ith candidate are not able to win him the elections then we need to take help of the undecided voters and they will always vote the lowest index candidate that means all the candidates with index < i must be removed. If the sum of fans of index < i + a[i] + undecided voters given is >= max element on the right of the index i then the answer would be i-1. Else we also have to remove the candidate with the maximum fans on the right side of i along with all the the candidate on the left that means (i-1) + 1.

          prefix sum and max element on the right side of ith index can be computed before the start of iteration.

          3) one edge case that needs to be considered is if a[0] + undecided is already >= the max of the whole array then we have no choice but to remove the prefix of the ith index in every iteration

          Link : https://codeforces.com/contest/1978/submission/266038667

          sorry for the bad English. Also can someone please tell me how to add code / message in spoiler dropdown ?

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

    I think that's not very clear, D is easier to implement but requires more clear-cut idea than C, C feels closer to implementation problem (and a bit harder to implement).

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

    && i give 1 hour+ on C... After the contest , i realized i should try D

    → Reply
  • »
    »
    47 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed I felt the same... I came up with the solution much faster than C. But still got WA in D due to silly mistake :(

    → Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

5 seconds away from submitting D... I was too drowned on E+F and that wasted my time... :(

UPD: That D actually AC'd. I have myself to blame, I guess.

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, I resolved the problem into the following Given a list of segments, for each query l, r find number of segments that fall into [l,r]. I'm not sure how to build a segtree for this (the merging part). Any hints?

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

    Your reduction is correct. You can solve the queries offline with a simple point-add range-query segment tree.

    → Reply
  • »
    »
    2 days ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Precalculate A array. Notice for each query only numbers on edges(a[l], a[l + 1], a[r — 1], a[r]) change. Calculate them manually.

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

    As r-l+1<=5, you can actually use 5(in fact 4) partial sum arrays to solve the problem.

    → Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Imho E was quite easy, easier than D and probably even C, I am surprised there are not that many AC.

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

    how you solved e?

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

      I didn't solve it (my code got buggy), but it seems like E is a standard sqrt-decomposition problem.

      → Reply
      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You probably over complicated it, u can see my code:)

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

          Just shuffled my mind again, silly me I guess. Thank you...

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

        E is a prefix sum problem.

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

        you can answer l+2----r-2 by precalculation. by doing some calculation, you can merge the answer.

        → Reply
    • »
      »
      »
      2 days ago, # ^ |
      ← Rev. 6   Vote: I like it +6 Vote: I do not like it

      Suppose we have a whole string. Then the algorithm is first:

      s: 0.0 -> 0.0
t: ... -> .1.

      and then

      s: ... -> .1.
t: 1.1 -> 1.1

      Save the new s and t into s_aug and t_aug

      This is quite obvious, we always improve answer. You can check that after running those 2 steps neither of steps repeated would change anything.

      We can precalculate prefix sums on final t and use it to get number of ones in the segment.

      Now, actually we have substrings. The key is to notice that only 2 first and 2 last elements could be different from what we calculated initially, so we need to handle those elements manually, it would be O(4).

      Answer would be result for manual cases + sum_inclusive(t_aug, l+2, r-2)

      Cases with len of segment < 4 are easier to hardcode separately.

      P.S I made stupid off-by-one error initially so had to write stress test, it wasn't complicated but still wasted a bunch of time :(

      The main part of code:


              // for substrings with len >= 4

        let t_aug_l_old = t_aug[l];
        let t_aug_r_old = t_aug[r];

        t_aug[l] = t[l];
        t_aug[r] = t[r];

        // s[l] and s[r] are exactly like they was initially
        let mut ans = s[l] + s[r];

        if s[l + 1] == 1 || (t_aug[l] == 1 && t_aug[l + 2] == 1) {
            ans += 1;
        }
        if s[r - 1] == 1 || (t_aug[r] == 1 && t_aug[r - 2] == 1) {
            ans += 1;
        }

        out.print_line(ans + prefix_sum(l + 2, r - 2));

        // just restore
        t_aug[l] = t_aug_l_old;
        t_aug[r] = t_aug_r_old;
      → Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I think E is easier than C.

    → Reply
»
2 days ago, # |
  Vote: I like it +43 Vote: I do not like it

D and E are both easier than C.

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I think E is the easiest problem in CDE and D is the hardest

    → Reply
    • »
      »
      »
      2 days ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I overcomplicated D for myself (I see segtrees everywhere these days), but actually it's not as bad as it may seem, you can solve it with just a multiset alone.

      What D boils down to

      That being said I myself got lost figuring out what do I want to do with segtrees.

      → Reply
  • »
    »
    44 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Indeed. I think the hardest part in C is how to prove the correctness of the solution.

    → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why it's not working 266036235 problem D

I know this will TL anyway but, quite shock that even brute force solution got WA on pretest 2 am I understand something wrong completely?

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

does someone know why I got idleness limit exceeded on C. I'm so sad right now :(

https://codeforces.com/contest/1978/submission/266042353

→ Reply
  • »
    »
    47 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that 0 <= k <= 10^12, but you use "int". So k may fail to read. Then in the next test, n may fail to read. At that time, you creat a vector with size n(n may be a large interger). So you will get "MLE". (Forgive my poor English

    → Reply
    • »
      »
      »
      47 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but I have #define int long long

      → Reply
      • »
        »
        »
        »
        47 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "mx += abs(2 * i — n + 1);" should be "abs(i — (n — i + 1)) = abs(2 * i — n — 1);" Because of this mistake, "while" will not stop But I don't know why it get "MLE". Perhaps "swap" does lots of copy.

        → Reply
  • »
    »
    39 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your loop is wrong:

    for (int i = 1, c = n; i <= n; i++, c--) {
    mx += abs(2 * i - n + 1);
}

    This does not sum to $$$(n*n)/2$$$. Example testcase: 2 4. Expected output No, the output on my machine is Segmentation fault (core dumped).

    → Reply
»
2 days ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Extend the original array into $$$a_2, a_3, \dots, a_{n-1}, a_n, a_1, \dots, a_n$$$, then use DSU to connect the elements of that new 1D array.

    Corner case: if $$$a_i = 1$$$, all appearances of it in the matrix must be counted separately.

    → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats in test 2 of F? Any counterexamples? (My solution is kind of scanline on dividers).

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

    got the edgecase with a_i = 1?

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

      Wait, when we have 1s on diagonal, we can't collapse them into one component... Okay, guess my code only works when a_i=1 is the last element... Thanks for the hint!

      → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a great round! I hope my C won't FST... I don't understand what is wrong with my solution for F, btw, like no idea. So sad couldn't find mistake during the round.

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

    Okay, i was never connecting $$$a_i = 1$$$, sad. My solution still will get TL, but, if i saw that during the round, i would probably come up with better complexity.

    → Reply
»
2 days ago, # |
  Vote: I like it -12 Vote: I do not like it

long longforces

→ Reply
»
2 days ago, # |
  Vote: I like it +16 Vote: I do not like it

I guess many people, including me, got confused that the word "number" was used instead of index.

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Just Found out that B can be done without Binary search.. Maybe I think too much LOL. 265999363

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

    I did it with Arithmetic series

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

    I used ternary search, I thought that it's the most straightforward way to do it lol

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

      Lol now I see poeple have done it in O(1), feel ashamed hahaha

      → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how to proof C that we have to take the two pointer and if 2*diff<=k then we reduce it else either p1++ or p2--. Anyone?

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

    First, if you swap all pos(1,n, 2,n-1 , 3,n-2.....), the ans is max ans you can get. Then ,when you p2--, the new ans -= 2, since answer exist only when k % 2 == 0,so it can reach all legal k .

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

      Thanks, got it! I started thinking in terms of set bits in k therefore got confused although D was easy than C.

      → Reply
    • »
      »
      »
      47 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you explain how to prove that we get max with that configuration?

      → Reply
»
2 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Such a fool contest! For prob. A to prob E, there's nothing harder than suffix sum! How can this Contest be Div.2 ???????

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why does the idea of swapping $$$i th$$$ and $$$i+k/2$$$ th elements not work for task C?

Code
→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    if k > 2*n ，you wasted.

    → Reply
    • »
      »
      »
      2 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      can you please elaborate?
      I had a post check after swapping elements that answer is possible iff after all swappings, $$$k>0$$$

      → Reply
      • »
        »
        »
        »
        47 hours ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        My bad, I gave up in the contest, but, it was a ridiculous mistake.
        Here is the AC submission, it uses the same idea as above: 266053962.
        The only difference is that $$$cnt$$$ starts from $$$1$$$

        → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

would have been great for me if i had not wasted time in B

→ Reply
»
2 days ago, # |
  Vote: I like it +133 Vote: I do not like it

oops!

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It was not possible to make a better contest !! Hats Off to vaaven

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please share a typical case for D?

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me the TC where this code gets runtime error[submission:266046159]. Approach:We can always create any K greedily if its even and is less than the max value achievable.Then we know that if we swap two values,then twice of their difference contributes to K,so i have halved the value of K to x.Then using binary search on set to get maximum possible value which we can attain to decrease x, we swap both of them and decrease x.We repeat until x is 0.

→ Reply
»
2 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Nice overall round with +ve delta forces. I think this round was a great opportunity to gain some positive delta bcz the problems were a bit easier than a normal div 2 round. Kudos to the tester who gave us the hint to read all the problems bcz I think there was a good chance an average newbie coder could have also solved D if he was a bit sincere on the clock(unlike me).

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why its not working???? PROBLEM D

Code
→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

System test when?

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

testing please we wanna submit unsolved

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

    I don't know if I should be happy or sad if my compiled error submission gets accepted after I fix it

    → Reply
    • »
      »
      »
      47 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i fixed silly bug after 1 min contest ended and now it got accepted(

      → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am so ded rn,i forgot that iterator doesn't copy it points to original location,which returned ruined my C solution.

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone give the test case for problem C where this submission is giving wrong answer 266027942

UPD: Nvm got it

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

solved my first div 2 problem in contest (just A but still happy about it)

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Ayyo... Why am I getting Idlesness error in C??? 266040778

→ Reply
»
2 days ago, # |
  Vote: I like it +26 Vote: I do not like it

on problem A and D why don't you just say index instead of number ... what a problem statement

→ Reply
»
2 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Will this solution work for E?

https://www.ideone.com/PApbrg

I was very slow in contest, I assumed that E would be harder and started it very late.

LOL it turned out to be easier

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved B using calculus first derivation. I know this is not intended solution. But I would love to share here because it was interesting.

Noticed that the answer should be

$$$a(n - k) + bk - \frac{k(k + 1)}{2} + k$$$

you can use gaussian for this computation.

You can modify this to make $$$f(k) = -\frac{1}{2}k^{2} + (b - a + \frac{1}{2}) k + an$$$

You can look for the maximum $$$f(k)$$$ using first derivation, $$$k = b - a + \frac{1}{2}$$$. Don't forget to check the answer with $$$k = 0$$$ and $$$k = min(n, b)$$$ as the boundaries.

→ Reply
»
2 days ago, # |
  Vote: I like it +65 Vote: I do not like it

Statements were a bit unlcear, in my opinion.

  • A: The statement says "highest number", but I can't find where 'number' is defined. There are many other places where 'number' is used, but some of them are referring to 'number of pages'. There is no place where it says 'number' actually means $$$i$$$. It is not obvious that '$$$1$$$-st book' means that the 'number' of the book is $$$1$$$. It could be more clearly stated, or could just be replaced with another word.

  • B: The story of the legend is misleading. Like, Bob organized the promotion to "attract customers", but he's trying to sell them even more expensive than they currently are? Why would customers be attracted to such promotion?

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    To add to that, in problem B it felt like the variable $$$b$$$ was introduced in the statement with too little explanation. Like, the first explanation of what $$$b$$$ actually represents only comes up in the input section so until that point you're just kinda left to assume that it's probably just an input parameter.

    → Reply
    • »
      »
      »
      45 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      100% agreed I was very confused that what is b. The only way I got it by looking at the test case explanations.

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

    LOL yeah I agree

    → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I just realized my solution for F had a very terrible sieve, that it didn't really puncture composite numbers — so instead of listing all prime divisors for integers in range $$$[1, 10^6]$$$, it lists all divisors instead (this will affect the DSU process later on since the number of edges are increased drastically).

Solution: 266020666

Can it be uphacked? Thanks in advance.

→ Reply
  • »
    »
    27 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I am doing the same , with primes , getting TLE on 3rd test case , any idea the weak areas in the code . https://codeforces.com/contest/1978/submission/266151360

    → Reply
    • »
      »
      »
      27 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Your map loop was unnecessary: you can just go through all pointers of the map instead of looping from 1 to maxi, also index-accessing a map is dangerous as it will create memory block on keys not yet initialized.

      Should a test like this appears $$$10^5$$$ times:

      2 4
1 1000000

      it would be pretty likely that you'd TLE/MLE due to that, as that loop will certainly create $$$10^{11}$$$ blocks in total.

      My fix: 266154363

      The fix still has a RTE though, but it seems easier to patch that (it also has CF's diagnosis log), so I'll hand it back to ya.

      → Reply
      • »
        »
        »
        »
        27 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh , thanks , maxi i was intially trying but i removed that , forgot to remove from the area (you are pointing) . Me idiot

        → Reply
      • »
        »
        »
        »
        27 hours ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Also that RTE is because of spf vector is of N= 1e6 length but the numbers can be upto 2e6

        → Reply
  • »
    »
    26 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Finally, after so many attempts I made it :)

    Providing the same numbers with most number of divisors didn't really work (they took only around 3.6s), so I tried a bit of things to slowdown other aspects, mostly to cause cache misses. Still I must not have lowered the number of divisors of the numbers too much, so I tried to find some integers that:

    • have at least $$$x$$$ divisors
    • maximize the size of the set of the divisors of all integers

    Then it was about trying with different $$$x$$$'s and the number of integers (which I mostly went with 10, to repeat exactly $$$t=10^5$$$ times). It also took me some tries to shuffle with different seeds to make it actually exceed 4s, as in average it was still around 3.7~3.9s.

    → Reply
    • »
      »
      »
      25 hours ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Freaking hell, so even this uphack was gacha-based. Thank you for your effort though, it was fun witnessing and reading your approach on it!

      → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest. Absolutely Loved it. This was my first time solving Div2 B & C

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why does this solution to E give wrong answer? Can you suggest a countercase?

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

The wording threw me off so bad for A and D that it took more time to solve A than it took to solve D. v_v

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody point out the error in my code of c or give me a test case where my submission is failing?

Submission id is 266045808

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Best contest for me.

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest me how to plan to solve the correct questions?? Since many of you are saying that D and E were both easier than C. But I solve in order and presume that E>>D>>C in difficulty so no point in reading it. I solver A and B under 30 mins, figured the logic of C easily but it took me 2 hours to implement it and AC'd after the contest was over. I am still a newbie (hopefully will become Pupil now) so can you guys please suggest me how to plan to solve the right questions??

→ Reply
»
47 hours ago, # |
  Vote: I like it -82 Vote: I do not like it

Indian are cheaters 99.99% from indian are cheaters and the other 0.01% are idiot and cheaters

ban_india

ban_every_miboun_indian

→ Reply
  • »
    »
    47 hours ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    +1 damn such amount of cheating on C,what will someone achieve after all this.

    → Reply
  • »
    »
    47 hours ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    bro can't even solve 2 questions in an easy div-2 contest and blames indians for his performance.

    → Reply
    • »
      »
      »
      46 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yaatek assba ala rassek

      → Reply
    • »
      »
      »
      46 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What Telegram channel do you use to code? XD

      → Reply
      • »
        »
        »
        »
        46 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        None, you can see my codes. I just want to say that you can't say cheaters to all indians. Cheaters are there, but not everyone is a cheater.

        → Reply
        • »
          »
          »
          »
          »
          46 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          After some research I just find that there are a huge number of YouTube channels and telegram channels that publish solutions while the contest is still running. Guess what all the channels I found are from India . Broo you Indians are just ruining our journey in codeforces

          → Reply
          • »
            »
            »
            »
            »
            »
            46 hours ago, # ^ |
              Vote: I like it +21 Vote: I do not like it

            See from India, the no. of users are almost 70000 and from your country it is somewhere around 1100. There is a vast difference. Because of a such large no. of users, it is always possible that a group of users are cheaters. But that doesn't mean that all users are cheaters. And I want to say to you just one thing that you shouldn't care about cheaters, codeforces will take care of them, you should try to focus on you problem solving skills and that will be good.

            → Reply
          • »
            »
            »
            »
            »
            »
            45 hours ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            India is full of cheaters, it's ingrained in our culture.

            → Reply
    • »
      »
      »
      46 hours ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      at least i solve by my mind not telegram

      → Reply
  • »
    »
    42 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I apologize on behalf of my countrymen; it's sad

    → Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

i was doing Binary seach on the problem B for optimal k which gives me the max profit but getting wromg answer i dont know which case is not being handled pair<ll,ll> possible(ll n,ll a,ll b,ll mid,ll initial) {

ll val=mid*b;
    // cout<<mid<<endl;

    ll val2=((mid-1)*mid)/2;
    ll sell=val-val2;
    ll sell2=(n-mid)*a;

    ll profit=sell+sell2;

    if(profit>initial)
    {
        return{1,profit};

    }
    else{
        return {0,initial};

    }

}

void solve() { ll n,a,b; cin>>n>>a>>b;

ll low=0; ll high=n; ll initial=n*a;

while(low<=high) { ll mid=(low+(high-low)/2); pair<ll,ll>temp =possible(n,a,b,mid,initial);

if(temp.first==1)
        {
            initial=temp.second;
            low=mid+1;

        }

        else{
            high=mid-1;

        }

} ll val=n*b; // cout<<mid<<endl;

ll val2=((n-1)*n)/2;
    ll sell=val-val2;
   if(sell>initial)
   {
    cout<<sell<<endl;
    return ;

   }

cout<<initial<<endl; return; can check my code..

→ Reply
  • »
    »
    45 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should use ternary search. Cause if you keep increasing k the answer will keep increasing and at some point it may start to decrease. So there is a peak.

    You can also differentiate the equation to find the maxima, which is actually the desired value of k.

    → Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro... 2 rating points away from pupil...

→ Reply
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

round is relatively div2

→ Reply
»
46 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

I can't believe how 6000 coders solved C.I would like account verification to be more difficult. Because it's unreal to watch how many guys who write for the first time pass ABC.

→ Reply
  • »
    »
    42 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I was able to solve C started contest half hour late immediately got the idea but implementation omg 266044140 took me around 5 attempts good thing was you can debug C easily if something went wrong its amazing how people were able to implement on first go .. also if anyone wants to hack my solution feel free because I am still not sure about some edge cases

    → Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

CDE should've been in reverse order, C took too much of my time and couldn't solve D due to a small implementation error. Upsolved E pretty quickly.

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial is not published in contest materials

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why did my rating drop down by 4 even after solving 3 problems(ABC) today?Can someone explain how does this rating change works? Is it coz I got ranked lower than my rank in previous div 2 round?

→ Reply
»
46 hours ago, # |
  Vote: I like it -6 Vote: I do not like it

Before Eid-day, I am back to CYAN!!!

→ Reply
»
45 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

d1mk orz

→ Reply
»
44 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

266080165 Can anyone tell me what's wrong with my problem D solution, it fails in the second test.

→ Reply
»
44 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how problem E can be solved?

→ Reply
»
43 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone address the 'Unexpected verdict' issue on my hack? It's just a simple $$$t=10000$$$ test where 9999 of them are 1 10^12 and the last one is 190001 18050190000 to hack an $$$\mathcal{O}(n^2)$$$ solution with slow I/O. I don't think any intended solution is supposed to get hacked on this test.

UPD: resolved.

→ Reply
»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Though I couldn't solve it in the contest, D is such a nice problem

→ Reply
»
43 hours ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I can't delete my comment so I'm editing it

→ Reply
»
43 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

B can be solved using ternary search i think it should be added as a tag https://codeforces.com/contest/1978/submission/266093452

→ Reply
»
42 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Please release the tutorial

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

hey everyone, this is my submission for problem c in div 2 contest, may someone tell me what is wrong with my code? even though my manhatten distance is correct? https://codeforces.com/contest/1978/submission/266099707

→ Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

its true

→ Reply
»
39 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

C appeared before in last year's ECPC, likely giving some participants an advantage since C > ABDE. This is probably a coincidence, but it suggests that the selection of testers should maybe consider representation from all regions, or at least the major ones.

→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why binary search on k won't work in porblem B ?

→ Reply
  • »
    »
    38 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because the Bob's profit expressed as a function of k is not monotonic but rather unimodal. So one can use ternary search to find k which delivers the maximum, though this is not the unique approach to solve this problem.

    → Reply
»
39 hours ago, # |
  Vote: I like it +16 Vote: I do not like it

For me after upsolving F is much easier than C xd

→ Reply
»
35 hours ago, # |
  Vote: I like it +17 Vote: I do not like it

Abnormal round. B with quadratic function, E,F with simple ideas which are easier than normal.

→ Reply
»
27 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

I suspect that the top1 cheated. Maybe more than 1 people use that account to submit.

→ Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did i get a plag on que E , it was a standard one the check the segments in a range only change being the inserting of l and r

→ Reply
  • »
    »
    7 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no response , anyways im uploading my notes(from a CP course) from which i copied the code(ig its not against the rules) Notes

    → Reply
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

As a chinese participant, it is a very usual time in the afternoon.

→ Reply