Hello, Codeforces!
I'm glad to invite you to Codeforces Round 732 (Div. 1) and Codeforces Round 732 (Div. 2), which will be held on Jul/11/2021 17:05 (Moscow time). Note the unusual start time of the round.
The round will be rated for both divisions. Each division will have 6 problems and 2.5 hours to solve them. There may or may not be an interactive problem, so I suggest you should read the guide for interactive problems.
All problems were written and prepared by CoupDeGrace, kuangbin, mejiamejia, Heltion, Melacau, Nanako, GOATWU, Cirno_9baka, Suiseiseki, ODT, box, Ynoi, syh0313, wh0816 and me.
And thanks to QAQAutoMaton, gamegame, starusc, interestingLSY, chenkuowen, DataStructures, Monogon, ijxjdjd, Schwarzenegger, sunsiyu, Nezzar, mana, TheOneYouWant, gyz_gyz, kimoyami, njupt_lyy, ptd, coderz189, manik.jain, absi2011, gyh20, errorgorn, antontrygubO_o, oolimry, zhangzx123, wxhtzdy, tribute_to_Ukraine_2022, SonDinh, triple__a, Pecco, AzusaCat, dorijanlendvaj, Imakf, Forever_Pursuit, kartikeyasri23 for testing and good advice, isaf27 for his excellent round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.And you, for participating!
This is my first round ever. Great efforts have been put in during the past six months. We are sincerely looking forward to your participation. We hope everyone will enjoy it.
Good luck!
UPD1: Here's the score distribution:
Div 1: 500 — 1000 — 1500 — 2250 — (2000+2000) — 4000
Div 2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
UPD2: Sorry to everyone! This is my first round and I spent lots of time to prepare it. I prepared at least 23 problems, and chose these eight ones for this round. I invited 35 testers to test, and chose problems according to their feedback. However, the difficulty is more than expect.And the pretest is not strong, leading to FST for many people. I blamed myself sadly. So I must say sorry to you, my dear friends. I will improve myself in the future. Wish you good luck and happy everyday. (๑•ᴗ•๑)
UPD3: Tutorial is available.
UPD4: Congratulations to the winners
Div1:
1.gisp_zjz
3.xtqqwq
4.Swistakk
Div2:
1.ki_msaga
2.jk-jung
First Upvote done.
Video Editorials of this contest - Div.2A AquaMoon and Two Arrays
- Div.2B AquaMoon and Stolen String - Div.2C AquaMoon and Strange Sort
orz! Looking forward for a great round!
I can confirm problems are awesome! Good luck in the round!
BS
I'm never trusting a tester's word ever again.
No offense.
noc
though only the first 2 problems of div2 are different :)
Is Aquamoon a girl?AquaMoon
Yes, I hope you like my problems!
You are a very cute girl, I believe I must have good luck in this contest. Hope I can like your problems.
Thank you! Wish you good luck and happy every day! (๑•ᴗ•๑)
the community bonked me hard i see
And you didnt even participate lol
I just solved a single problem! :(
great start buddy!
I solved 3 today, hard work is paying off, I assume :)
Became Pupil for the first time :}
Congrats, my friend. Wanna race to specialist? :p
Yes. She is a lovely girl.
Yes, but, unfortunately, this is not a dating site. :P
Coordinators: How many testers do you want?
Authors: Yes.
Most of the testers are my friends. It's me but not coordinators who invited them for testing.I want to make the problems better.
Seems like you like making even blue as your friends. Can I be your friend in next round? :P
Of course you can. Welcome!
I am interested in testing too. Hope i can be your friend too
Tip: If you want to be her friend, you can ask her discord using the cf station letter.
what is cf station letter. Pardon my naiveness but i dont spend a lot of time on cf. Also google search showed irrelevant results
It's my honor to be your friend!
yes, we are on discord now
It displays that you are quite passionate in making your first round likeable. I wish you good luck that everyone will like your contest!
I think that this contest shows well why friends are not good testers
As a tester, problems are great!
BS
2.5 hours... Any reason?
Determination is based on the feedback of the testers.
The photo below the goodluck!..is giving me good vibes ❤️
How u practice your math skills like typical pnc problems and dp + pnc , so difficult to find intuition sometimes.
Good problems! The difficulty level is moderate, the knowledge covered is broad, the statements are clear and short and the solutions are more natural.
I would like to give upvote to the writers!
update near the end of the contest: Now you may know what's the true meaning I said.
Great thanks to conscience problem writers!()
"The difficulty level is moderate"
There's a famous problem setter in China.
And he always set comments like this after the hardest contest in China.
I just translate it into English and change something.
题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。 给出题人点赞 ！
you should've said this before the contest "/
But someone didn't let me say.
So I could only set a comment like that, expected someone would get the meaning.
Every asian rounds ever
no nothing is true T-T, you played with us.
I'm a tester and I'm sure the problems are excellent!
Oh, yes. It's so excellent that I can boom 0! :)
Good lucky to everyone.Get a high rank!
will benq cross 4k
tourist reclaimed the throne
*Tourist reclaimed the throne without even participating
that's what i call a pro gamer move
As a tester, I hope you can get the ideal score :)
As a setter, I hope you enjoy the problems!
Subscribe to Technoblade to AK div1 :)
And what about div2 guys? What should they do to AK round #732 div1 ?
Work hard and improve yourself. Good luck! Wish you would be happy everyday.(๑•ᴗ•๑)
After mathforces and messforces I am hoping for good codeforces Round .
This was just a sarcasm guys don't take too seriously?.
It's like talking random shit which belittles the efforts of the setters and testers and then trying to push it aside as a joke. I can't see why you wouldn't get downvotes for this.
Good luck in the round! I do wish that you can enjoy our contest!
How is this not in the homepage yet?
It's on the homepage now.⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄
I literally had a heart attack seeing this much color at one place!!
Bro thats serious, go to the doctor.
i took this advice seriously and doc prescribed me 3 more cf rounds in this month
>.<
As I tester, I can say that the problems are very interesting! Strongly suggest you to participate!
Wow, Chinese Round again!! So many familiar writers and testers, can't wait to participate in ;)
Why is it called the China Round
As a participant , I can say that I dont know anything about this round.
Just look I see the post after 6 days !!!
Sorry. We made a draft 6 days ago.
No problemo.. Just noticed its on my birthday.Wish me luck.
Happy birthday! Good luck! ~╮❤╭~
I can't confirm as I'm mentioned in the blog for absolutely no reason, but I do believe problems will be great.
First time I've seen the word "behoove" in a sentence...interesting word!
Sorry, I have fixed the issue. Sorry for my word. Sorry again. Could you forgive me? (╯﹏╰)
There's nothing wrong with behoove? I just thought it was interesting..
Coming!
Orz yyb !!! You're my idol !!!
I have not worked out any problem for a long time, probably I cannot solve any problem in the round >_<
I bet you will solve at least three problems (*≧▽≦*)
I think that is impossible >_<. I have no ability to solve so many problems in a round now.
Don't be too modest ! (✿ω✿)
But that is the truth. QwQ
I wonder how this idiotic talk is getting upvotes
This is to illustrate that contribution points reliably measure valuable contribution. :)
I am really excited for the problems! hope high rating for everyone .. including me :)
Aarghh!! Clashing with Wimbledon finals time (:
Are you participating in Wimbledon finals?
Auto comment: topic has been updated by AquaMoon (previous revision, new revision, compare).
I'm sure that AquaMoon's first attempt will be glorious
first time a round post where round coordinator is given a backseat and testers are racing to win the game~
This comment section is one of the most wholesome ones I've seen on codeforces thanks to AquaMoon!!
Aoligei, ganle!
Mathforces->My favorite genre
The mighty Chinese questioning team!
Looking at testers and setters I already feel like I'm going to learn a lot from this round. Thank you for efforts!!
An All-star Round
Best wishes to everyone):
It must be an interesting round.
I think Div.1 F is a data-structure problem. Because ODT is one of writers.
Maybe or not (≧▽≦)
As you wish......-_-#
99% of the comments : "as a tester...."
As a tester...
Is this rated?
why are you looking for downvotes
A 'relevant to this blog' meme
Should i start my journey with this contest ?is div1 easy than div 2 ? I have registered today itself ,i don't know anything about this site
difficulty level is div1>div2>div3 If you are just getting started, div3 would be better. But there is no harm in giving div2 contest. Give div2 contests.
Thanks bro .btw can you give me some tips to be a specialist over here
A noob whose first problem solved on Codeforces involving fenwick trees :|
The score distribution seems very good! I hope I will be able to participate. If you need an extra tester in future contests, I'll gladly help :))
Get to that level firstly man
Hi, I hope to get there soon! It's going pretty good, no worries! :))
Welcome! You can contact me in CF talks.
At which rating we can be a tester and can i be a tester ?
There is no requirement for rating, but you must be a good friend of the writer or coordinator (the core idea is that you are trustworthy).
I hope there are no math problems
Maybe or not (≧▽≦)
CCP is proud of you! No more gang of four!
Sunday = contest day (Leetcode->Kickstart->CF) Back2back contests
Also, Leetcode $$$\lt\lt$$$ Kickstart $$$\lt$$$ CF, gets better
Any tips for the newbies:)
enjoy the contest
What is the penalty for div 2?
Aquamoon responding to every comments leads to some fat contribution for her, ngl.
Standing on 1399 I can ask only one thing from you , I need atleast +1 rating change .
Sorry couldn't participate , will try next time !!
Q!!
AquaMoon is not good at Programming is a pun!
Why did i even start programming ?
for depression
The difficulty gap between problem D and E (B and C in div 1) is so large. The contest has run 1 hours and half and no one accepted E in div 2.
i quit after solving a, b, c.
I quit after seeing problem E has no accepted submissions. And go to the standing board to see my current ranking dropping.
I'm not even reading E, comment section is more exciting.
Maybe not. D seamed crazy too to me at first. Maybe from some strange angle there's short solution too.
Wow. That's some really monster combinatorics :) I'd like to see where to read on this.
AquaMoon was so hard but the problem was interesting !!
But still, problem statements where ones of the clearest I've seen on codeforces :)
We couldn't help this much. Tell AquaMoon to be good at programming.
Hackforces
speedforces also
AB-forces
AquaMoon aka 'not good at programming, yet better than you'
Me seeing numerous solution of Div1A get hacked:
What is the hack test for Div1.A?
1
6
2 1 2 1 2 1
Oh, god. Two adjacent friends with same number but different directions can't switch their directions! Why did it seam so apparent they could... ah...
Did anyone actually manage to prove the solution for Div1B? I just did some guesswork based off the pascal's triangle. And also how weak is the pretest for Div1A because I see so many people getting hacked
You can moves 1s in pairs. So consider 0s and one 1 from odd size blocks of 1s to be fixed. Now this is just normal stars and bars where you're trying to place the pairs of 1s among the 0s (odd block 1s are indistinguishable regardless of which side you place the block(s) on).
Damn, I could not make that observation during contest, guess I have to work on some combinatorics.
Note that the operation is equivalent to 'shift 2 1's to the right or left'.
Now we can just move any even subsequence, so let's focus on the sequences of an odd number of 1's. Between these sequences, the number of 0's is constant.
Great, so if we ignore the pairs, which we can move, we get a sequence like 0000100101 with no 2 consecutive 1's. Then we can basically ignore the 1's, we only get to choose which 0's to put each of the pairs of 1's between. Suppose there are Z 0's and P pairs. Using the stars and bars argument, there are exactly
ways.
Here's one intuitive way to justify the formula for Div1B: Greedily pair up adjacent ones. Then, you can (with the operation) permute the zeros and the pairs of ones arbitrarily, and the unpaired ones will have their locations determined by the zeros. If there are $$$p$$$ zeros and $$$q$$$ pairs of ones, there are clearly exactly $$$\binom{p+q}{p}$$$ different ways to do this.
EDIT: I should have refreshed to check if this was already answered before typing this up. It's too late now, though!
How did pascal triangle helped you in this "Aquamoon and Chess"?
Just look at the 14th row of the pascal triangle and you will see the answers for the last three sample, 1287 and 715, so I assumed there is some kind of a combinatorial formula that immediately solves the problem and found the exact formula explained by others.
Seems I need to byheart the pascal triangle rows.
Yes.First we will add 2 zeroes one at the beginning and one at the end.let x be the number of zeroes.let ai be the number of ones between the ith and (i+1)th zero for all 1<=i<=x-1 .Notice that the operation is same as subtracting 2 from one index(which has value atleast 2) and adding it to 2 to one of its neighboring index so the invariant is parity of ai.
How to solve B?? Turns out this whole cute blog was a clickbait.
The key observation here is that when swapping, the swapped characters' position do not change. So you go over all n strings and store each letter's position, then go over the remaining n — 1 strings to rule out positions, which leaves you all the letter positions of the missing string.
Omg, this was easy, I got confused with swapping and shuffling in the statement and messed up pB.
I thought strings could be shuffled after swapping. Smh.
Yeah, it happens. The statement is quite long :)
How did you solve D?
((No. of consecutive ones-1) for all streaks of ones +no. of zeroes) choose (no. of zeroes)
Yeah, I just realized that too. Ran out of time to implement during contest :(
FSTed in C , I think I did very poorly, smh, so much weak pretest.
You should check my result, it'll make you feel a bit better ^^
I took the sum of ASCII values of i'th(1<=i<=m) character of all the original strings and subtracted from it the sum of ASCII values of i'th(1<=i<=m) character of all the new strings.Then just accumulated the character for that value in a string.that's your output.Check my submission for clarity.
tilted off the face of this fucking planet, I can't solve C because I can't implement for fking shit, even with 50 minutes AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAVAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAASDFKLSANFLKAS;JFLSJKL
it is actually very difficult to upvote your comment in my computer because of the huge AAAAAA
There's a lone V in your AAAAA...
Finally tourist will be back on rank 1 .
I tried to hack some of the solutions with test
I think the answer should be YES here, but the checkers says it's NO. Any ideas? :)
After you convert the array to
2 2 2 3 3 3 3, the direction of each element isL R L L R L R. There is no way to convert that to allRL R L L R L R -> R L L L R L R -> R R R L R L R -> R R R R L L R -> R R R R R R R ?
I dont think your final array is sorted
In the second-to-last step, you cannot make LR to RL.
When you swap an L with an R, nothing changes
L R
-> R L (swapped locations)
-> L R (lefts become rights, rights become lefts)
Holy Moly! Thanks for explanation :)
I think you can't go from
L R L L R L RtoR L L L R L Rby swapping only the first 2 elements. They still face the same direction.Note that when a person moves, they also carry direction with them. In this example, the first person is facing the
L. After swapping positions with the second person, they will faceR, so the direction for element 2 is still 'R'Shouldn't it be NO? (Either that or my solution is going to FST)
In essence a swap moves a person to a position of the opposite parity. So for an even number of swaps they must be on the same parity in the end. So count the number of people with each $$$a_i$$$ on each parity in the original and sorted arrays. They should be the same for YES.
With
3 2 3 2 3 2 3, we have all 3s on odd parity and all 2s on even parity.After sorting we have
2 2 2 3 3 3 3which definitely doesn't satisfy the property. Is my analysis wrong and is there some way of achieving this movement?11 pretests passed. Kudos to the authors :))
I made the same mistake , think "LR" will be "RL" in a swap.
Same...
When hackers get hacked :>
new 200iq contest strategy: write a bad solution so that you get hacked, realize that many other solutions can be hacked with the same test and gain more points than you lost
Give test please!
For D2E is this true — If we make a graph of array as nodes result is $$$2^{c}$$$ where $$$c =$$$ number of bipartite components?
I thought about counting in such components, wherein component nodes(arrays) are pairwise distinct in every position (component is a full graph) and the answer is a sum of C(size_of_component, n) for each component
Not to complain but this round is WAY TOO HARD for me
System testing is gonna slower than internet explorer.
What the hell is wrong with you? Wasn't half a year enough to prepare well? Why does this bold note in D even exist? I don't see any reason to make this task "interactive" and put that garbage in the statement. Did you want to make your long awful statements even more unreadable? Well, then you succeeded. Also, please, learn such mathematical constructions as "intervals" and "segments" so you don't have to cripple your statements with these countless 10^-18. Pls stop creating problems.
I think this is because it's quite hard to check if an input is valid. And, maybe codeforces doesn't have a way to provide a different input format as a hack unless the problem is interactive.
They are making the problems interactive to support the hacking format.
Prob hacks. Well, if you use intervals instead the answer has to be defined as limit and that's another can of worms.
Hello. It is very unpleasant to read your comment, so I can't ignore it.
About the interactive problems Div2B and Div1D: it is impossible to ensure, that the input is valid because it is NP-hard problem. So, validator can't be written and we have some ways how to deal with it:
It was my proposal to use the second option, maybe it was not the best, we will consider this experience in the future. Anyway, if the paragraph about the interaction was unclear to you you had an option to ask the question to us.
About the intervals. Everything was defined formally. There were no mistakes in that definitions. So what can be told here? We know the difference between intervals and segments.
If you couldn't solve the problems it is very stupid to take out your anger on authors. I have personally seen how much work was done to make this round possible and know how much sadness you can make by your comment.
Of course, in this round, there are some things, that we could do better. And thanks to everyone, who will write his or her good or bad opinion, but not in such form.
And according to the style of your comment, I propose you stop writing such comments after the round.
I hope I will see many rounds from AquaMoon and her friends because in my opinion the problems were very interesting and had very beautiful solutions.
I also liked the round, thanks for your efforts in preparing it.
One thing I want to point out here. Maybe it would be better to let the participants know why this problem is "interactive". It was a little annoying reading a restriction that comes out of nowhere.
what the hell are you talking about? why if problems are disgusting and statements are ugly people can't talk about it in comments?
He never asked not to talk about it. You know you can discuss about them without insults to authors right?
Hello. It is very unpleasant to read your answer to this comment, so I can't ignore it.
First of all I want to clarify that I missed the round and had a chance only to read the problems in the middle of it so I can not honestly say anything about the quality of the problems even so I may or may not like them. I want to thank authors and testers for their efforts in preparing this round, but certainly there were some issues which could be fixed for the sake of future contests.
About Div1D: I believe that most of the displeased contestants were confused by the fact that problem was interactive for some reason and that it was included in the middle of the statement without any proper explanation. I think it should be considered a bad tone to say that if you had any questions(about obviously somewhat unclear statement) you should have asked them lol. From my and my friends experience of problem setting, it is considered to be authors' and coordinators' responsibility to make problem statements clear and easy to understand for the majority of participants, as it is your desire to attract as many people as possible to take part in your round.
About Div1E: I guess that the main objection here is that using intervals of time with +- 1e-18 thingies sounds a bit strange and obfuscates the problem statement in a certain way. For sure, your definition was formally correct, but again it is best to write it more clearly. These intervals just look ugly and it's unpleasant to read a problem statement like that.
It also looks very petty to me to make remarks like "If you couldn't solve the problems it is very stupid to take out your anger on authors". It's very bold to make such assumptions, and from what I understood despite the offensive form of his comment the main problem in this round in his opinion was not his lack of ACed problems during the contest or even the quality of the problems themselves, but the problem statements. Even the most offensive phrase is just a reference to an old comment from the famous nuttela coder if I recall correctly.
There were lots of rounds and lots of displeased people in the comment section with messages way more rude than this one(for example under my global round). I agree that it was wrong to put all the blame on the authors, however, decent problems statements are mainly coordinators responsibility and your a bit childish response made it look even worse than the comment itself.
Maybe late, but here is an explanation on Div1E.
Cirno_9baka told me the problem like this: there are some squares in a plane, and there is a line (y=x), the line can't cross the squares( but not include the bound), and change the line need some cost, find the min cost.
Then change it to the statement with the backgroud is a hard work ( The problem had been changed because no writters could solve the previous version. ) How to define we can walking on the bound?
We have discuss about both closed interval and open interval, if it is closed interval, than the boundary is not able to be walked.
It seemed that open interval can solve the problem, but there is still a problem, how to control the time?
We can stop the time, but if we let the time go, and then, the person will die immediately.
Finally, we thought to define it with +-1e-18 is the most clearly definition for the problem.
The statement of Div2B is hard to understand, which is bad given that it is a more or less trivial problem.
The main points are:
For me it was like 20 minutes text understanding but only 2 minutes problem understanding. Since A was not very clear either I did work on B before submitting A. And after having spent that 20 minutes I was out, not submitting anything.
Hi ! I have a doubt regarding this. Can you please help me understand why getting a validator in a non-interactive version is np-hard and how making it interactive solves it ?
talant's comment is very rude. It is also arrogant and aggressive. I'm sad that high-rated participants allow themselves to lead the discussion in this way. This tone divides the community and multiplies the negative. The same facts could be stated without aggression.
Let's read the text again.
Intolerable form and transition to personality. Great start to the discussion.
Well, why is it here? It is solely a matter for the writers and the coordinator with what intensity they work.
The word "garbage" has been added to make the authors more unpleasant.
Again all sorts of unjustified rudeness and amplification: "awful", "even more unreadable". Well, you're just manipulating! The problem is quite normal, except for this unusual phrase. There is nothing at all bad about it.
What an arrogant tone. And very disgusting. In addition, the international mathematical community (in contrast to the Russian mathematical school) did not seem to agree on the terms interval and segment. See https://en.wikipedia.org/wiki/Interval_(mathematics)#Note_on_conflicting_terminology
No, I prefer you just stop solving problems here, please. I really hope that the authors will not listen to you, but will simply draw some conclusions and please us with another round. They made significant efforts to make the community better. And you have no moral right to write to them in that tone.
Let me summarize. I believe that it is imperative to give feedback on the rounds and problems. Including pointing out defects and mistakes. But this must be done in the form of civilized communication of educated people. You offend people. It's always easier to attack and criticize. It's just mean to behave like that. Preparing problems is very difficult, it is not an easy job. We must support the writers, be grateful to them. This is an adult and mature position. And mistakes and defects must be pointed out correctly.
C was beautiful =)
A and C dawn on systems, bruh
Hack test(problem div2C/div1A)
1
10
5 7 5 7 5 7 3 3 4 7
Output: NO
Is "NO" what a correct program would output in this case?
NO is correct answer
I think the answer is 'YES'. My logic:
Feel free to correct me if I'm mistaken somewhere.
every 5 is on odd position and 1 need to be on even position at the end so answer is no
Eh? The original three 5s are on odd positions, and 2 need to be on even positions (a.k.a the 'L's), which can be swapped to 'R's. Same goes with the four 7s.
You can't do L R L -> L L R.
oh yeah, i see. thanks a lot
why not..? Can you please explain...?
If you swap RL the R on the left becomes an L when it get's to the right, and the opposite occurs with the L, making RL -> RL
Thanks for this beautiful contest.
lmao
FST kids
Can't believe the solved count of problem D in Div2
Solution was leaked...lol
A,B,C,D...Some uploaded all of them at 9:40 India Time
They sky rocketed in last 20 mins
Thats why u shd never underestimate the power of telegram.
If someone told u ans=ncr(zeros+ $$$\Sigma$$$ consecutive ones/2,zeros), you would have solved it too.
No cases of plagiarism, no penalty, <500 rank, absolute win.
Could anyone explain the solution to Div2D ? Editorial is not helpful at all.
What's the intuition behind the nCr formula?
Let n be the no. of zeroes and m be the no. of pairs of 1 . Observation : we can replace atmost 1 one from a pair of one's with any zero in the string . So answer is (n+m)C(n) , since there are total n+m things and we have to choose n of them which will be zero
Already figured out D2D is calculating combinatorial number but didn't have the time to implement it... sad :(
thanks for the contest
I regret not trying to hack during the contest
Wow what a contest (--_--)....**** the test cases :|
Anyone faced an issue with B problem, thinking about the answer when
n = 1Submission 1 Submission 2 Ac I got twoIdleness limit exceeded on pretest 3because of this.Great problems anyway!
Didn't you forget to
returnaftercout<<r<<"\n";?Oops! Thanks!
Couldn't solve problem A
how to solve D?
Notice how the pawns travel in pairs. If a pair of traveling pawns meets an isolated pawn, then the odd pawn gets shifted one to the left and the pair continues on its journey:
This is equivalent to if the odd pawn didn't exist at all.
So we can iterate over the array and count the number of pawn pairs $$$p$$$ and zeros $$$z$$$. Then the total arrangements are $$$C(p + z, z)$$$.
The answer is
nCr, whereris the count of number of zeros in the string andnis r + (No of consecutive 1s)/2.For ex, 100111100
Here,
ris 4, andnis 4 + (1/2) + (4/2) = 6. So answer is6C4You'll have to find
nCr % pusing some efficient technique (like here : https://www.geeksforgeeks.org/compute-ncr-p-set-3-using-fermat-little-theorem/)Can you explain why it works?
Sure.
Observe that if you have 0110, you can move this "11" as a single entity. So, you can have 1100 or 0011. Similarly, if you have 011110, you can move the two "11" as separate entities, like 110110 or 011011 and so on..
Basically "11"s move together and 0 can move anyways as it pleases.
Now, 011110 can basically be treated as collection of 4 elements where two 0s and two 11s are identical. This means you have
4!/(2! * 2!)possible ways to permute, which is same as4C2.You can try multiple examples with variations like
01110or10110(i.e. what if you have odd number of consecutive 1s) and you'll see that the observation still holdsThanks for this explanation! To add on the last point about odd number of consecutive 1s, if we fix the positions of all 1 pairs, then all the remaining single 1's position will be fixed as well, hence they do not really matter, right?
Yes. Once we choose certain "11"s as pairs that we're gonna permute, the remaining single 1s won't matter as they'll be fixed.
Thanks for this. Editorial was too bad for this problem.
The binomial solution is also pretty heavily motivated by analyzing the simples. Two of them are 13C5 and one of them is 13C4 which leads one to think whether we can break the structure down in order to get that form. Once you look for something along those lines, the solution becomes way easier to find.
Man, Div 2 C really gave me hell. I can't think clearly about permutations this early in the morning.
And I didn't even solve it correctly in the end, FST my life. :(
Why was B such a half baked interactive problem tho?
I have the same question
It actually caused some timelimit issues in python for me, so I would like to know what was the reason to set up the problem as interactive
Can you tell me whether this TLEd due to time limit issues for py or anything can be optimized?:/
The biggest issue is
ans += chr(curr)actually. In pypy strings are trully immutable and this operation is O(n)But even without it you have input of 10^5 strings which is somewhat expensive and pypy is not good with io. I usually bypass it by having the entire input read in the beginning which is not possible in interactive problems, That was my issue.
The solution is the same though. I think your code may pass if you resubmit in python3, not pypy
Because it's impossible to write a validator if we don't use the hack format.
I think the word Pre-Tests is self-explanatory. Why did you even care to run pre-tests on Div1 A if they were so weak.
HackForces
I accidentally submitted for A at 00:54. ╥﹏╥ I swear my hand autopilotted me to submit A.
I will be orange without the pA hack. I am going to quit cp. (Nah just kidding but I hope the pretests are stronger :(
Solution for div1D
For finding the culprit, find the consecutive sums of coordinates of that aren't in AP.
With this we get the culprit, and the number $$$D$$$ to be added to one of the coordinates in that culprit time $$$T'$$$.
Now observe sum of squares of coordinates for a time moment.
They are of the form $$$f(t) = a + tb + ct^2$$$
Find a, b, c by finding the sum of squares for any three unchanged moments and solving the linear equation.
We now know what the sum of squares of coordinates will be at $$$T'$$$. It's just $$$f(T')$$$.
Now find a coordinate in $$$T'$$$ which if incremented by $$$D$$$, makes the sum of squares $$$f(T')$$$. This number is unique under the constraints. (brute force)
Who can estimate the difficulty of C div1?
I guess 2900?
What the hell is the interactive solution? Why does not my solution work? I' ve added
fflush(stdout)as tutorial says.https://codeforces.com/contest/1546/submission/122130911
UPD: see my comment below.
Dude, you have to flush in a loop, not outside the loop
You only flushed for the last output, do it inside the loop
Same result https://codeforces.com/contest/1546/submission/122130422
I dunno, try using endl
"\n" is the same as endl.
not completely true
endlflushes the output but\ndoesn'tendl flushes the buffer and moves to the next line
Ok, but why
fflush(stdout)does not?You had to you fflush before taking input every time , you flushed it only at the end of all test cases which is surely wrong
Look at the second link — it flushes in loop.
You had to flush after every use of printf, your fflush(stdout) is outside the loop.
UPD: problem is, as mentioned several times: flush must be inside loop, like my another solution: https://codeforces.com/contest/1546/submission/122130422
The reason why does the second solution fails is that test case input does not send new line at the end of input. I'm reading input as
scanf("%s\n",s). My opinion is that it is a bug of a test case.You don't actually ever have to flush the output, I have no idea why people in this thread and the problem statement said that you have to. The only problem was there not being a newline at the end of the input, which is really weird.
It is very interesting, why the solution doesn't work.
I checked now, that we send new line at the end of the input, so there is no bugs with a test case.
May be a bug with the test system?
It is very unlikely, because I think test system just creates a pipe between the solution and interactor and they communicate through it.
Maybe scanf works differently when it reads the data from pipe.
Div.1 become speedforces, sad to see my negative delta...
1E and 1F just stand there, and no one can defeat even either of them! lol
Find a hack case in the last minute and lose 400 pts :(
Lots of WA on problem A because of my carelessness.
(._.) (._.) (._.)
How do you manage to have 998244353 testers yet have weak test cases and imbalanced af contest.
Maybe because 998244353 = 0 (mod 998244353)
"How do you manage to have 998244353 testers yet have weak test cases"
It's very easy: just don't stress test the testers' solutions. My solution for d1A would've gotten hacked.
Forgot that B was "interactive". Waiting for my
Idleness limit exceeded on test 5:D+)
I think it just puts all the input from the beginning in this problem.
I was lucky to be late for the contest.
As a tester, I dont know why they thought that most testers only solving AB was good difficulty balance.
when can I enter virtual participation in this contest?
I believe it's just after the system finish testing all incontest submission so it should be in half an hour approximately
There is a decades-long technique to store secret data in the answer file.
A pity Polygon does not support it, and the authors have to resort to technical interactiveness.
What's happened?
Umm, nothing?..
What didn't happen so far is supporting the technique in Polygon. Generally, pre-generated answer files are against best practices. So, such feature would be abused by novice or lazy problem authors, if it existed. At least that's the rationale I know.
Can you explain how this relates to today's contest? Is this related to why Div 2B was interactive?
Yeah. Ask yourself the question: why is the problem set as interactive?
Anyway, it's not without upsides: the current technique (with interactiveness) allows for hacking, without changing anything in the hacking interface. I'd like it to matter more though, the common and very loud opinion is that hacks are bad somehow...
It's sad that just "knowing" a formula can get you solving Div. 2 D problems.
Scenario 3
Can you elaborate pls!
The link in the spoiler describes it very well.
Here in our problem, we have:
and the answer becomes:
Where $Ones$ contains the sets of consecutive ones in the input string and $$$odds$$$ is the number of sets in $$$G$$$ which have an odd size.
Wont it be Scenario 2? Edit: It can be solved with Scenario 3.
Come on! It's Stars and bars.That's like basic combinatorics .We are supposed to know that.
but it's a basic combinatoric formula, it's like complaining about binsearch problem that has to be solved using binsearch