vaaven's blog

By vaaven, history, 5 months ago, In English

Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 953 (Div. 2), which will start on 16.06.2024 12:05 (Московское время). 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
  • +249
  • Vote: I do not like it

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

interesting score distribution

»
5 months ago, # |
  Vote: I like it -15 Vote: I do not like it
»
5 months ago, # |
Rev. 6   Vote: I like it +14 Vote: I do not like it
Spoiler
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    A Question which I can't resist to ask you:
»
5 months 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.

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

As a tester, I tested the round yesterday

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

Thank you, and I wish everyone success!

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

Please notice the unusual time!

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

Comeback Round

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

As a tester, do try all the problems.

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

Score Distribution is really good. Excited for tomorrow.

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

Hopefully I solve a,b and c .

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

If FynjyBath = tester, round = good

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

Hoping to reach pupil ;)

»
5 months 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

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

Clashing with Shanghai CPC, skipping this one

»
5 months 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

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

good luck, hoping for +delta

  • »
    »
    5 months 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.

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

Hopping for +delta

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

OMG Mikhango!!!!

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

Potential SpeedForces on the way!

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

sounds like CodeForces Round 879 Div. 2

https://codeforces.me/contest/1834

»
5 months 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.

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

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

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

Woowww score distribution so interesting

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

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

»
5 months 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 !!!!

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

Let's do it..

»
5 months 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!!!

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

excited for this ,lets goooooo

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

Pre-Eid Day Contest , Participating

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

GLHF, hope I become expert today

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

Getting good vibes for this round

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

Meow.

»
5 months 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

»
5 months 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.

  • »
    »
    5 months 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! :)

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

good logic used today

»
5 months 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.

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

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

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

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

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months 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.

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

mathforces strikes again

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

darn I was an hour late! still fun contest tho

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

It was super gang bang

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

div 2.5?

»
5 months 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

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

submitted D with just 2 min left

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

Can someone explain why my code for D fails?

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

D felt little easier than C.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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).

      • »
        »
        »
        »
        5 months 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)

        • »
          »
          »
          »
          »
          5 months 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.

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

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

        • »
          »
          »
          »
          »
          5 months 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.me/contest/1978/submission/266038667

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

  • »
    »
    5 months 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).

  • »
    »
    5 months 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

  • »
    »
    5 months 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 :(

»
5 months 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.

»
5 months 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?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

»
5 months 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.

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

    how you solved e?

    • »
      »
      »
      5 months 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.

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

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

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

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

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

        E is a prefix sum problem.

      • »
        »
        »
        »
        5 months 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.

    • »
      »
      »
      5 months 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;
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I think E is easier than C.

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

D and E are both easier than C.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months 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.

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

      What did you find hard to prove in C ?

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

        I quickly came up with a guess that I just need to use the elements from two ends of the array. However, I couldn’t prove that it’s the optimal way and after 30 minutes of thinking I submitted the code and found it accepted.

»
5 months 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?

»
5 months 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.me/contest/1978/submission/266042353

  • »
    »
    5 months 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

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

      but I have #define int long long

      • »
        »
        »
        »
        5 months 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.

  • »
    »
    5 months 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).

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

How to solve F?

  • »
    »
    5 months 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.

»
5 months 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).

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

    got the edgecase with a_i = 1?

    • »
      »
      »
      5 months 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!

»
5 months 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.

  • »
    »
    5 months 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.

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

long longforces

»
5 months 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.

»
5 months 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

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

    I did it with Arithmetic series

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

»
5 months 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?

  • »
    »
    5 months 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 .

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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?

»
5 months ago, # |
  Vote: I like it 0 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 ???????

»
5 months 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
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    if k > 2*n ,you wasted.

    • »
      »
      »
      5 months 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$$$

      • »
        »
        »
        »
        5 months 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$$$

»
5 months 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

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

oops!

»
5 months 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

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

Can someone please share a typical case for D?

»
5 months 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.

»
5 months 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).

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

why its not working???? PROBLEM D

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

System test when?

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

testing please we wanna submit unsolved

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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(

»
5 months 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.

»
5 months 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

»
5 months 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)

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

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

»
5 months 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

»
5 months 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

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +73 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?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

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

    LOL yeah I agree

»
5 months 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.

  • »
    »
    5 months 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.me/contest/1978/submission/266151360

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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!

»
5 months 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

»
5 months 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?

»
5 months 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

»
5 months 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

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

Best contest for me.

»
5 months 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??

»
5 months 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..

  • »
    »
    5 months 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.

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

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

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

round is relatively div2

»
5 months 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.

  • »
    »
    5 months 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

»
5 months 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.

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

Editorial is not published in contest materials

»
5 months 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?

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

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

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

d1mk orz

»
5 months 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.

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

Can someone please explain how problem E can be solved?

»
5 months 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.

»
5 months 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

»
5 months 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

»
5 months 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.me/contest/1978/submission/266093452

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

Please release the tutorial

»
5 months 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.me/contest/1978/submission/266099707

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

its true

»
5 months 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.

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

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

  • »
    »
    5 months 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.

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

For me after upsolving F is much easier than C xd

»
5 months 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.

»
5 months 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.

»
5 months 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

  • »
    »
    5 months 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

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

      I request vaaven to please have a look at these and kindly remove my plag

»
5 months 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.

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

E < D < C

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

My cf id is not opening and handle is kxhitz I had given last contest on 16th June 2024. Please check it out and resolve this issue as soon as possible.

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

Thanks you for good contest! I enjoyed it!

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

what is the penalty for wrong submission for div2 ? time or points or nothing ?

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

You are welcome

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

Thank you to all the problem setters and testers for an engaging and challenging contest! I found problems B and C particularly interesting due to their unique approaches. Looking forward to the next round and hoping to see more creative problems like these!

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

I got a Wrong Answer on test 2 in problem E. Can any one help me? Many thanks.

Code