dario2994's blog

By dario2994, 4 months ago, In English

Hi!

On Oct/10/2020 17:50 (Moscow time) we will host Codeforces Global Round 11.

This is the fifth round of the 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round are as follows:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Problems for this round are set by me. Thanks a lot to the coordinator antontrygubO_o, to the testers dacin21, Giada, Omkar, DimmyT, _cherry_, oolimry, gege, Prakash11, Tlatoani, growup974, nvmdava, stack_overflows, dorijanlendvaj, and to MikeMirzayanov for the Codeforces and Polygon platforms.

The round will have 8 problems and will last 180 minutes.

The (unusual) scoring distribution is: 500-750-1000-1000-1500-2250-2250-4500.

Why such a scoring distribution?

In codeforces rounds there is a minimum possible score and a maximum one. Moreover, to spice up the strategies for top contestants, I wanted to have F+G=H. Satisfying these constraints is nontrivial and has generated this scoring distribution.

The low scores for problems B-C-D-E-F-G should not suggest that they are easier than usual.

I hope you will have fun solving the problems!

UPD: The round is postponed by 15 minutes because just before the round there will be a 10-minutes-long unrated testing round. Considering the recent Codeforces downtime, this is a measure to make sure that there will not be technical issues during the real round.

UPD2: There were no technical issues during the testing round, hence the real round will happen. Good luck and see you in the scoreboard!

UPD3: I hope you liked the problems, here is the editorial.

UPD4: Congratulations to the winners!

  1. Benq
  2. yosupo
  3. ksun48
  4. Um_nik
  5. ecnerwala
  6. sunset
  7. maroonrk
  8. zscoder
  9. SirShokoladina
  10. gamegame

UPD5: And congratulation to Petr who upsolved H before the editorial was posted! You made me happy!

Announcement of Codeforces Global Round 11
 
 
 
 
  • Vote: I like it
  • +1025
  • Vote: I do not like it

»
3 months ago, # |
Rev. 4   Vote: I like it -164 Vote: I do not like it

"The low scores for problems B-C-D-E-F-G should not suggest that they are easier than usual."
but i hope 1000 pointer C,D is not as hard as recent Div2 675 C and if they are, then honestly they deserve more points.
edit: I want atleast 500 downvotes now.

»
3 months ago, # |
Rev. 2   Vote: I like it +269 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it +98 Vote: I do not like it

as a tester, I want contribution

PS

This is the first round, I ever tested !

Good Luck !!

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

    as a participant I also want contribution.

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

    We will give you a contribution after our solutions will not fail in the system test.

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

    how did you become a tester? can you tell me? if there is a link that refers to becoming a tester of the round I would like to know thanks

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

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

Solving F+G+H, exactly

»
3 months ago, # |
  Vote: I like it -132 Vote: I do not like it

Sometimes really annoying.

»
3 months ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

Oh please, then make score of every problems twice. What if some contestant gets C/D but not B and gets bad position due to closer score distribution. And in combined rounds, its common to get tougher B(at least for me)

»
3 months ago, # |
  Vote: I like it -45 Vote: I do not like it

This Comment Section is Shit.

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

....so basically if LGMs can solve H they will participate, else skip the round?

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

    ... especially if they are not running for top positions in the 6-round series

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

    I hope not! I hope they will participate to have fun, not (only) for the rating.

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

Note the duration -- 3 hours!

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

As a tester, I am very lucky that no one will see how bad I was in this round.

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

dario2994 "500-750-1000-1000-1500-2250-2250-4500", Can we expect C and D to be equal in difficulty and same with F and G( though I don't care about F and G, since I have never solved that many problems in a contest )

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

    Yes.

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

    maybe you need to care about F and G to solve them

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

      Yes, I am focusing on improving my advanced data structures and upsolving 2000+ scored problems. Lets hope soon I would be able to solve them and increase my speed for solving Div2D as my next goal is become master.

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

      can't believe I never thought of this. I'll just make sure I care about H this weekend. see y'all in GM!

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

        update: 2397, but if I solved H, then I think I would have made it

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

As a tester I want to say that the problems are really interesting. Wishing All of you big positive deltas!!!!

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

F, on Sunday my rating will go down

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

Tshirt = H

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

We know who will win)

»
3 months ago, # |
  Vote: I like it -66 Vote: I do not like it

Adhoc shit incoming

»
3 months ago, # |
  Vote: I like it -40 Vote: I do not like it

wiil B-G will harder than as usual???at least B & C?

»
3 months ago, # |
  Vote: I like it -28 Vote: I do not like it

I hope pretests are not weak, otherwise every successful/unsuccessful hack will be worth a lot of rating points.

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

(120996911_3404290582998045_8389644735048710731_n.jpg)

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

The low scores for problems B-C-D-E-F-G should not suggest that they are easier than usual.

If it doesn't mean B-C-D-E-F-G will be easier, then why the score distribution is like this? Someone could solve A, C, D, and most probably would be behind a guy who only solved A, B, C. Here B & D are playing the deciding factor. How even this is fair if B & D has a normal round's difficulty? I am sorry, but I couldn't get the explanation for the unusual distribution.

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

    you will be downvoted for raising voice towards this stupid score distribution like me

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

Are you ok Codeforces..?

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

    Codeforces-Chan seems to be ok now ;))

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

      I don't think Codeforces is completely fine... Problem in loading my own profile

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

Oh my god, what happened?

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I think codeforces contest is hijacked by some top coders.Other will not get anything else rating drop LOL

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

there is no logic in making the difference between some problem's score and some other harder problem's score too little just to make F+G=H

»
3 months ago, # |
Rev. 8   Vote: I like it +44 Vote: I do not like it

oops,after the contest end about 7 hrs there is a big competition called CSP-S1 which is important to Chinese OIers,so many Chinese student(include me) may not take part in it.

upd :

cf contest : 22:35GMT+8 ~ 01:35GMT+8

CSP-S1 : 09:30GMT+8 ~ 11:30GMT+8

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

    nobody cares about Chinese competitions, why are you always complaining about CF contest start time

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

      I am not complaining,but I'm quite sad because I love global rounds' nice problems

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

      nobody cares about you, why are you always complaining about other people

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

        nobody cares about you, why are you always complaining about other people

»
3 months ago, # |
  Vote: I like it -92 Vote: I do not like it

Small but major correction.

points he gets ...

should be

points he or she gets OR points they get ...

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

Your Atcoder round was great! Waiting for interesting problems here as well.

Maybe F+G=H makes sense for the top but this distribution will make the round worse for the remaining 99% of participants. What about loosening the condition and making it e.g. 3000-3000-4500 for three last problems, along with some adjustments for earlier problems. Also, isn't the score of 250 possible too? And please remember about adjusting points drop/drain for a longer round.

I will go live just after the round and explain my solutions to whatever problems I manage to solve https://www.twitch.tv/errichto

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

    i don't understand how this will make the round worse for remaining 99% participants.

    i doesn't seems like they care about H anyway.

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

      They indeed don't care about H so the scoring becomes 500-750-1000-1000-1500-2250-2250. This flat scoring discourages solving problems out of order. And you will get a similar number of points for C and G because of time penalty so better not fail C!

      Notice that the average step in 500-1000-1500-2000-2500 round is 500 points (or around x1.5 ratio) while in this round the step will be 291.66 (or ratio $$$(2250/500)^{1/6} = 1.28$$$). More problems and yet smaller difficulty range, hurray.

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

      seems like even the top 1% of players also didn't care about H.

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

    Since I see many comments concerned about the score distribution and how it might ruin the contest for many contestants, let me explain. First, three remarks:

    • No, I was not allowed to give 250 as a score.
    • No, 3000, 3000, 4500 would not be the same.
    • Trying a new score distribution is fun. I think that many of the people complaining (maybe not you) are complaining because it is new, not because it is bad.

    Now, let us discuss about what I think is concerning for many people (and I guess is the meaning of "will make the round worse for the remaining 99% of participants"): There is a relatively small difference of scores between B and C,D. Why might this be an issue? Because someone who solves B fast might get a higher score than someone who solves C slow. Because hacks and failing system tests play a bigger role if scores are low.

    I claim that none of these issues is real.

    • Pretests should be strong on A-B-C-D, so there should not be many failing system tests and hacks (this is a risky thing to say... future reader please forgive me if this will not be true!).
    • The difference between 750 and 1000 is not so small. In hard problems we are very used to this kind of ratio between consecutive problems. More precisely this difference means that C will be worth as B at the beginning after 1h30m. This is a lot of time and I think it is fair to say that someone who solves B in 30m should get a higher score than someone who solves C in 2h30m.

    I hope I have taken into account at least some of the concerns. In any case, I will not say anything else about the scoring distribution (because I have already spoiled too much about the contest). After the contest, I might say a bit more about the choice of this scoring distribution.

    I hope you will like the contest :)

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

      I won't try to convince you about changing the scoring for this round but let me argue further and maybe this will affect some future rounds.

      I like strong pretests in C but one can still struggle with WA and decide to skip it. Or just dislike the problem and skip it to solve something more interesting. And there are issues other than getting similar score for C and G. The further we are from geometric scoring, the more we care about the speed of solving easy problems. If scores are 500-1000-2000-4000-8000 and you solve all problems in order ABCDE, then 1 minute spent on A affects your final score a bit less than twice as much as 1 minute spent on E. If scores are 500-1000-1500-2000-2500, the ratio increases from around $$$1.9$$$ to $$$(1+2+3+4+5)/5=3$$$. If scores are 500-750-1000-1000-1500-2250-2250 then it's $$$4.11$$$. If we indeed manage to solve all these problems in time, it's like an Atcoder round but you multiply the time of solving A by 4 (and similar multipliers for other easy problems). This is how ties are decided between people with the same set of problems.

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

        Scores in range [500, 2500] made some sense when we had 5-6 problems per round. If we get 8-9 problems on regular basis, CF should use much wider range of scores. In particular, 4500 points is too little for every hard problems.

»
3 months ago, # |
  Vote: I like it -31 Vote: I do not like it

This round will be a nightmare for the beginners like me

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

And then you realise problem H is another Cube Lattice (1375I)

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

With the permission of the site administrator, I think we can actually create high-scoring problems by creating the same H1 and H2 problems, avoiding systems that limit the maximum score.

»
3 months ago, # |
  Vote: I like it -17 Vote: I do not like it

I'm guessing there will be a lot of competition for rank in this competition. Many div 2 people will do A,B,C and many will get similar points for this and same ranking. Getting good rating change is going to be tough for this round. Solving D problem will be the deciding factor for div 2, I guess.

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

    Getting good rating change is going to be tough for this round.

    How sarcastic, points are given according to your ranking between the people you compete with. Actually, I don't understand your point of how getting good rating change is tougher than other rounds...

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

Ok. I will try to solve H first.

»
3 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Not the correct place to ask but are Educational Round over ? I think every month there were two Edu Rounds.

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

    I highly doubt that edu rounds are over. Just be patient.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Unusual Start Time

Contest seems to be delayed by 15-20 mins and an unrated testing round is scheduled just before it.

»
3 months ago, # |
Rev. 4   Vote: I like it -49 Vote: I do not like it

nice contest

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

To all the people asking how to become a tester, finally your day has come! Together we are all testers in testing round 17.

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

    How so Orz monogon .rz.rz.rz.rz.rz

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

    finally your day has come! Will Mike make a thread on home page with all our names!
    LOL!!

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

    I was just about to say "in before the comments section becomes Monogon's twitch chat" but looks like I'm too late now

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

      Hi, dear SecondThread, could you please provide your unbiased opinion regarding the scoring distribution of this round? The smaller differences among A, B, C and D might not be much of a problem to Div1 Contestants, but to all other participants, especially the lower-ranked ones, it could definitely cost us. Just my opinion, tbh.

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

    As a tester of testing round 17, Give me contribution.

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

So the real contest starts after 10 mins after the 10 mins Testing Round. What if there is some issue and it can't be fixed within 10 mins?

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

    At least they will have an idea and postpone the round.

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

Hello!Hope that contest will be great and wish you high ratings

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

Why just not to make testing round earlier instead of "deviating the main round"?

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

    Ikr. That is like why ICPC and IOI 2021 will be in the same week. From the 365 days, they cannot sort this out lol.

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

    Obviously in order to have more participants in the testing round

»
3 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Hope strong pretests.Come Up~

»
3 months ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

Hope to change my color in this round . (Else would leave CP forever)

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

    Imagine becoming an admin after this round.

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

I am a big Anton Trygub fan. antontrygubO_o orz

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

I'm kinda scared. In your last AGC I couldn't even solve a single problem. Hope I can solve at least something this time

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

Looking foward to the first *4000+ && *600- problems! (Although I can't solve it QaQaQaQ)

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

Not really :'(

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

back to back rounds(global and educational) in 24 hours with no time to upsolve!! its going to be a fun weekend and a long week!

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it

What the hell?

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

How to solve B of the testing round ?

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

    52B - Right Triangles same problem.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it -9 Vote: I do not like it

    Code: [submission:95090566]

    Explanation: Compute the number of '*' in each row and column. Say that in number_of_star_in_row[i] = r and number_of_star_in_col[j] = c. The number of right triangles with base grid[i][j] is (r-1)(c-1).

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

    I think its a leetcode problem , i had already solved that somewhere. As i remember ,i stored sum of * in rows and col in arrays and then applied some math to it to get answer .

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

I think the testing round was very slow :(

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

Was it intentional that the statements of the testing round were not available in m-instances?

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

I wonder how many T-shirt did tourist get from all the contests

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

    He must be using this much of t-shirts to mop his floor I guess.

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

This global round feels like atcoder grand contest to me. (:

»
3 months ago, # |
Rev. 2   Vote: I like it -53 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
3 months ago, # |
  Vote: I like it -37 Vote: I do not like it

horrible round it is

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I think this round is not entirely fair for the newbies

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

Div 1.5

»
3 months ago, # |
  Vote: I like it +38 Vote: I do not like it
Let's see who you really are
»
3 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Code Forces Global Round 11? More like Code Forces Global Div 1 Round 1. ;-;

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

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

Why you guys need to make tough B? Now, I have idea for me but I have only 10 minutes left

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

Most Deadly Global Round I have appeared in so far .

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

Whats with the statement of C? It is so complicated for no reason.

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

Wrong answer on pretest 2 in B? Try this :

1

11 2

WWLWLLLWWLW

ans : 14

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

How to solve B?

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

    dp with memo

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

    Not tried but have a solid hint :- Try converting consecutive lengths of L as per minimum contiguous L first then next minimum series of Ls and so on until k ends.

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

      This is what i came up with during the contests , it did pass the pretest , hope it passes all the test cases.O:)

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

      yup did the same, counted the gaps or consecutive Ls and sorted them. the last pretest was really good, it gave this idea otherwise I was just growing the existing W substring in length.

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

    Observation : It is always optimal to fill contiguous loss substrings between two wins. Additionally, it is always optimal to completely fill the contiguous loss substring , thats why you sort in increasing size of contiguous loss substrings (excluding prefix and suffix). If you completely fill a loss contiguous substring, answer is incremented by (size of substring) * 2 + 1 . If you partially fill the substring answer is incremented by (size of substring) * 2. ( Note +1 in first case. This makes it optimal to completely fill substrings. To maximize that sort substrings in increasing size. )

    If after filling all the substrings, you have some operations left , use them on the prefix or suffix.

    Corner Case : When k=0 or number of wins = 0.

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

      Did the same but still was getting wa on pretest 2?

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

Problem C? Thought 2 hours on it yet clueless after one point?

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

      I have come up with O(n^2) solution similar to LIS dp. but TLED on TC5 . i optimised little bit then wrong answer. Actually I am not able to know that within my particular manhattan radius i such that

      $$$i<=r$$$

      . and what is the place within current radius where number of celebrity already meet is maximum. I hope you got where I got stuck.

      PS: Passed

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

      Got it I realised that points in range i+2*r are important only but not that after that too answer was there, just one step was remaining ! NIce problem thanks anyways.

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

The idea of using graphics in C was amazing , didn't get the question though !

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

going live now, talking about ABCDE and my maybe-wrong solution for H https://www.twitch.tv/errichto

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

How to solve C guys?

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

Thats it I am done with global rounds.

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

So one did solve H after all :(

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

I believe the TL of G is strict. My first submission is indeed $$$O(N^3)$$$ time solution, but it got TL. My local testing suggested that only iterating the graph represented by vector<vector<Edge>> takes much time. Yes, I knew it's time-consuming and I should have noticed that before implementing it. Still, I wish the constraints was $$$n \leq 100$$$ or something.

Is there any reason to set this TL, or you didn't noticed solutions like this? Anyway, I like the idea of the problem, so thank you for that.

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

    With $$$n\le 100$$$ there would have been $$$O(n^4)$$$ solutions getting accepted and solutions using fancy min-cost flow implementation (but with bad complexity) getting accepted, and I did not want that. On the other hand, I understand that the strict time-limit of problem G made it slightly harder to get accepted even for $$$O(n^3)$$$ solutions.

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

is there any dp solution for B

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

    yes I almost had a dp solution dont know why it fails on the one of the samples couldnt find out a minor bug anyways here it goes :

    B
    //Think simple yet elegant.
    #include <bits/stdc++.h>
    using namespace std;
    #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define ll  long long
    #define all(v) v.begin(),v.end()
    #define ff first
    #define ss second
    #define pb push_back
    #define mp make_pair
    #define pi pair<int,int>
    #define REP(i,n) for(int i=0;i<n;i++)
    const ll maxn=100005;
    const ll mod=1e9+7;
    
    vector<int> dp(1e5+10,-1);
    string s;
    int n,k,ans=0;
    
    int go(int ind,int moves,int cur){
    	if(moves>k || ind==n)return cur;
    
    	if(dp[ind]!=-1)return dp[ind];
    
    	if(ind>0 && s[ind]=='W' && s[ind-1]=='W'){
    		ans=go(ind+1,moves,cur+2);
    	}
    	else if(s[ind]=='W'){
    		ans=go(ind+1,moves,cur+1);
    	}
    	else{
    		if(ind>0 && s[ind-1]=='W'){
    			s[ind]='W';
    			if(moves+1<=k)
    				ans=max(ans,go(ind+1,moves+1,cur+2));
    			s[ind]='L';
    			ans=max(ans,go(ind+1,moves,cur));
    		}
    		else{
    			s[ind]='W';
    			if(moves+1<=k)
    				ans=max(ans,go(ind+1,moves+1,cur+1));
    			s[ind]='L';
    			ans=max(ans,go(ind+1,moves,cur));
    		}
    
    	}
    	dp[ind]=ans;
    	return dp[ind];
    	
    }
    int main(){
        fast;
      	int t,i,j;
    	cin >> t;
    	while(t--){
    		cin >> n >> k;
    		cin >> s;
    		int fans=0;
    		ans=0;
    		for(i=0;i<n;i++)dp[i]=-1;
    		go(0,0,0);
    		for(i=0;i<n;i++){
    			fans=max(fans,dp[i]);
    		}
    		cout<<fans<<"\n";
    		
    		
    	}
    }
    
     
    
    
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're solution is wrong. Because if you reach an index with a different moves count (k left) you can get a different result.

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

      1

      12 3

      WLWLWLLLWLW

      It fails for this test case

      Expected — 14

      Output — 13

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

The low scores for problems B-C-D-E-F-G should not suggest that they are easier than usual.

Yes, and they seemed to be even harder than usual.

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

So much for question H. Zero Solves :)

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

I've tried to solve problem C making a graph in which a node is a celebrity, and there's an edge between $$$v_1$$$ and $$$v_2$$$ if $$$v_1$$$ appears before $$$v_2$$$ and it's impossible to take a photo to $$$v_1$$$ and $$$v_2$$$. And now you have to get a maximal independent set of the graph. As far as $$$t_i < t_{i+1}$$$ and the grid is not very big, any node won't have too much edges, anyone think about it? Due to lack of time because I got that idea in the end of the contest I couldn't try to implement it, but I'd like to know if it works or not

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

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

how to optimize DP solution of C ... i got n^2 solution??????? thanks for help

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

How to solve D. I was able to come up with a solution that requires at most $$$2 * n$$$ operations. But how to do it in at most $$$n$$$ operations.

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

    In every step try to put them into (1, 2, ..., cur, ...) or (..., cur, ..., 2, 1). Just zone 1 of them into the streak each operation. Save the last one for rotation.

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

    Step 1 : get 1 as a prefix.
    Step 2 : get 2,1 as a suffix.
    Step 3 : get 1,2,3 as a prefix.
    So on.

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

    Its probably something like putting $$$(1, 2, ... , x...)$$$ and $$$(...x, ... , 2, 1)$$$ alternatingly. Like this. for this sequence $$$2, 3, 6, 1, 4, 5, 7$$$
    Moves are like this
    $$$1, 4, 5, 7, 2, 3, 6$$$
    $$$2, 3, 6, 4, 5, 7, 1$$$
    $$$1, 2, 3, 6, 4, 5, 7$$$
    $$$4, 5, 7, 6, 1, 2, 3$$$
    $$$1, 2, 3, 4, 5, 7, 6$$$
    $$$6, 7, 1, 2, 3, 4, 5$$$
    $$$1, 2, 3, 4, 5, 6, 7$$$
    I don't know the proof nor I implemented it(it was only 10 min left). But, probably this is correct.

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

How to solve D, I thought of something like grouping every ele and ele-1 together and doing this over and over again.

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

So much for "spicing up the strategies". Maybe it would've worked for a different contest, but it doesn't make for a very fun experience with speedforces and hard problems with low point values. As for top contestants, the other problems were hard enough for no one to solve H even with a 3 hour contest time.

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

I splits the array into two parts. One is positive part and another negative part.. If the sum of positive part is bigger than I printed that first and then negative part. Same for the negative part, and if both are same then answer will be NO. But I noticed one thing, if I print 0 with positive part, it gives me wrong answer. If I print 0 with the negative part it passed the testcases. If multiple answers are possible, then 0 can be in any side, it doesn’t effect, right?

And one more thing, If I don’t sort my split parts it also gives wrong answer.. But why sorting is needed? I just need to check if the sum is not 0. Sorting shouldn’t be a matter, right?

Please tell if I am wrong.
Mycode: https://codeforces.com/contest/1427/submission/95120716

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

    Consider the case: 0, 1, -1, 2, -2. Without sorting and keeping the zeroes with negative numbers you will get: 0, -1, -2, 1, 2 or something similar which is wrong.

»
3 months ago, # |
Rev. 4   Vote: I like it +2 Vote: I do not like it

This round is sooo hard. Here are my solutions to A-E:

A

If the sum of all values of all $$$a_i$$$ is 0, the answer is NO.

Otherwise, the answer is YES. If the sum of all values of $$$a_i$$$ is positive, put all the positive values before the nonpositive ones. If the sum of all values of $$$a_i$$$ is negative, put all the negative values before the nonnegative ones.

B

Let's calculate our score in a different way. The score is equal to $$$2 \cdot \mathrm{wins} - (\mathrm{number\ of\ contiguous\ blocks\ of\ wins})$$$.

Obviously, we never want to change wins to losses. Therefore, we know the number of wins we would have at the end, which is $$$\mathrm{min}(\mathrm{initial\ wins} + k, n)$$$. Now we just have to minimize the number of contiguous blocks of wins.

Let's put all gaps between adjacent blocks of wins into an array and sort it. Then fill gaps with wins, starting from the smallest gap.

The case where there are no wins initially needs to be separately handled.

C

Do a DP. $$$f_i$$$ represents the maximum number of celebrities from 1 to $$$i$$$ that we can visit, if we are required to visit celebrity $$$i$$$.

An $$$O(n^2)$$$ solution is now obvious. To reduce this to $$$O(nr)$$$ we note that if the time difference between two celebrities is $$$2r - 2$$$ or greater, we can always go travel between the two celebrities (because $$$2r - 2$$$ is the maximum Manhattan distance between any two points).

Therefore, when doing the transition for the DP we only need to manually check the previous $$$2r - 1$$$ celebrities. All the celebrities before that can come to our current celebrity, and we do not need to check each. Just maintain a maximum variable that holds the maximum $$$f_i$$$ of these celebrities.

D

After the first $$$i-1$$$ operations, we want the values 1 through $$$i$$$ to occupy a contiguous interval in the array, and we want these values to appear either in sorted order or in reverse sorted order.

Before any operations are performed, the condition is obviously satisfied. With the $$$i$$$-th operation, we want to join the value $$$i+1$$$ to the contiguous interval we have. There are several cases that we need to handle, depending on whether $$$i+1$$$ appears to the left or to the right of the interval, and whether the interval is in sorted or in reverse-sorted order. (The details are not too hard to figure out.)

We have performed $$$n-1$$$ operations now. We might need one final operation to reverse the entire array, if the values 1 through $$$n$$$ are currently in reverse-sorted order.

E

Disclaimer: I have no idea why this works, or even whether it will continue to work if the constraints are increased. Some of the claims made below might not hold for larger values. The only thing I know is that this solution can pass all test cases within constraints.

See the procedure used in the first sample? Turns out, this procedure can be generalized. Subject to certain conditions, the XOR of the initial value and the final value is equal to 2. The requirements are: - In the binary representation of the initial value (with no leading 0's), there cannot be two 0's in a row. - The bottom 2 bits of the initial value must be 1.

Once we have a 2, we can easily eliminate all bits in any number (except the bottom bit), and thus create a 1. Now we focus on how to generate a number that satisfies the requirements.

Turns out, for any $$$x$$$ within the constraints, there always exists a reasonably small number $$$k$$$ such that $$$kx$$$ satisfies the requirement. We can find $$$k$$$ by brute force, and multiply $$$x$$$ by $$$k$$$ (this can be done by finding $$$2^{p}x$$$ for each $$$p$$$ and sum them together based on $$$k$$$'s binary representation).

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

As an ordinary contestant, I want contribution :D

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

The low scores for problems B-C-D-E-F-G should not suggest that they are easier than usual. Now i know this is true. I only solved three problems in total. Problem B thought about a wrong algorithm at the beginning and wasted a lot of time. B is obviously harder than usual div2B, and C is also harder than usual div2C. D may be the same as usual div2D.upd: 10 minutes after the start of the competition, I still can't see the complete content of the question. In the mathematical formula part, all I see are inexplicable symbols. How is this going?

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

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

How to solve H?

»
3 months ago, # |
  Vote: I like it +113 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!

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

Ratings updated! That was quick.

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

Wrong submissions were a bit too pricey, and constructive tasks as always. Otherwise great contest!

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

https://codeforces.com/contest/1427/submission/95098796 Please tell me why was it giving runtime error.

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

Moral : Always check all possible inputs when the number is reasonable. Still passed all pretests even though the solution fails on a large number of inputs.

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

How to solve E systematically? I really played with numbers for 1.5 hours and couldn't find any solution :(.

  • »
    »
    3 months ago, # ^ |
    Rev. 6   Vote: I like it +42 Vote: I do not like it
    1. $$$2k\oplus(2k+1) = 1$$$.
    2. If we have $$$x$$$ we can get $$$K.x$$$.

    Reach a number $$$X$$$ that can be made such that $$$gcd(X, N) = 1$$$. One possible number would be: $$$N \oplus (N . 2^B)$$$ where B is the highest power of $$$2$$$ less than $$$N$$$.

    Proof:

    $$$X$$$ = $$$N \oplus (N . 2^B) = N + (N . 2^B) - 2 . (2^B) = K.N - 2^{B+1}$$$, which has no common factor with $$$N$$$. ($$$gcd(K.N - 2^{B+1}, N) = 1$$$, as $$$N$$$ is odd)

    After that we need to find a solution $$$(a,b)$$$ to $$$a.X = b.N + 1$$$ where $$$b*N$$$ is even.
    This can bruted by iterating on $$$a$$$. ($$$a$$$ will be upto $$$2N$$$)

    Now we just print $$$b.N$$$ xor $$$a.X$$$

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

I think weak systests for C?

95127155

500 2 950 500 500 3000 1 1

Output should be 1, mine is 0, so WA. Please correct me if I'm wrong.

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

Guys how are the "best participants" selected?

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

Petr after getting -11 on H during contest

LUL.jpg

»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Just after contest, my ratio changes +179. But after few hours : +180, even I'm still rank 80. Why?

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

I just a got mail about one of my solutions being similar to another participant. It is, but due to the common and simplest approach followed by me.(also the language used by me was python, where number of lines is less). This is purely coincidential.

And for the record, I didn't use online ide and neither my code left my machine, except from submition here.

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

    I had the same reason B is such a only implementation technique everyone used, so coincidence happens

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

probably one of the best rounds i've ever participated in. Good problem statements, clear explanations, beautifully difficult tasks, and no technical issues! Hope more rounds could be like this

»
3 months ago, # |
  Vote: I like it -17 Vote: I do not like it

The topic is a little difficult, but it inspires me to continue to study hard. The team is wonderful

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

For ABC and D, the points rating is double the points give to it.

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

can someone explain how to do problem B

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

Excellent round btw

Well-balanced difficulty unlike most atcoder rounds
Algorithmic, not mathy. It is individual but I like it
Good balance of idea and implementation
Visible effort put into editorial

I felt thrill throughout the whole contest

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

When is the list of people who will be getting random t-shirt coming out?

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

Congratulations to tshirts winners!

List place Contest Rank Name
1 1427 1 Benq
2 1427 2 yosupo
3 1427 3 ksun48
4 1427 4 Um_nik
5 1427 5 ecnerwala
6 1427 6 sunset
7 1427 7 maroonrk
8 1427 8 zscoder
9 1427 9 SirShokoladina
10 1427 10 gamegame
11 1427 11 kefaa2
12 1427 12 lumibons
13 1427 13 tatyam
14 1427 14 Enjoy_the_game
15 1427 15 jiangly
16 1427 16 Endagorion
17 1427 17 dreamoon_love_AA
18 1427 18 olphe
19 1427 19 dlalswp25
20 1427 20 duality
21 1427 21 amethyst0
22 1427 22 tourist
23 1427 23 mnbvmar
24 1427 24 Maksim1744
25 1427 25 Golovanov399
26 1427 26 snuke
27 1427 27 gs18115
28 1427 28 Radewoosh
29 1427 29 Farhod_Farmon
30 1427 30 Petr
33 1427 33 RAVEman
67 1427 67 Mikaeel
91 1427 91 amnesiac_dusk
118 1427 118 jschnei
125 1427 125 BohdanPastuschak
132 1427 131 Martin53
148 1427 148 gyh20
182 1427 182 jjjjj19980806
186 1427 186 DreamingLeaf
218 1427 218 4eT_llpuyHblJl
234 1427 234 kraborak
238 1427 238 marX
240 1427 240 ezLadder
316 1427 316 emuyumi
341 1427 341 Behind_the_Clouds
349 1427 349 Nika_Tamliani
358 1427 358 zld3794955
403 1427 402 VLamarca
439 1427 438 kupriyanov
493 1427 493 l1ll5
»
3 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I hate that problems

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

Perhaps you want to know current results of globals. See https://clist.by/standings/codeforces-global-rounds-2020-18730990/.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<stdio.h>
int main()
{
    int t=0,p=0,z=0;
    int negative=0;
    int positive=0;
    long sum=0;
    int array[51];
    int temp=0;
    int y=0;
    scanf("%d",&z);
    for(int x=0;x<z;x++)
    {
        scanf("%d",&t);
        while(p<t)
        {
            scanf("%d",&array[p]);
            if(array[p]<0)
            {
                negative=negative+(-(array[p]));
            }
            else if(array[p]>0)
            {
                positive=positive+array[p];
            }
            sum=sum+array[p];
            p++;
        }
        if(sum==0)
        {
            printf("NO");
        }
        else if(positive>negative && sum!=0)
        {
            printf("Yes\n");
            for(int i=0;i<t-1;i++)
            {
                for(int j=1;j+i<t;j++)
                {
                    if(array[i]<array[i+j])
                    {
                        temp=array[i];
                        array[i]=array[i+j];
                        array[i+j]=temp;
                    }
                }
            }
            while(y<t)
            {
                printf("%d ",array[y]);
                y++;
            }  
        }
        else if(positive<negative && sum!=0)
        {
            printf("Yes\n");
            for(int k=0;k<t-1;k++)
            {
                for(int m=1;m+k<t;m++)
                {
                    if(array[k]>array[k+m])
                    {
                        temp=array[k];
                        array[k]=array[k+m];
                        array[k+m]=temp;
                    }
                }
            }
            while(y<t)
            {
                printf("%d ",array[y]);
                y++;
            }  
        }
        printf("\n");
        p=0;
    y=0;
    }
    return 0;
}

Could anyone help me I do not undrestand what is wrong with my code on my computer everything works perfect but when I submit my solution the program give odd answear, why ? Link to problem https://codeforces.com/contest/1427/problem/A