Supermagzzz's blog

Codeforces Round #702 (Div. 3)
By Supermagzzz, 10 days ago, translation, In English

Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #702 (Div. 3) will start at Feb/16/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems for this round were invented by MikeMirzayanov, Supermagzzz, Stepavly and sodafago.

Thanks to MikeMirzayanov for platforms and coordination of our work. Thanks to darkkcyan, Sho, sodafago, Nebuchadnezzar, kocko, akagami_no_shanks, Gassa, infinitepro, bfs.07 for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

UPD: Editorial is ready!

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

Comments Comments (168)
»
10 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Every announcement of Div3 round from Supermagzzz, Stepavly and MikeMirzayanov makes me happy!

→ Reply
»
10 days ago, # |
  Vote: I like it +87 Vote: I do not like it
As a
→ Reply
»
10 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Good luck everyone !!!

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

Sick, I miss div 3 contests so much, looking forward to participating into this!

→ Reply
»
10 days ago, # |
← Rev. 4   Vote: I like it -39 Vote: I do not like it

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

is div3 rated for someone with current rating < 1600 but his max rating >= 1900 ??

Edit : sorry i didn't see this Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

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

    It's based on current rating only. Max rating doesn't make a difference.

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

      so what about this point do not have a point of 1900 or higher in the rating. ?? what do they mean of trusted participants ?

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

        Accounts that have reached a rating >= 1900 at any point can safely be assumed to belong to the stages beyond amateur grade. Therefore, having them part of the "official standings table" that is published is likely to distort the actual standings list.

        Similarly, new accounts could be alts to high rated coders as well and including those would lead to similar results.

        Therefore, while the round will be rated for anyone below 1600 (at the time of the contest, I believe — or maybe registration, this is actually my doubt as well). The official standings list published simply won't contain the names of these "participants that may not be trusted as div 3 folk"

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

    I'm quite surprised that you had $$$203$$$ contests and you still didn't know.

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

Is the rated cap for rounds based on the user's rating at the time of the contest or at the time of the registration?

I tried searching for some relevant blog but couldn't find one.. Thanks in advance :)

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

    At the time of the contest rather.

    Calculation of rating, finalization of winners board logic happens after contest as well as validation of being trusted participant and/or below 1600 member.

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

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

    true story

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

    it is relatable . my mom 's TV sound !! is high everytime i give contest

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

    F

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

    The contest starts at 22:35 in CST(UTC +8). That is the time my family go sleep.

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

    Ah.. Stop farming contribution by someone else's ideas

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

      .

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

        Can't you count to 2?

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

          I just asked that if 2-gon is the international grandmaster 1-gon.. caz many pros make new accounts to give the lower rated contests... but everyone was downvoting it for no reason... N whats up with u man..its not binary. U can be a good coder n polite at the same time!!!! Now dont get overexcited u r just a pupil. Some 150 points more than me!!!!!!

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

            Stop attacking me — I did not downvote you, I promise. :)

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

    Same scene at my home. People having loud fun chat and me struggling to concentrate on how to solve the question

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

    OMG it's true

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

    The most relatable meme that I've ever seen in the comment section this far.

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

    Same, if you got WA then its very frustrating to think about.

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

Yah Codeforces Hey!

Yah hum coders hey

Yaha Cowding ho rahi hey!

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

Finally, a div3 round that I missed so much

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

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

1

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

Previous rating change unrolled, will this contest be rated for me ?

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

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

Back to back cf Round :D

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

Judging by my very poor performance of the last round(spoiler: never enter a round 40 minutes after it started:)) i think that this round should be rated for me. Are the new ratings coming until the start of this div3?

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

will the new ratings come before div3 or not ??

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

From the last contest there seems to be less participation because of busy schedules and lot of assignments of college.

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

As a participant, I wish no "Wrong Answer On Test x" situation.

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

is there any other div. 3 contest i have work so i usually cant participate in this one

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

This is my first time to compete in CF. good luck. 祝我好运！

→ Reply
»
9 days ago, # |
← Rev. 4   Vote: I like it -13 Vote: I do not like it

Okay

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

Wait is over ❤ Finally div 3 after long time

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

Goodluck, everyone <3

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

Thank you ! perfect time for div3

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

Wtfffff Muffinhead 6 problems in 9 minutes how is this even possible !!

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

    It seems that codeforces recognized him as a cheater because he is not on the scoreboard anymore.But I think that he his Benq with another account any ideas?

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

      Even for a legendary grandmaster that's too fast but that's weird why would he participate in unrated contest from another account

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

        I think it happened once before , remember that video on William lin's channel

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

I am unable too see problems or register can someone help?

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

Positive delta YES!!!!

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

Is it just me or these div3 rounds have become wayy too easy.

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

    Or you have become better?

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

      I don't think so maybe it's just more suitable for the target audience these days.

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

        A Supermagzzz round is an ez round

        I think they actually seem easier than the older div3s, especially with the 7-problem format.

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

    I think first few are harder while the last few are easier, nice problems overall.

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

    and here I am couldn't solve even "A"...don't know what's going wrong :(

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

is this a div4?

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

    I think, it's just real div3

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

wrong answer using segment tree on g why? Here:107616153

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

    Seriously, how do you expect people to understand your solution just by hinting with some topic.

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

invented ! =discovered.

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

Supermagzzz's DIV 3 are easier as compared to vovuh's.

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

    bro more than 2700 people solved F. that's crazy

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

speedforces :(

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

I was not particularly quick today but still solved all problems and recorded a screencast with explanations

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

The difficulty from A-E is in decreasing order

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

Felt more like a Leetcode Contest without its final problem

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

how the answer for this A test is 3? 12

4 31 25 50 30 20 34 46 42 16 15 16

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

    4 8 16 31 25 50 30 20 34 46 42 21 16 15 16

    8, 6, 21 are added.

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

      someone can tell me why A solution https://codeforces.com/contest/1490/submission/107622033 this failing? what i should change to make it correct?

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

        One this test case

        1
12
4 31 25 50 30 20 34 46 42 16 15 16

        Your code will update the array 4 times as

        8 31 25 50 30 20 34 46 42 16 15 16 
16 31 25 50 30 20 34 46 42 16 15 16 
16 31 25 50 30 20 34 46 42 32 15 16 
16 31 25 50 30 20 34 46 42 32 30 16

        However, the last update isn't necessary. 32 isn't adjacent with 15, it is with 16. If you implemented to code to add the values instead of updating them. The list changes would be

        4 8 31 25 50 30 20 34 46 42 16 15 16
4 8 16 31 25 50 30 20 34 46 42 16 15 16
4 8 16 31 25 50 30 20 34 46 42 32 16 15 16
        → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't we solve problem f without using the concept of hashing? initially, I was thinking to declare an array of size 10^9. later realized that it would give any runtime error or memory limit exceed.

Is there any way other than hashing or map to solve f ?

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

    you can store the numbers in an array, sort it and then count how many there is for a given value but it's nlog n

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

    I solved it using Treemaps but Yes You can easily convert it to hashmap solution.

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

My solution for problem C outputs "NO" in my local device while outputs "YES" when I submit, for input 34. It tried with brackets also, but results are the same. It showing 'wrong answer for test 1'.

my solution is: https://codeforces.com/contest/1490/submission/107615310

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

Why this solution (for problem F) TLE on test 2. I think the time complexity is O(nlogn): https://codeforces.com/contest/1490/submission/107618301

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

    The time complexity is O(t * MAXN) where MAXN is 2e5, so you got TLE.

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

Does someone know a test where this solution for G might fail? : https://codeforces.com/contest/1490/submission/107619800

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

is all problem of div 3 is of equal points or C(poihnts)>B

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

Spent 35 minutes on this bug. fml.

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

What the heck is Unexpected verdict

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

    Inside the system there are solutions marked as correct solutions. If one of these solutions fail on a hack (maybe cause of WA, RTE, TLE, MLE, ...) then the hack is marked having "Unexpected verdict".

    When it happens, then just wait for a little while. Usually the problem setters fix it pretty quickly.

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

Problem C why my hacking verdict is 'Unexpected verdict'

Input :
100
1000000000000
1000000000000
1000000000000
1000000000000
1000000000000
...
→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe that solution has been hacked before.

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

Different problem statements, but very similar question to E

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

BinarySearchForces :3

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

Finally very good Div.**3** contest! All who are Div.2-level could solve almost all problems.

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

How to Solve G?

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

    if( prefix_sum[index_j] == xi ) ans = index_j — 1

    else if , for some positive integer k if prefix_sum[index_j] + k*prefix_sum[n] = xi or in other words prefix_sum[index_j] is congruent to x mod prefix_sum[n] then , ans = k*(xi-prefix_sum[index_j])/prefix_sum[index_j] + index_j-1; store prefix_sum and prefix_sum % prefix_sum[n] in map to query

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

    Create prefix sum $$$s_1,..,s_n$$$. The condition for which the result is -1 is $$$s_n\leq 0$$$ and $$$x > sm = max_{i=1..n}s_i$$$. Otherwise, if $$$x\leq sm$$$, find smallest index $$$i$$$ that $$$s_i\geq x$$$, the answer is $$$i-1$$$. For the last case where $$$x>sm$$$ and $$$s_n>0$$$. Let $$$p$$$ be the smallest value such that $$$p*s_n+sm \geq x$$$, the answer is $$$p*n + i'-1$$$ where $$$i'$$$ is the smallest value that $$$s_{i'} \geq x -p*s_n$$$. You can find $$$i$$$ by segment tree.

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

    link to my submission (obviously upsolved) without using Segment Tree. https://codeforces.com/contest/1490/submission/107636300

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

Can some one tell me where I am wrong in problem B.

Spoiler

for testis in range(int(input())): n = int(input()) l = list(map(int, input().split())) ll = []

for i in l:
    ll.append(i%3)

c0 = ll.count(0)
c1 = ll.count(1)
c2 = ll.count(2)
d = n//3
#print(c0,c1,c2)
#print(d)
m = max(c0,c1,c2)
if m==c0:
    ans = c0-d
    if c1+c0-d>d:
        ans = ans + c1 + c0 -d  - d
    else:
        ans = ans + 2*(d - c1-c0 +d)
elif m==c1:
    ans = c1-d
    if c2 + c1-d>d:
        ans = ans + c2 + c1 -d -d
    else:
        ans = ans + 2*(d - c2 -c1 +d)
else:
    ans = c2-d
    if c0 + c2 -d >d:
        ans =ans + c0 + c2 - d -d
    else:
        ans =ans + 2*(a - c0 - c2 +d)
print(ans)

I am just removing the extra part (present count — the equal number of c0,c1,c2 that shud be there) from maximuum of c0,c1,c2 and adding it to next one among them ..and then again removing the extra from that part and adding it to next part. But I ma getting WA on runtime error on tc 2. ples help Thanks in advance.

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

    Testcase where your code would fail:

    6 3 3 3 2 2 2

    Answer is 2, but your code would give 0.

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

      how is the answer 2 ?

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

      How is it two? One two has to be increased twice and one 3 has to be increase once. So shouldn't it be 3?

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

        Sorry my bad, yes it should be 3 not 2.

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

      dude my code is also giving answer 3, on this test case. I am getting runtime error and I am not getting whats the issue. ples help

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

Easy round, but I found my mistake on G 3 minutes before the end :(

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

Bruteforces!!

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

Those who have just started reading Binary Search , they must try to solve problems C , E , G. All 3 of them decent problems to start with.

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

107615789 why this code didn't get tle ?

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

if(c2>n/3) { c0=c0+c2-n/3; cout<<(c2-n/3)+abs(c0-n/3)<<"\n"; } else { c1=c1-(n/3-c2); cout<<(n/3-c2)+abs(c1-n/3)<<"\n"; }

//why this logic is wrong in question B

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

Why this logic is wrong in question B ~~~~~ if(c2>n/3) { c0=c0+c2-n/3; cout<<(c2-n/3)+abs(c0-n/3)<<"\n"; } else { c1=c1-(n/3-c2); cout<<(n/3-c2)+abs(c1-n/3)<<"\n"; } ~~~~~

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it 
if(c2>n/3)
	  {
	  	c0=c0+c2-n/3;
	  	cout<<(c2-n/3)+abs(c0-n/3)<<"\n";
	  }
	  else
	  {
	  	c1=c1-(n/3-c2);
	  	cout<<(n/3-c2)+abs(c1-n/3)<<"\n";
	  }

Why this approach is wrong in B

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

https://youtu.be/lEOz-It922w

Video solution for A. Dense Array

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

Here’s my attempt to screencast this Div3 contest, where I have explained the solutions to the problems later. It’s my first ever screencast, and any suggestions would be helpful.

https://www.youtube.com/watch?v=fbv5NKA9t9c

I hope you like it.

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

Never solved 6 problems before. Thank you div3, finally I am able to achieve.

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

Is this round rated ? as it is showing in unrated contest in my performance graph in profile section

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

Unfortunately, D was much easier than the first three problems. T_T

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

G is a harder version of this problem

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

I uploaded a screencast: https://youtu.be/InbURHKu_Lk

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

When do we get registered the contest in our profile?

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

Is anyone here who solved F using Binary or ternary search?

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

    yeah, using lower bound and upper bound Solution Link

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

      I liked your approach, not sure if it's really binary search. Actually, I was expecting something similar to this:

      Code

      This code gives WA at case 3.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

    Professor

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

    My handle is RohitS.Singh . I did not know that submitting same code from multiple accounts is not accepted , also I am a newbie so just wanted to check my solution before submitting through my main account. I was unaware of rules so created another account whose handle is dar_k_horse and submitted the solution there before submitting through my main handle. I recently got a mail from codeforces about the same . I accept my mistake and as I am now aware of the rules would never repeat the same . I am not a cheater.

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

Why unordered map gets tle in F?

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

    Because of anti-hash test. In these kind of tests unordered_map takes it's worst case complexity of O(n). You can check this blog on unordered_map.

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

      Thanks a lot for sharing this, TIL. I was completely stumped as to why unordered map didn't work!

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

problem (C + D) link : https://www.youtube.com/watch?v=3_qtawn7zHY problem(A + B) link : https://www.youtube.com/watch?v=J3u3UAUHrjo

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

How to approach problem F if instead of "either zero or C times" we consider "multiple of C times" in the problem statement? (I misread it during the contest).

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

    You can take frequency of frequency of elements as count. Each time just check whether number of elements of that particular frequency * frequency of frequency of elements is max.

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

      I am not sure if you understood what i asked. Or can you please elaborate your approach as to how is this possible without modulo arithmetics by just using frequencies.

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

        F solution. I hope my solution is much clearer. I have just used 2 maps to store frequency of elements and frequency of frequency. The product of this is the number of elements we can have include in our array.

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

          I asked how to solve an alternate version of F viz. "how to solve if we can take all frequencies in a multiple of C times instead of just C times or 0 times", not this! Leave it. Thanks.

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

My F got accepted in 100 ms but 2000 ms after hacking phase. Collision between values is the reason for this because of hash function?

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

    Yeah sucks, same here.

    The one with unordered_map fails but with map.

    I purposefully used unordered_map thought it would be faster.

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

good contest

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

My handle is RohitS.Singh . I did not know that submitting same code from multiple accounts is not accepted , also I am a newbie so just wanted to check my solution before submitting through my main account. I was unaware of rules so created another account whose handle is dar_k_horse and submitted the solution there before submitting through my main handle. I recently got a mail from codeforces about the same . I accept my mistake and as I am now aware of the rules would never repeat the same .

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

Problem F — Equalize the Array

"you can consider only unique values of C (there are no more than O(n*√n)), and get a solution in O(n*√n)"

I used this approach mentioned in the editorial during the contest and get a TLE in test case 12.

Here is my submission:107609642

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

Rating got changed again ? Something happened?

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

As for my ranking in this contest,when I found my name in the "common standings",it shows that I got rk1947,but when I chose "Friends standings",I got rk2130,and finally the increase of my ratings is based on the rk2130......Though I'm not so focused on the ratings itself,I wondered how this happened. :D

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

problem d by segment tree time_complexity O(T*NlogN)

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

Hi, Guys! I am stucked on #F on 12 test with time limit. No ideas to fix it. May u help, please?

int t;
    cin >> t;

    while (t--)
    {
        ll n;
        cin >> n;
        vector<ll> a(n);
        unordered_map<ll, ll> m;
        for (auto& x : a)
        {
            cin >> x;
            ++m[x];
        }

        vector<ll> cnts;
        ll sum = 0;
        ll cnts_size = 0;
        for (auto x : m)
        {
            cnts.push_back(x.second);

            sum += x.second;
            ++cnts_size;
        }

        //countSort(cnts);
        sort(cnts.begin(), cnts.end());

        ll c_val = sum - cnts_size *cnts[0];
      
        for (ll i = 1; i < cnts_size; ++i)
        {
       
            if (cnts[i] == cnts[i - 1]) continue;
            ll val = sum - (cnts_size - i) * cnts[i];
            c_val = min(val, c_val);

        } 

        cout << c_val << endl;
        
    }
→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why were solutions rejudged on uphacks?

→ Reply