Блог пользователя ScarletS

Автор ScarletS, 3 года назад, По-английски

Hey there Codeforces!

flamestorm and I are glad to invite you to our first-ever Codeforces round, Codeforces Round 742 (Div. 2), which will be held on 05.09.2021 17:35 (Московское время). This round will be rated for participants with rating lower than 2100.

Special shoutouts to:

You will have 2 hours to work on (and solve!) 6 problems. At most one of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round! You are highly encouraged to read all the problems ;).

UPD: The score distribution is 500 — 1000 — 1500 — 1750 — 2250 — 2750.

Good luck, and see you on the scoreboard!

UPD: Editorial is out!

UPD: Congrats to the winners!

Div. 2 (the only 5 contestants to solve the whole set!):

  1. shengtongtong

  2. zihouzhong

  3. NOOB228

  4. definition_win

  5. TearsFreeze

Div. 1 + 2:

  1. SSRS_

  2. dlalswp25

  3. LayCurse

  4. neal

  5. Vercingetorix

We hope you enjoyed the round. See you soon!

  • Проголосовать: нравится
  • +967
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +130 Проголосовать: не нравится

As a tester, I like the tags of this announcement just like the problems.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Really excited for this one!

»
3 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

not because he contributed anything to the round, but because he would annoy me for months if I didn't mention him here
Lol

»
3 года назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

surang fan club rise up !

»
3 года назад, # |
  Проголосовать: нравится +104 Проголосовать: не нравится

ScarletS you had one job!

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +89 Проголосовать: не нравится

As a tester, did you know that if you don't upvote an 'as a tester' comment you will get negative delta? I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

Me having to get up at 12:35 am (midnight) till 2:35 am because of bad time zone differences.

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

I know that this will be a high quality round.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

upvoting this blog and giving me contribution Authors and testers always asking for contribution, reminds me of mr ditkovich from spiderman 2 who always used to ask for rent. https://youtu.be/usIJYbv_gXw

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Unban from server

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

By the way, who is saarang? @saarang

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Pupil missed the large range of testers. Sad life :(

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

time to upsolve this

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

As a participant, I hope this would be a great contest with 6/6 wonderful problems

»
3 года назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

    We all deserve low contribution because of the importance of

    this in the Codeforces community

    Don't you see that high-rated people have higher contribution? When your rating is high enough,people will start to give you likes. So dude,don't care about contribution. Care about how to get high rating.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -24 Проголосовать: не нравится

      I can't agree with you more , I'm trying to improve my programming ability , and this link is my best friend's music , i want to make it more visible but I post it in last contest's blog and get 50 downvote...

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +36 Проголосовать: не нравится

        Dude, why are you posting music in a contest blog? No doubt you will get many downvotes. You should post it in your own blog.

    • »
      »
      »
      19 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Is my rating high enough to get high contribution? No

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

As a Newbie, I am gonna take ScarletS 's graph as a motivation

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Has there ever been a tester that criticized a contest(before the round)?

»
3 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

As a tester, I enjoyed being in the same team as ScarletS in hashcode this year!

He loves his team name

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I will become Pupil after 3 days. This is so exhilarating...

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Don't be so sure. Saying from experience

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      LOL! I show your rating graph. It's nearly the same as mine.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Exactly, At one moment you are expecting pupil the next moment you get -126.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        Spoiler

        `

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I can't play on Sunday night, so have mercy on me. Only 6 points short.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, the day the contest starts is my 15th birthday, so I hope I could get a high ranking as my birthday present :)

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Ready to become newbie again

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

支持此比赛!

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

I have a question. I am a Chinese middle school student. But I started school on Monday morning, and I couldn’t participate in the Sunday night game. Because of the time difference, it only started after ten o'clock in the evening, and I needed to sleep. But what should I do if I want to participate in the competition?

»
3 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

As the official video editorialist of the round, subscribe to my channel

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I really hope to solve problem C, but it might be too difficult

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are specialist and can't solve c ??

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    :)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Sir kindly once have a look at it. These idiots are downvoting my contribution. My only intention was to stop such things and make Codeforces a healthy place in whatever way I can.


      I feel disheartened to see these things going around us and sharing with all of you what I came across recently. I was trying to solve this B problem and after devoting 1 hour approx I decided to log out my account as I didn't get it logic. I searched on the youtube the problem name just to check if anyone is not posting solutions during the contest like the way people post video solutions during codechef long challenges.

      It did not used to happen earlier but recently it started happen and I came this issue several times but I just moved on then. This time I could not resist myself from not sharing this, that these kind of folks are trying to ruin the whole environment of the community by doing such cheap acts just to get views and subscribers.

      Kindly take actions regarding the same. This needs to be stopped.

      Sharing the blog link and the youtube channel link. Please do have a look. https://techtogether.live/codeforces-round-742-mexor-mixup-solution/ https://www.youtube.com/watch?v=XlHgagQjUIc

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Bro just chill, these peeps would go nowhere, and more importantly these peeps would majorly effect greens and lower blues... So, work hard go way beyond their ability and you are rocking and moreover many blogs have already been posted and many people at top level know about this and would definitely do something... Till then, just scratch your brain and enjoy!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

looking fwd to this chinese round .. will surely become rated this time :} Also i wanna congratulate all chinese people for their nation's outstanding performance in paralympics , love from north korea

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All set to become newbie again. Here we go again.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I'm gonna do good in this contest.

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

There might be a game theory problem, guessed from the alice and bob tag :)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what the hack is MEX and link is no opening too

»
3 года назад, # |
  Проголосовать: нравится +91 Проголосовать: не нравится

digitforces

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Problems. Specially Problem E.

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

so i had to lose around 400 points because i didn't know x^b==a and (x^b)==a aren't the same (-_-) if you know you know

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Good contest! But I think that there is so many math problems, like B,C ans D :(

Now I have a chance to improve my math skills.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I know that I am dumb but daaaamn question C is tough.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice contest, thank you ScarletS

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I spent 45 mins cause curr_xor^b is different from ((curr_xor)^(b)) (-_-)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i dont get it....how is it different...can u please share any resources?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Its not different , its just that:

      When you do (a^b == c) the compiler actually does a^ (b==c) because of the precedence of operators. so (a)^(b) == c is basically (a^b) == c which is the correct version

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If I fail system tests I'm going to kill my self and it's your fault, I'm finally getting to CM !!!

»
3 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

I think the difficulty ranking is:

A<B<E<D<C<F.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Overwhelmed by sadness

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

What's the solution for E?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Segment tree where for each node we store the total number of good subarrays, the lengths of the longest prefix that is good and the longest suffix that is good, and the first value and the last value of the interval

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Came up with the solution for E after a glance but it seemed that my brain is "voidily" than any black holes in the whole universe for C and D.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Nice contest, finally a Div.2 B with normal difficulty.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

If my F passes, it will be my first time reaching Master :D

But I think my F solution can fail, it looks too simple. It is only bipartite matching.

  • If a marked cell has one or three adjacent unmarked cells, there is no solution
  • If a marked cell has two unmarked cells connect them with an edge
  • If a marked cell has four unmarked cells connect the top and left cell with an edge, as well as the bottom and right cell with an edge.
  • Then do assignment of colors with bipartite matching.
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I came up with the same idea when I saw problem F, but I don't know how to proof its correctness and I don't think the solution is right......

    So why is it correct......it seems that the solution passed the system test.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      During the contest, I tried to construct a counterexample to my approach by I could not. Probably I should have submitted my solution earlier.

      The proof of correctness is explained in the editorial.

      But my D failed systests, so I guess no Masters for me :/

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem C ?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    note that if you build 2 numbers:

    1. number from odd positions = x

    2. number from even positions = y

    then, those numbers are correctly computed during the process. so the answer will be: (x + 1) * (y + 1) — 2. (because those cases for each number are disjoint)

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Let poss(x) = number of ordered pairs (a,b) such that 0 <= a,b <= 9 and a + b = x. You should with some casework or bruteforce. Also let dp[i][j][k] be the number of ways to fix the ith digit to the last digit with carry j for i-2 and carry k for i-1.

    We can make the recurrence dp[i][j][k] = dp[i+1][k][0]*poss(s[i] + j*10) + dp[i+1][k][1]*poss(s[i] + j*10- 1), and with it, the answer will be dp[0][0][0]-2.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I applied bitmasks to calculate for which positions get a carry and which do not.

»
3 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

I think maybe problem E is too easy for a div2E.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C is a good idea!

»
3 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

ScarletS I am sorry to say that, but the problems C and D are of very questionable quality, as for my taste. I even know some people (from post-contest discussions) who would ask you to stop creating problems (in a very cf-toxic manner). Instead, I want to ask you to keep going. I believe in you, and hope that your next contest will be better!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    The only toxic things here are the problems.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +63 Проголосовать: не нравится

    Funny that you say that, because IMO C is one of the most genius easy problems I have seen in a while.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -41 Проголосовать: не нравится

      Same for D. Only some observation in D and an easy DP in C.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Well, there will always be some unhappy people. For example, I don't like digit-related problems in general, so my opinion is clearly biased. What I was saying is "don't take all comments personally, even if they come from div 1 users"

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me what's wrong with my code, problem C. I used brute force approach

code
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    You should take one test, output pairs you've found, compare them to given solution in problem statement and look into your logic — why they don't match. It's called debugging, this is part of problem solving you should get used to.

»
3 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

I think it was probably the worst round I've ever in.

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

swap(C,E)

»
3 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

solved A,B under 30 mins and failed to implement C for 1 and a half an hour :(

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Should've seen E first, spent 1 hour implementing D.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved $$$B$$$ in $$$19$$$ minutes, $$$C$$$ in $$$1$$$ hour and $$$13$$$ minutes, and $$$E$$$ in $$$16$$$ minutes. I'm still shocked :)

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Where is the interactive problem?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Test case 5 killed me in D :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why already system testing, but I still have B on "Pretests passed"?

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Last 10 minutes brought 200 + Successful submissions on both D and E , amazing.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

ready to be specialist again :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When solving problem B, spent too much time thinking that $$$a$$$ was supposed to be the smallest non-present number in the array among those that are positive and got the whole contest derailed because of this. After a long debugging session wondered why [1, 10001] was not a correct answer for the a=2, b=10000 testcase and then checked the problem statement again.

Now I wonder what was the purpose of the a >= 1 constraint in the first place? The problem would be still solvable if $$$a$$$ was allowed to be 0. It's entirely my fault, but reading comprehension played a major role here and if this was the contest authors' intention, then they surely achieved their goal.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Missed an AC in E by 3 minutes , Sad life :(

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I enjoyed this contest.

Thank you for the nice problems.

»
3 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

»
3 года назад, # |
Rev. 10   Проголосовать: нравится 0 Проголосовать: не нравится

@below oh i must have missed it when I read it thanks

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually no. I think it's better to read Codeforces instructions to avoid downvotes

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thx

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I didn't like C and D, but F was pretty nice.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

C: just another standard digit dp problem.

E: just another standard segment tree problem.

Downvoted.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

AliceForces!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone check why my submission for problem D failed? I just did the carrying one by one starting from the rightmost digit of $$$s$$$.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

One of the best problem sets in recent times. Thanks ScarletS and flamestorm for the contest! :)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think I have wrote a wrong F but it passed !

Compare submission 127972613 with submission 127978516 , I think that I only change the left and right when a 'X' has 4 '.' neighbors .

I think I can be Up Hacked.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Problem C is beautiful. I love it.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A: U->D D->U L,R unchanged B: Preprocess the exclusive OR of 0~n-1 and judge with m

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please update problem ratings.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi regarding Question C of this round (742) ,the test case number 3 where input of n is 8 ,the output is given as 7 whereas it should be 9 . What I mean is that to make 8 according to question we have following pairs : (`1 ,7),(7 ,1) ,(2 ,6),(6 ,2)(4 ,4),(5,3),(3 ,5) ,(8 ,0),(0,8).This adds to total of 9 .Can anyone tell if its right . Here is the question link : **https://codeforces.com/contest/1567/problems** Thank you for your time .

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Notice that the statement asks for the number of ordered pairs of positive integers, so $$$(0,8)$$$ and $$$(8,0)$$$ don't count, as $$$0$$$ is not positive.