Supermagzzz's blog

Codeforces Round #710 (Div. 3)
By Supermagzzz, 4 years ago, translation, In English

Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #710 (Div. 3) will start at Mar/25/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 darkkcyan, bugdone, harlequen, iankury, bfs.07, songsinger, infinitepro, sodafago, Gassa, Rox, sharepoLOVEDDD for testing this round.

Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!

</almost-copy-pasted-part>

UDP: Editorial is ready

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

Comments Comments (128)
| Write comment?
»
4 years ago, # |
  Vote: I like it -120 Vote: I do not like it

Finally another Div 3! I was half expecting to go a month without one... Wishing everyone an enjoyable contest and positive delta!

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

Always so exciting to have these Div 3's in my life!

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

Isn't it risky to have a round without testers? Are there are some hidden testers for Div-3 rounds :P?

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

Can't wait for my first Div3 Round....

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

I'm waiting this contest since days ... it's best for me ^_^ We hope that are no any mistakes during the contest ... Thanks for your efforts !!

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

Wishing you all A big positive delta!!

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

    U should have wished for positive upvotes in comment section.

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

wow, there's no comments with more likes than dislikes.

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

Are you saying no matter what I write I will still get downvotes

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

![ ](11)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -63 Vote: I do not like it

َ

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -56 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -47 Vote: I do not like it

Will any comment here get upvoted?

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

After the div2 brutal round hopefully this contest will serve as a motivation to continue CP! haha

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

plot twist: this comment is gonna get downvoted

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

Guys let me compete with Monogon for 1 rank in contribution, I need your help to achieve that goal!!!

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

    Upvoted. I think you have a lot of work to do. You made a few mistakes with this comment, such as not posting it immediately after the announcement comes out. Also, in this comment you state that you have a particular goal and people should upvote you to help you reach that goal. Unfortunately, this will isolate people who are willing to upvote you for different reasons. So, you should not state any reasons or argument for why the reader should upvote you. Instead, just directly command them.

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

Why all comments are getting downVote?

→ Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Spoiler
→ Reply
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it
Spoiler
→ Reply
»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

We Want vovuh in upcoming div3 rounds :P

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

Is it rated?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    I just asked a simple question. Why downvote me?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      Because you don't like reading blog carefully, 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
»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Downvote

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

I was gonna post a meme but I changed my mind

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

BanjoByster who?

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

One who dislike this post doesn’t love his/her mother!!

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

    One who dislike this post doesn’t love his/her mother!!

    Why go on mother, you could have gone on anything like keyboard, mouse, CP, electricity, Edison, etc. but don't comment such to just gain some upvotes, PLEASE!!!

    → Reply
»
4 years ago, # |
← Rev. 14   Vote: I like it -26 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

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

plz downvote me, i'd like to have anticonributiuon on this acc

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

¿Quieres?

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

.

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

This is my first comment.Hoping to become pupil. P.S. Don't Downvote

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

I am not scared of anyone of you......... >.<

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

The round starts in 20 mins, make sure you registered. I wish everyone participating good luck and a fun round !

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

please don't downvote

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

good luck everyone! hope to get rating increase

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it

my solution to problem E: https://youtu.be/efrkmxiEDNc
code: https://codeforces.net/contest/1506/submission/110998366

nevermind i think i missed the joke.

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

    Comeon Man, this isn't fair... Your video was posted way before the contest was gonna end... Atleast could have waited for the contest to end! Your videos must be source of logic and thinking for upcoming coders, not a way to help them seek an easier way to just copy and paste

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      no it wasn't. it was supposed to premiere at 10:15PM IST. I made it live at 10:05PM IST exactly when the contest got over. do you seriously think I would do something like this for a few hundred views?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -39 Vote: I do not like it

        I don't have a personal grudge here man... Just that someone has commented there exactly 15 minutes ago... Meaning at 10:01(+5:30). This would mean that your video got uploaded before 10:01 itself

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          if I premiere a video on youtube, the thumbnail will be visible way before it goes live. people are allowed to comment, like/dislike but not watch before the premiere begins.

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

Almost all solutions are aviable online : C: https://www.geeksforgeeks.org/longest-common-substring-dp-29/ G: https://www.geeksforgeeks.org/lexicographically-smallest-string-formed-by-removing-duplicates/ @MikeMirzayanov It should be made unrated cause it is not fair to those who are giving.

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

How to solve problem D?? but nice contest though loved it:)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    If some number occurs x > floor(n/2) times, then, it is 2x — n. Else, its 0 or 1 depending on the length of the array

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

I was just going to submit D and contest finished :-( :sadpuppynoises:

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I wanna know abt D... It took so much brain power and idk why but i feel it's gonna be damn easy

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

      Just use priority queue keeping frequency of nos...Run a loop untill its size is strictly greater than 1

      In loop reduce frequency of first two nos and insert each one iff its frequency is still greater than 0.

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

      firstly, sorry for my english

      let max be the maximum number of times the number occurs. if max>n-max, then the answer is max — (n-max) tk we can delete this number with all the others, but we can't delete it with ourselves. otherwise, the answer is n%2, because we can delete the remaining numbers up to the number of our number, and then delete them with our number. well, if n%2 == 0, then we can delete everything, otherwise everything is clear

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why does my implementation using sets fail

https://codeforces.net/contest/1506/submission/111057558

Afaik the time complexity must be O(N*log_2(N))

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what the heck happened to the comment section?!

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

Thanks for the round! Here's my screencast (HD versions forthcoming): https://www.youtube.com/watch?v=s7owI7Uo2rk

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

Is there any difference between :
auto itr = st.lower_bound(val); and
auto itr = lower_bound(st.begin(),st.end(),val);
One solution gave TLE and the other passed and the only difference is listed above, ACCEPTED and TLE

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

    yes for set its the right way -> st.lower_bound(val);
    and it totally wrong ->auto itr = lower_bound(st.begin(),st.end(),val);

    i once faced that.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Okay I understood that it is wrong, that is why it must have given TLE, but what is the exact difference between them or their time complexities

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

        In lower_bound(set.begin(), set.end(), val), std::set doesn't have random-access iterators (think of them similar to array indexing), so the time complexity is linear. With set.lower_bound(val), std::set has that lower_bound built in, so it's much faster, logarithmic time complexity.

        Edit: Just realized that b23v said pretty much the same thing :/

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

I see too many downvotes in this blog post. I'll investigate it in few days. Sorry, no time to do it right now. But I'll try to revert unfair votes and prevent such behaviour in the future.

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

    Hey, MikeMirzayanov Just wanted to bring before you plagrism of two users

    cyborg_7459 and cyborg7458

    Both of these Users don't know whether same persons or different has submitted solution of Problem A and B with minor Changes. Please Do look at their submission. Even their template is same. Since Even submitting Solutions from alternate account is clear voilation of policy please Review their submission. Maybe they would be same person just submitting solution from one account to confirm its correctness and escape penalty, which is voilation of Rule and needed to be punished if really found guilty.

    Their Submissions:

    Problem A: 110996666 and 111008607

    Problem B: 111007814 and 111006918

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it -34 Vote: I do not like it

      MikeMirzayanov plag_report Yeah my bad, but I have an explanation for that which I think might be justified. Since the past 3 contests I've been facing issues with the CodeForces server being down, as might be evident from the bad results of my past 2 contests as well as the fact that I could not give the Division 2 immediately preceding today's contest. Thus, to prevent a negative effect on my rating I started today's contest with my alternate account but switched back to my original one after facing no issues for about half an hour.

      I had no idea that submitting from 2 accounts is also a violation of Rule, and I thought that since I could easily prove the 2 accounts to be mine, I would be able to show that the code is completely original in case someone said otherwise.

      I can assure you that it wasn't a case of trying to avoid a penalty because I did get penalties in my D and E as well. If I had been trying to avoid penalties by testing solutions with my alt account, then I obviously wouldn't have stopped that for the harder problems

      Moreover, I submitted the solution for A from my main account 15 minutes later, which covers up the 1 penalty advantage that I would've received in problem B

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        Still, you should have read the rules. They are right before registering into the contest. And also, don't you think it is unfair to whenever you have a good performance in your alt to you switch back to your main? This way it would be very easy to farm rating, just create an alt where you compete normally, and if you have a good performance switch back to your main account. This attitude shouldn't be tolerated since it is unfair to other participants. There is no justification to this, it is obviously unfair and violates the rules.

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

    I wish that could be prevented but I wonder how especially that deciding if a comment should be downvoted or not is an opinion

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

is CF oke ?? may be some bug for downvoting . mesanu sir do something

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

Almost all solutions are aviable online : 1. C: https://www.geeksforgeeks.org/longest-common-substring-dp-29/ 2. G: https://www.geeksforgeeks.org/lexicographically-smallest-string-formed-by-removing-duplicates/ - - @MikeMirzayanov It should be made unrated cause it is not fair to those who are giving.

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

    It wasn't phrased as "find longest common substring" so the task was really figuring out that lcs was optimal. And constraints are low enough to brute force.

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

Garbage Contest and Discussion!

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

Is there any specific reason why B is always tougher than C on CF contests ?

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

    There is no specific reason because it isn't true.

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

can someone help me understand why my code is giving tle hacking, i am not able to find the test case in which it can give tle.

https://codeforces.net/contest/1506/submission/111050778

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you miss B because you type k instead of j.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone tell me how my code to E 111026430 being hacked... :(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    		F(int, i, 1, cnt) {
			x = a[maxi[i]];
			F(int, j, maxi[i] + 1, maxi[i + 1] - 1) {
				while(vis[x]) x--;
				ans2[j] = x, vis[x] = 1;
			}
		}

    see you are deccrementing x and then finding the max avaiable number there is to fill. maybe this is causing tl in some very specific testcase.

    for example lets read

    N=8

    5 5 6 6 7 7 8 8

    answer is 5 4 6 3 7 2 8 1

    now see to get to 4 at index 1 you decremented x 1 time

    for index 3 you decremented 3 times

    for index 5 you decremented 5 times

    for index 7 you decremented 7 times

    total complexty is 1 + 3 + 5 + 7 + 9 + 11 + ... n (sum of all odds upto n). this looks like n^2. and exactly where tl is coming from.

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

I am black. If u downvote me — u are racist.

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

My computer was just used by others.I'm sorry to say rev.1's words

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

    Yes,I used his computer because of this easy round.

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

      He who fights with monsters should look to it that he himself does not become a monster. And if you gaze long into an abyss, the abyss also gazes into you.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I get TLE in question D upon using unordered_map instead of map ! Isn't unordered_map is implemented using a BST which makes me think it should be faster than map ?

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

    Same I too got TLE on 8th case in problem D this is because the value of a[i] can be 1e9 if in any case there are more values greater than 1e8 then it will form chain structures to hold key-value pair so instead of O(1) per query the amortised complexity may be O(n) resulting in O(n^2) overall. So better to use map which has constant factor of O(log(n)) it won't hurt you!

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hi, it was my first contest and I solved 3 questions. will I get a rating, if yes when will the rating changes be announced?

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

    will be updated soon! have patience.

    and congrats for positive delta!

    → Reply
»
4 years ago, # |
  Vote: I like it +6 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
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hello guys!!

i am getting a tle for my solution of problem D(Epic Transformation)

Can anyone pls look at my code and help me correct it??

My Code

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

    endl is too slow.

    It is bad comment. I tested changing endl to '\n' but it is not fast enough.

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

    unordered_map => map

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

MikeMirzayanov wrote 2 yr. ago (https://codeforces.net/blog/entry/65383):

Yesterday slappy advised me to stop writing problems. I will not listen to his advice and will not stop coming up with new problems.

This was another good Div.3 round! (After https://codeforces.net/contest/1490).

So thanks for authors for their problems, and keep composing!

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

in problem d i used unordered map and time limit got exceeded but replacing unordered map by map ans is accepted how is it even possible .111012090 time limit exceeded 111111133 accepted

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

For question B what will be the output for-

11 2

....*.....*

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

G was an easier version of https://ncna19.kattis.com/problems/earlyorders

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution was skipped even though I neither copied nor showed anyone my solution.How can I prove that I did not copy?This is really disgusting.This contest was unrated for me but what if it was rated.Please do review this. My D problem matched with someone I neither know and neither follow

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

    was not expecting you to cheat :(

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

      I didn't

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

        no one submission of d skip without matching of same code nd its not A its d almost all with honest submission have different code,,,Anyways please dont give contest in couple thing,I hope u will be honest from nect tym

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution was skipped for this contest even though I neither copied nor showed anyone my solution.How can I prove that I did not copy?This is really disgusting.This contest was unrated for me but what if it was rated.Please do review this. My D problem matched with someone I neither know and neither follow

→ Reply