By Vladik, 6 months ago, translation,

Hi Codeforces!

I am glad to announce and invite you to Codeforces Round #678 (Div. 2), which will be held on Oct/24/2020 17:05 (Moscow time). A couple of weeks ago, we held Codeforces Round #675 (Div. 2) based on the tasks of the [contest:297213], and this time we want to offer you to solve the best 5-6 problems of the finals.

Please note the unusual start time of the round. This round will be rated for the participants with rating lower than 2100.

This is the second year that Andersen has been holding the competition, which is primarily intended to support students of regional Universities in Belarus and Ukraine (starting this year). This year, 60 students from regional universities in Belarus and Ukraine will take part in the finals of the competition.

Thanks a lot for your contribution to the preparation of the round!

Good luck to everyone in the upcoming competition! :)

UPD: The editorial was posted.

Congratulations to the winners of div 2:

as well as div 1 winners:

Thank you all for participating!

• +278

 » 6 months ago, # |   0 Unusual time + Comments on Scoring Distribution
•  » » 6 months ago, # ^ |   +11 added, thank you
 » 6 months ago, # |   +10 Stay hydrated!
•  » » 6 months ago, # ^ |   +126 Why do I get the strange idea that some people just copy what I say?
•  » » » 6 months ago, # ^ |   +19 Last time I saw you was orange and setting great contests. Congrats on getting grandmaster :)
•  » » » » 6 months ago, # ^ |   +32 *testing
•  » » » » 6 months ago, # ^ |   +10 Yeah congrats circle
•  » » » 6 months ago, # ^ |   +9 Everyone beware!, Comment section hijacker is in the house! (why not hit 200 with this one ?)
•  » » » 6 months ago, # ^ |   +15 I wanted to see if a green warrants less upvotes than a red :P (which it does, as expected)
•  » » » » 6 months ago, # ^ |   +15 Well it doesn't help that people remember that Monogon wrote it first already
•  » » » » 6 months ago, # ^ |   +16 Hey, he was a tester when he left the comment. I think, big part of it was tester appreciation.
•  » » » » 6 months ago, # ^ |   +33 You forgot that people are less likely to upvote something if you're the 2nd person to say it and that it's more important that the comment poster was monogon than that the comment poster was red.
•  » » » 6 months ago, # ^ |   +3 They are copying your strategy to get contribution points.
 » 6 months ago, # | ← Rev. 3 →   -13 Last time the contest was nice. Hoping the same this time as well.
 » 6 months ago, # |   +96 Clashes with El Clasico
•  » » 6 months ago, # ^ |   0 Yeah that's a terrible news too ):
 » 6 months ago, # |   +4 I have a question to ask the author. Compared with other div2 competitions, the questions in the last preliminary round are already considered difficult. Are the questions in the finals more difficult than the preliminary rounds?
 » 6 months ago, # |   +42 Codeforces Cotest at 8:05pm El Clasico at 8:00pm What will you choose!
•  » » 6 months ago, # ^ |   +17 Obviously Codeforces Contest .
•  » » 6 months ago, # ^ |   0 7:35 pm*
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 He is from Bangladesh. Bangladesh's time runs 30 min faster than India's.
•  » » » » 6 months ago, # ^ |   0 Oh, my bad!
 » 6 months ago, # |   -31 El Clasico at 20:00.Is it possible to reschedule the contest!!
•  » » 6 months ago, # ^ |   +303 Do you really think any of the players were going to participate?
•  » » » 6 months ago, # ^ |   +194
•  » » » » 6 months ago, # ^ |   +29 Also ronaldo could play this game, but he came to Juventus
•  » » » » » 6 months ago, # ^ |   -15 But Ronaldo attackted by corona . Hope to , champ will get well soon !
•  » » » 6 months ago, # ^ |   +35 GOAT -messi- is going to miss El clasico due to cf
•  » » 6 months ago, # ^ |   +65 CF round at 20:05(UTC+6). Is it possible to reschedule the El Clasico?
•  » » » 6 months ago, # ^ |   +43 I think we need to ask the officials of ERIC12138 and RealMadrid
•  » » 6 months ago, # ^ | ← Rev. 2 →   -10 Deleted
 » 6 months ago, # |   -13 So I can't watch the El Clasico.
•  » » 6 months ago, # ^ |   +4 So I can't participate in contest
 » 6 months ago, # |   -10 clashes with ieeextreme
 » 6 months ago, # |   -33 I actually have a college assignment due today, can this round get rescheduled to tomorrow?
•  » » 6 months ago, # ^ |   +14
 » 6 months ago, # |   -19 scoring distribution?
 » 6 months ago, # |   -66 Is it rated?
•  » » 6 months ago, # ^ |   0 No
•  » » 6 months ago, # ^ |   -6 It is clearly mentioned in the bold letters in the post that "**It is rated for the participant with rating lower than 2100**
•  » » » 6 months ago, # ^ |   0 You forgot to bold..
•  » » » » 6 months ago, # ^ |   0 I selected that B (Bold)option from the cf editor but it didn't work.Can you please help with this?
•  » » » » » 6 months ago, # ^ |   0 It is clearly mentioned in the bold letters in the post that It is rated for the participant with rating lower than 2100
•  » » » » » » 6 months ago, # ^ |   +9 How did you help him?
•  » » » » » » 6 months ago, # ^ |   0 Please explain how did you do that?
•  » » » » » » » 6 months ago, # ^ |   +5 remove the "
•  » » » » » » » » 6 months ago, # ^ |   +6 okay
 » 6 months ago, # |   -19 El classico or codeforces round 678??
 » 6 months ago, # | ← Rev. 2 →   -17 .
 » 6 months ago, # | ← Rev. 2 →   -17 .
•  » » 6 months ago, # ^ |   +11 Me, but I am not proud of it
•  » » » 6 months ago, # ^ |   -15 Well I'm not proud, I'm just trying to make my contribution to 0 but got downvotes xD
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   -16 I can totally understand you bro....I had -76 contribution on my other account once and had no hope of becoming it positive but now it is 70+ (+146) -> I got it in only two weeks..You have to be smart...not just comment anything..But again I am not proud of it..
•  » » » » » 6 months ago, # ^ |   +18 You are talking as if upvote count is some kind of a measure of your skills.
•  » » » » » » 6 months ago, # ^ |   0 sorry to disturb you..
 » 6 months ago, # |   0 this time is good for me.
 » 6 months ago, # |   0 No Ronaldo No Like
 » 6 months ago, # |   -13 when someone asks about score distribution:downvoters be like****:Today we will make your contribution hit a century in negative axis.
 » 6 months ago, # |   0 Wait if its rated till 2100 then the actual level of questions will be Div 1 I am not sure
•  » » 6 months ago, # ^ |   0 Even Edu Rounds are rated for those users.
 » 6 months ago, # | ← Rev. 2 →   +7 Codeforces : There is a contest at 17:xx MSK.Random user : The round clashes with 17:xx MSK. Is it possible to reschedule the contest?
 » 6 months ago, # |   +50 score distribution ?
•  » » 6 months ago, # ^ |   +1
•  » » » 6 months ago, # ^ |   +2 Busy watching El Clasico?
•  » » 6 months ago, # ^ |   +15 after the contest
•  » » 6 months ago, # ^ |   0 May be we have to wait till the contest started!
 » 6 months ago, # |   +3 Score Distribution Vladik ???
 » 6 months ago, # |   0 Will there be dynamic scoring?
 » 6 months ago, # |   +14 queueforces
 » 6 months ago, # |   +19 Why such a long queue for submission?
 » 6 months ago, # |   +4 what is the problem with prob A. you guys are changing prob statement while contest is going on. time to say goodbye to this contest....:)
 » 6 months ago, # |   +14 Getting unexpected error on submission for B.
•  » » 6 months ago, # ^ |   +13 me too
 » 6 months ago, # |   +9 getting unexpected error. can't submit b. what is happening????
 » 6 months ago, # |   +9 Getting unexpected error while submitting B. Please fix!
 » 6 months ago, # |   +9 not worth the frustration. going to eat dinner instead
 » 6 months ago, # |   +11 unable to submit solution :(
 » 6 months ago, # |   +14 This round should be unrated. Unexpected errors, long queue etc...
 » 6 months ago, # |   +52 I don't mind long queues, atleast everyone is on the same disadvantage. But this unexpected error puts people who solved the problem first on a disadvantage. Please make this unrated.
 » 6 months ago, # |   +80 Wow! I wonder how the good idea of making this round "RATED" even the submit was delayed for about 10 minutes LOL
•  » » 6 months ago, # ^ |   +19 How about make another Rated Round with 10 munutes delay together? It seems very good idea to make great round!
•  » » 6 months ago, # ^ |   +53
•  » » 6 months ago, # ^ |   +11 I am not sure but I think it is taken care of bcoz for problem B some people who have submitted after me have gotten more points thus compensating for the 10 min delay.
•  » » 6 months ago, # ^ |   +139 I've read the logs — the issue with the unexpected error during code submit was fixed in less than 5 minutes. Queues also were fixed quickly. Plus the longest time to judge was only 459 seconds (most submissions which faced a queue were judged much faster).Are you sure that less than 5 minutes of such a breakdown plus some queues at the start are worth sacrificing a month of work of problem writers?
•  » » » 6 months ago, # ^ |   +12 What's wrong with semi-rated? TL;DR 5 minutes makes a huge different for greens/greys.Personally, I made 5 attempts on problem B which probably took around 10 minutes longer becuase of queues. Since I only solved A and B (like a lot of greys and greens), this change made a huge difference.
•  » » » » 6 months ago, # ^ |   +10 What does semi-rated mean? How would that be implemented? Does the leaderboard change? Do the ratings get calculated against the ratings of people who drop out as well?
•  » » » » » 6 months ago, # ^ |   +13 All rating changes get cut in half.
•  » » » 6 months ago, # ^ |   +7 Testing round 17 before global round 11 seems a better idea for most of the contests.
•  » » » 6 months ago, # ^ |   -7 MikeMirzayanov Do you think people just kept hitting submit button for 5 mins straight or magically knew when the error was fixed and submitted in the very next moment? Even if the error was only for 5 mins, it has cost more time than that for most people. I'm sure there were some people who got frustrated seeing the large queue and left the contest as well. And about your question, 5 mins of breakdown + queues affect people a lot, especially during the beginning, so yes, it is indeed worth it.
•  » » » » 6 months ago, # ^ |   +11 MikeMirzayanov, I started with problem B today, because A looked too tough for me. After getting the implementation intact, I submitted my solution, and naturally it didn't submit. I left the contest out of frustration, because I saw people had already submitted A by that time. Now, I definitely agree that the setters did a lot of hard work, but at the same time, the starting five minutes of the round are much more valuable for a newbie/pupil. So, you should make this round semi-rated. I think it's a good compensation for both the setters and the participants. And, note that-regardless, this round will be unrated for me. So, I am actually unbiased over here.
 » 6 months ago, # | ← Rev. 2 →   -34 [deleted]
•  » » 6 months ago, # ^ |   -36 Instead of conducting many contests under Div2 and setting easy problems. Better Codeforces should conduct more contests as they are doing now, but the contests must be distinguished between Div 2 and Div 3 perfectly.Because it is sometimes disgusting to wait for Div 2 contest and the finding Div3 or Div4 level problems in the contest :(
•  » » » 6 months ago, # ^ |   +42 Lol mate, you've solved only 2 in this contest. Big words, though.
•  » » » » 6 months ago, # ^ |   0 I'm talking about all contests nowadays, not this one in specific:)
•  » » » » » 6 months ago, # ^ |   +37 What's the difference between Div3 and Div2 problems?
•  » » » 6 months ago, # ^ |   +8 Well it certainly does not contain Div3 or Div4 level problems(looking at your own submissions (you manage to solve only 2 in div3/4..certainly not)). The problems are great and balanced but the contest would have been better if there were no queueforces, delays etc.
•  » » 6 months ago, # ^ |   +1 See the thing is A is cakewalk, B is easy constructive, C is cool and enjoyable and D seems tricky...perfect for a Div2 contest.
•  » » 6 months ago, # ^ |   +47 I don't understand your point at all. You solved only 2 problems this contest, and took 30 minutes to do so. Didn't you need to think? What's bad about you solving 2 problems out of 6? Are you lacking challenging problems?
•  » » » 6 months ago, # ^ | ← Rev. 3 →   -71 [deleted]
•  » » » » 6 months ago, # ^ |   +35 You didn't even solve more than a single problem in your last 3 contests(2 were div 2) and now you are bullshitting this.
•  » » » » » 6 months ago, # ^ | ← Rev. 3 →   -37 [deleted]
•  » » » » » » 6 months ago, # ^ |   +28 Don't expect people to listen to you after writing from an alt xd U can't comment from your main id to decrease ur contribution If you understand your comment is good, write from main account. If it's bad, don't write it. If it's good but you would get downvoted anyway, then for sure contribution system is broken so don't worry about your contribution. So no reason to use an alt.
•  » » 6 months ago, # ^ |   +7 Bro see the difficulty level this was a perfect div2 contest. A require some brain as always it involves.B trick of just using 2 and 3 as prime numbers.C good problem gives you deep intuitions of Binary search . The way the binary search used was brilliant.D. DFS problem with a lot of insights and mathematics of finding averages and numbers.E Another cool problem involving a lot of thinking.F No idea.Also see the balance between the number of submissions. 'A perfect Div2 contest must look like this only!
•  » » » 6 months ago, # ^ |   0 but do u think nowadays contest is going good for high rated specialists or experts....If by luck u get late in even one of top 3 then ur rating is going to fall....I can see from ur case also....
•  » » » » 6 months ago, # ^ |   0 I don't know what you want ratings or practicing those hard problems If your option is first think once again!
•  » » » » » 6 months ago, # ^ |   0 so rating fall doesnt affect u..Rating seriously provides a motivation ..By the way I want to ask u,Isnt is better to judge candidate on the level of their skills rather than how speed he solved....some newbie could have solved first two qsns very fast and some coders let it be u take time in A isnt u get demotivated and panic on seeing ur rank to be 7000 for a moment...Isnt it better having question level something lik 800-1000-1300-1700-....
 » 6 months ago, # |   +26 I would be happy to have a like/dislike button for contests. So I could click there instead of writing bad comments.
•  » » 6 months ago, # ^ |   +6 The blog under which you are commenting itself has a upvote/downvote button. Why don't you use that
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Well, the problem with it is that it cannot be changed
•  » » 6 months ago, # ^ |   +1 Agreed, perhaps a rating for problems as well since a contest may be made of problems written by different writers. This will give feedback to the writers on what people find interesting (and what they dislike), and also help people prioritize better problems during practice.
 » 6 months ago, # |   +10 How to solve E?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +16 Traverse the array from 1 to r and maintain a segment tree of the last position of X. For each ar[i], find min(lpos(1),lpos(2),...,lpos(ar[i]-1)). If this is > lpos(ar[i]), then ar[i] will occur in the final array.Corner case : For 1 to occur in the final array, there must be a non-1 element in the array.
•  » » 6 months ago, # ^ |   +3 Didn't solve it during contest, but if you could find subarray mex queries in time $F(n)$ then to find if mex $x$ is possible for any subarray, consider all pairs of consecutive positions where $x$ lies, say $i_1, i_2$ for one, then you need to check if $mex(a[i_1 + 1, i_1 + 2..., i_2 - 1]) == x$. Since there are atmost $O(n)$ such pairs you can solve the problem in $O(n F(N))$. One way to solve subarray queries is using Mo's algorithm and keep elements not in current segment in a set, giving $F(N) = \sqrt{n} \log n$
 » 6 months ago, # |   0 what is the idea behind C?
•  » » 6 months ago, # ^ |   0 I think you can just keep track of the recursion and calculate how many numbers you can pick for position middle.
•  » » » 6 months ago, # ^ |   0 Thanks but can you elaborate more? what do you mean by recursion?
•  » » 6 months ago, # ^ |   0 Put x in position pos, and assume the array is decreasing before x and increasing after x (so it's in sorted order, with x in its spot). Now run the binary search and see how many numbers of this array it accesses. Say there are "l" numbers that it accesses that are less than x, and "r" numbers that it accesses that are greater than x. Then it suffices to find l numbers < x and r numbers > x to place in their correct positions. Then can rearrange the other numbers however. It follows the answer is $\dbinom{n-x}{r}\cdot r! \cdot \dbinom{x-1}{l}\cdot l! \cdot (n-r-l-1)!$
•  » » » 6 months ago, # ^ |   0 I did the same but wasn't able to get the sample test output. Can you please share your submission. Thanks!
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +3 https://carbon.now.sh/zit55zLD3opEedCifi1wMy accepted code with the same idea..
•  » » » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ |   0 Hey can you please take a look at my solution? I used the same logic. https://codeforces.com/contest/1436/submission/96608378
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 hint for n = 6 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +4 OR Just 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 in any value of n
•  » » » » 6 months ago, # ^ |   +15 For those who are interested, here's our short video with some logic that could have lead to this solution
 » 6 months ago, # |   +11 D, anyone stuck on pretest 7?
•  » » 6 months ago, # ^ |   0 I got runtime error on test 5?
•  » » 6 months ago, # ^ |   0 Yeah! Have u figured it out?
•  » » » 6 months ago, # ^ |   0 int overflow
•  » » 6 months ago, # ^ |   0 I did for a while, then got stuck on pretest 4 on later submissions >:(Some things I fixed to get AC (no clue which caused the WA): Only add single direction edge from $p$ to $i$ instead of adding it in both directions and storing parents of nodes (this shouldn't have made a difference but it did) Depending on how you calculate the answer, intermediate calculations can overflow long long, so I switched to __int128.
•  » » 6 months ago, # ^ |   0 Pretest 7 was when there is only one child of 1. After correcting my mistake in this case my solution passed pretests
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Would you kind enough to share the case? Hopefully, my solution produces the correct output for this type of case. solution(WA on test7)
 » 6 months ago, # |   0 Does there exist an easier way to find subarray-mex-queries (i.e, given $l, r$, find mex of $a[l...r]$) other than Mo's?
•  » » 6 months ago, # ^ |   +5
 » 6 months ago, # |   0 How to solve D?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +17 The answer is the maximum of ceil(sum/sz) for each node. Sum denotes the sum of all a[x] in the node's subtree, and sz denotes the number of leaves inside node's subtree.I don't have a rigorous way to show this but this informal explanation is sort of intuitive if you think about it.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Damn I got it at the end of contest but couldn't code...This problem was a bit confusing, I had to read it again and again.
•  » » » 6 months ago, # ^ |   0 I see your logic, but can't we just simulate the process using bfs and keeping track of updated a[] values ?
•  » » » 6 months ago, # ^ |   0 I see. I will try to prove it myself before tutorial.
•  » » » 6 months ago, # ^ |   0 Proof : This an obvious lower bound. We just need to show that this can be constructed. Let us show this by induction on subtrees. This is obviously true for a leaf. Now let's show that we can create a root node, and join subtrees that this condition can still be satisfied. Let us move all the values on the subtrees to their leaves in the optimal arrangement. Now consider where the people in the root node go. Let's say the maximum value of a leaf in the optimal arrangements of the subtree is $m$. This is also equal to $max(sum(v)/leaves(v))$ for all immediate children $v$ since we are showing by induction. We can add to the leaves with smaller values until we reach $m * leaves(u)$. If we reach this point, that means that $sum(u)/leaves(u) >= m$. Now we can put the values one by one, and reach the optimal arrangement.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Damn that's smart, thanks.Also Tairitsu best.
 » 6 months ago, # |   0 How to approach problem C?
•  » » 6 months ago, # ^ |   0 https://codeforces.com/contest/1436/submission/96577050Try it before system tests =))
•  » » » 6 months ago, # ^ |   0 Can u please help me in finding the error?Thanks in advance here is my code https://ideone.com/gRTOIo
•  » » 6 months ago, # ^ |   0 "Simulate" binary search, at any iteration if the middle is lower than pos the in this position there should be a number lower than x, if middle is greater than pos then the number should be grater than x, so you can multiply the options for the values at each value of middle. When you reach posthen the posibble rearangements of the numbers that u did not use yet is just it's permutation
•  » » » 6 months ago, # ^ |   0 please share your code, because I have used the same idea but got WA on pretest 4
•  » » » 6 months ago, # ^ |   0
 » 6 months ago, # |   0 Lesson Learnt from this Contest: Long Queue and Submit button not working doesn't guarantee you an Unrated Contest
 » 6 months ago, # |   +2 Since when the problems are so difficult? last time I participated was like 6 years ago. :(
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I feel contests are getting harder and since lockdown, the competition has increased substantially i.e from around March onwards.The level of difficulty has certainly increased( I find old problems of same rating to be easier and I think thats also because of how many people are doing that during contest and it's position) since the competition and no. of participants has increased a lot.But anyways, with some practice you will be well off. Were the problems more Data structure/algorithm oriented earlier?
 » 6 months ago, # | ← Rev. 2 →   +12 In D, my O(n*log(U)) solution kept TLEing until I changed long longs to int.
•  » » 6 months ago, # ^ |   0 i think test case of C is designed to attack O(nlogn) solution
•  » » 6 months ago, # ^ |   0 Wouldnt it give WA when sum will exceed int bounds?
•  » » » 6 months ago, # ^ |   0 I meant variables that would not overflow, ex. n, p
•  » » 6 months ago, # ^ |   0 I just gave up and wrote the $O(n)$ solution after my $O(n \times log(U))$ solution got TLE twice.
 » 6 months ago, # |   0 If I submit a solution which passes the pretests and again after sometime I submit another solution to the same problem which again passes the pretests, then my last correct submission on the problem is considered or the first correct submission ?
•  » » 6 months ago, # ^ |   0 Only the last one.
 » 6 months ago, # | ← Rev. 2 →   -9 RIP queue
 » 6 months ago, # |   +13 I forgot to print newline in my first submission of problem B and the solution was in the queue. Expecting WA on pretest 1, I submitted again but both passed and I got a resubmission penalty. Can anything be done about it?first submission: 96543626second submission: 96544467
•  » » 6 months ago, # ^ |   0 i dont think so.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 Yeah happened with me for C, got a resubmission penalty and last submission was considered so overall a good negative in total score.
•  » » 6 months ago, # ^ |   0 Man… I did B in 13 minutes and I resubmitted after two hours a better solution, just to make sure it will pass the official tests. I didn't know that only the last submission counts. Now instead of +25 I get -60.
 » 6 months ago, # | ← Rev. 2 →   0 Can someone explain why i am getting Runtime error in pretest 3 of problem CMy solution 96588906Thanks in Advance :)
•  » » 6 months ago, # ^ |   0 Try including a value for fac(0) as well.
 » 6 months ago, # |   +20 The problem E is a problem of 2013 ICPC Hangzhou online.http://acm.hdu.edu.cn/showproblem.php?pid=4747BTW,I'm in Hangzhou now so I am familiar with this problem.
 » 6 months ago, # |   0 how to solve C?? need hint and ovservation.thanks in advance.
•  » » 6 months ago, # ^ |   0 Think about the order of the binary search. Every position in the array has a distinct binary search order. By tracing the direction of the B.S., you can reconstruct possible values for each "middle" position.
•  » » 6 months ago, # ^ |   0 Just stimulate a binary search and check the path that binary search follows in there and count smaller and bigger for x during that simulation. After that its simple PnC .
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 in binary seach we make jumps from mid to val that we need..., so when ever we come to some point. we just need to check weather to jump forward or backward.to jump foreward we need to put some value at that cell that is less than x. choices that we have is n-x for this cell in array. to jump backward we need to put some value at that cell that is greater than x. choices we have is x-1.now if you make two jumps forewards, choices to put values in those cells are n-x for first cell and n-x-1 for next cell. total choices are (n-x)*(c-x-1)after you fill and calculate all cells where you jumped. the permutation of remaining cells doesn't matter. you can permute all the rest of cells. eg 4 1 2we jump to 2 (4+0/2).val[2] == 1(x) [it is given value at 2 is 1]choices that we have to fill jumping indexes is 1 (only 1 was filled no other choice).ans = 1 * fac(3), [3 is number of cells whose value doesn't matter]ans = 6
 » 6 months ago, # | ← Rev. 4 →   0 [DELETED]
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 its strange because as i checked it doesn't ouput correct on the test below16 92759 72 10 90 73 72 75 47 30 59 90 16 76 82 48 28it outputs NO while the correct answer is YES|:
 » 6 months ago, # |   -24 O(n^2) solution didn't work for E ? I thought that for n = 10^5 , it should be fast enough
•  » » 6 months ago, # ^ |   0 No, it won't pass because you can probably do 2*10^8 low level operations per second in cpp.
•  » » 6 months ago, # ^ |   0 n^2 for n=10^5 would mean 10^10 operations which gives TLE.
 » 6 months ago, # | ← Rev. 3 →   -10 sorry
•  » » 6 months ago, # ^ |   +4 Hmm. So 10 minutes of queue affected your chances at trying ABC, and therefore you couldn't solve them? Don't talk bs man.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -10 Sorry again
•  » » » » 6 months ago, # ^ |   +6 that is your personal issue.
•  » » » » » 6 months ago, # ^ |   -7 nope bro actually its an issue...if u are going to get good plus doesnt means that contest standard hasnt fallen down
•  » » » » » » 6 months ago, # ^ |   +9 i meant that "saying something disturbed his mental peace" is his own issue. he cannot blame it on that "something".
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -7 sorry
•  » » » » 6 months ago, # ^ |   +6 you need to work on your "mental peace" then.
•  » » » » » 6 months ago, # ^ |   -6 Obviously ;)
 » 6 months ago, # |   +8 Can we solve D using binary search??
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 I tried using binary search. But got various results except AC. My idea : Binary search on the minimum no. of citizens bandit can catchSo, basically i fix the answer and check if its valid or not.https://codeforces.com/contest/1436/submission/96583528UPDATE : I understand that its failing because of overflow.Each leaf can take atmost 2e14 citizens. So, we carry forward 2e14 to 1e5 nodes. So, the value goes to 2e19 which leads to overflow.
•  » » 6 months ago, # ^ |   0 Yes, you can. 96579469
•  » » » 6 months ago, # ^ |   0 what is your valid function of binary search?valid in the following sense: lo=0,hi=n; while (lo
 » 6 months ago, # |   0 Hello there, can anyone help me with approaching problem C? I'm a newbie so please bear with me.Here was my idea but seems like something is wrong here:for example, for the testcase 123 42 24,to reach 24th position, we need to go via 61st, 30th, 15th, 22nd, 26th, 24th positions.And we can have 41(<42) numbers on position 61, 40 on position 30, 81(>42) on position 15, 80 on position 22, 39 on position 26, and 1 on position 24(i.e. 42) and the rest of the numbers shuffle in remaining positions. Therefore, 117!*39*40*41*80*81 % (1000000007) should be the answer.
•  » » 6 months ago, # ^ |   0 We will go like this 61 30 15 23 27 25 24
•  » » 6 months ago, # ^ |   0 First, if you use the pseudo code provided, the positions are 61, 30, 15, 23, 27, 25, 24.Second, if a position is to the right of pos, you should use numbers that are greater than x, since you want to go to the left. Similarly, if a position is to the left of pos, you should use numbers that are less than x, since you want to go to the right.So the answer is actually 116! * 81 * 80 * 79 * 78 * 41 * 40 Check.
•  » » » 6 months ago, # ^ |   0 Damn! Probably miscalculated due to frenzy. I was right all along. Wasted 30 mins on this :( Anyways thanks a lot for explaining!
•  » » 6 months ago, # ^ |   0 Well tbh I didnot read your approach but I will try to explain it to you easily....Notice that we only need to constrain logN number of positions. This is because in binary search there are logN steps to reach target each step follows a specific sequence of path to reach the target. This sequence of path is determined by the classic BS alg as given in problem. Now if your target pos is greater then mid that implies the element at mid must be less then x(inorder for BS to go right) and vice versa. Count the number of such positions where the element is constrained to be less then x and vice versa. Answer can be found using simple combinatronics.Here is my submission : C//Think simple yet elegant. #include 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 #define REP(i,n) for(int i=0;i fact(maxn,0); ll bin(ll a, ll b) { a%=mod; ll res = 1; while (b > 0) { if (b & 1) res = res * a % mod; //mod a = a * a % mod; //mod b >>= 1; } return res; } void fac() { fact[0]=1; for(ll i=1;i> n >> x >> pos; ll l = 0; ll r = n; vector a(n,0); while(lm){ a[m]=1; //x r=m; } else if(pos==m){ a[m]=-1; break; } } ll low=0,high=0,nue=0; for(i=0;i
 » 6 months ago, # | ← Rev. 2 →   +5 In problem E, why doesn't DSU work? I kept getting WA on TC 3.Edit: Nvm, I found my mistake.
•  » » 6 months ago, # ^ |   0 same here
 » 6 months ago, # | ← Rev. 2 →   -7 Honestly, I don't like Problems which are directly dependent on slight variations of standard algorithms. For problem C, I always update right as middle-1 and not middle itself. So during the entire contest, I tried debugging but couldn't figure out that it was a simple misreading of the Problem statement.
•  » » 6 months ago, # ^ |   +4 But you should just follow the recursion given by the code in question.
•  » » 6 months ago, # ^ |   +6 Just because you don't implement an algorithm the way it's written on the problem doesn't mean it isn't standard. Using [l, r) instead of [l, r] is not a "variation of standard," it's just another way to implement it.
•  » » » 6 months ago, # ^ |   -6 I agree it was my mistake to misread. My point is different people implement standard concepts in different ways. So I personally dislike those Problems where the authors implement their version of the standard concept and we're forced to work accordingly. Anyways, lesson learned!
 » 6 months ago, # |   0 What is wrong with my code on problem D . wrong answer on testcase 7 96592768
 » 6 months ago, # |   0 When I want to submit my code, it says you did not register for the contest. Did I really forget to do that or is it just a system problem?
 » 6 months ago, # |   0 https://codeforces.com/contest/1436/submission/96590709 problem c ,error on pretest 3. i dont know where is the error,any suggestion?? what i did is a! * b! * c! * d * e a=total moves to get to required position that is pos using binary search b=moves where mid < pos c=moves where mid > pos d=bC(x-1) e=aC(n-x)
•  » » 6 months ago, # ^ |   0 check for n = 1.
•  » » 6 months ago, # ^ |   0 The idea behind all of this is a bit math-y, but division and modulo don't play well together. Take for instance (6/2)%4, the correct answer is 3. However, if I first take the modulo of the numerator, then of the denominator, and then calculate, I get 2/2 = 1, which is not correct.In func, when you have for(long long i=1;i<=x;i++) { ans*=(n-i+1); ans/=(i); ans%=mod; } a similar problem may happen. You base your code in the fact that ans * (n-i+1) is divisible by i. This may be true if you didn't have a modulo, but since you modulo every step of the way, it may be the case where this isn't true and you end up with an incorrect answer.To calculate (nCk), use Pascal's Rule, nCk = n-1Ck + n-1Ck-1 or multiplicative inverses instead.
 » 6 months ago, # |   0 I wasted 30 minutes in C just to realise in the end that my code was failing at n = 1 .(Sad reacts only)
 » 6 months ago, # |   0 Hello! Can someone please help me, I don't understand what is wrong with my solution: https://codeforces.com/contest/1436/submission/96569147 My approach is to get 2 as the sum on all rows and columns
•  » » 6 months ago, # ^ |   +4 Since the problem is multi-test, you should reset any global variables before/after each test case. For instance, n=4 leaves you with 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 if I'm not mistaken, but if the next test case is n=6, you're left with 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 
•  » » » 6 months ago, # ^ |   0 Oh yes, Thanks!
 » 6 months ago, # |   +1 weak pretests on C, stupidly missed an obvious mistake and it passed.
 » 6 months ago, # | ← Rev. 2 →   0 Damn My B will FST as I mistakenly saw n<100 .!Passed but how?Wasnt there n=100 as test case by the way big case for me.
 » 6 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1436/submission/96589733 Can anyone tell what is wrong in this? Problem D using binary search
 » 6 months ago, # |   0 FSTs on C incoming!!
•  » » 6 months ago, # ^ |   0 lets have a good night's sleep then before rating changes.
 » 6 months ago, # |   +6 Is it just me who thinks that A & B were too easy for Div2?
•  » » 6 months ago, # ^ |   0 Yes
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 B probably wasDisagree regarding A, quite a typical A
•  » » » 6 months ago, # ^ |   0 Totally Agreed
 » 6 months ago, # |   +16 Disappointed as this contest had less number of pretests and the pretests were weak!!
 » 6 months ago, # |   +1 FSTforces. Cool problems though.
 » 6 months ago, # |   +4 I am not claiming that the round should be unrated, but let me tell you one thingFor A, i checked if the sum of the array is a multiple of m , it passed the pretests and later i got hacked and lost 350 pointsFor C, i submitted and got Runtime Error on test 79....So yeah sad contest for me!Cheers all! Kinda sad a good contest was turned into a worst one(for me)!
 » 6 months ago, # |   -34 hi guys. right now my solution for c is in queue, if my problem c got accepted you all can downvote this comment so hard!!. but if my solution got failed please upvote(it will make me feel better). and i think its funny to do such things. you will probably see more of these comments from me XD
•  » » 6 months ago, # ^ |   +19 Goodbye my friend.
•  » » » 6 months ago, # ^ |   +11 goodbye contribution. im so stupid XD
 » 6 months ago, # |   0 What is test 10 in C ??!!! I dont see why my solution would fail :(..Anyways I fastforced A and B so my rank went up lol.
•  » » 6 months ago, # ^ |   +3 Their binary search algorithm is really dumb, if you look at the code in the problem their algorithm keeps going even after it finds middle...If it's any consolation, I and many others FST'd for the same reason :(
•  » » » 6 months ago, # ^ |   +8 OMG! I didnot even look at the algorithm and just assumed it was a normal BS(Binary search). But turns out their BS was actually BS(Bu*lsh*t).
•  » » » » 6 months ago, # ^ |   0 I didn't understand answer of test 10 for C. :( . The test was-- 3 3 1 I printed 2, they said, it will be 0. So, aren't following permutations okay? 1 3 2 and 2 3 1 ???
•  » » » » » 6 months ago, # ^ |   +1 Yeah run these permutation against their algorithm....1 3 2 -> L : 0 and R : 3 and MID : 1It should stop here XD..but it still goes on due to stupid L.
•  » » » » 6 months ago, # ^ |   0 There is no such thing as "normal BS" Obviously bs can go different paths depending on the implementation.
•  » » » » » 6 months ago, # ^ |   +3 By normal BS.. I meant the one which usually stops when an element is found and doesn't go around frolicking.
•  » » » » » » 6 months ago, # ^ |   0 Funny thingBecause I always write BS that "goes around frolicking" instead of stopping when the element is found.
•  » » » » » » » 6 months ago, # ^ |   0 Good for you.
•  » » » » » » » » 6 months ago, # ^ |   0 well, ok, it does not really frollic. But it does not stop. The point is that there are different implementations and should've written the answer for the given implementation, not for the one in your head.
•  » » » » » » » » » 6 months ago, # ^ |   0 Ok sensei.
•  » » 6 months ago, # ^ |   0 n=1 i think
 » 6 months ago, # |   +7 This pretests...
 » 6 months ago, # | ← Rev. 2 →   +19 Damn, I failed systest in D because I said $10^9*10^5 = 10^{13}$, and also in E because I used a segment tree of size $n$ instead of $n+1$. If this contest was rated for me, I would be drowning with my own tears :P
 » 6 months ago, # |   0 One test Case , One Damn test Case and more then 1000 people got their rank dropped by 1000+....
 » 6 months ago, # |   +15 Weak Pretests, Long Queues, Unexpected Errors and Rated :(. Make it Unrated :P
•  » » 6 months ago, # ^ |   +14 I understand that the authors worked very hard for preparing this contest, but the issues are really too big to ignore at this point.
•  » » 6 months ago, # ^ |   0 I completely agree, Most of the FSTs could easily be resolved if only the verdict was WA instead of pretests passed.
 » 6 months ago, # |   +12 What a blood bath in Problem C!
 » 6 months ago, # |   +4 I've never seen a contest with pretests this bad for almost all problems
•  » » 6 months ago, # ^ |   0 The thing is this contest is a "based contest" .. I just wonder what happened with the people who gave this in official time
•  » » » 6 months ago, # ^ |   0 what is a based contest?
•  » » » » 6 months ago, # ^ |   0 Problem in this contest were from a official competition mention in the title of this blog and hence we say that this contest was based it. Moreover It was a final man.. RIP My C "pretest passed" :/
•  » » » » » 6 months ago, # ^ |   0 its funny how every one made same mistake of stopping iteration on stisfying mid rather than both limits.
•  » » » » » » 6 months ago, # ^ |   0 It even funny that not only we both but many many many people did same ......
•  » » » 6 months ago, # ^ |   0 Well, "based" contests, contests with some names in titles and contests with specific sponsors often have their peculiar features. While not all of them are perfect, they add some diversification to rounds
 » 6 months ago, # | ← Rev. 2 →   +61
•  » » 5 months ago, # ^ |   0 Can't stop laughing. it's unique.
 » 6 months ago, # |   +5 Why mathforces...
 » 6 months ago, # |   +8 Not expected such bad pretest! Good contest turned worst , long queue, bad pretest ...
 » 6 months ago, # |   0 I hope they don't make the round unrated. Even if it had some problems.
 » 6 months ago, # |   +2 Goodbye color, hope to cya soon...
•  » » 6 months ago, # ^ |   +5
 » 6 months ago, # |   +2 weak pretest for DIV2 B
 » 6 months ago, # |   0 While I agree that the contest had its problems, I don't think that "weak pretests" should ever be considered a serious issue.
•  » » 6 months ago, # ^ |   0 I'm biased because I have a positive delta, but I agree. There were 5 pretests on C and 7 on D. Pretty obvious pretests are weak.
•  » » 6 months ago, # ^ |   +5 You are saying that cause you didn't Failed any problem on ST
•  » » » 6 months ago, # ^ | ← Rev. 4 →   0 I always say that. Not only in this contest.I believe people rely on pretests too much and it is their mistakeIt is true that I haven't failed on ST. In fact I have only failed on ST once for all 50+ contests I took (yes, I was sad when it happened, but it never came to me to ask to make the round unrated because of that). What does it mean? Probably I think about corner cases more then others, I dunno
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Agreed on that. But, we are wanting to make this contest reason due to a bigger reason other than having weak pretests. I started with problem B today, because A looked too tough for me. After getting the implementation intact, I submitted my solution, and naturally it didn't submit. I left the contest out of frustration, because I saw people had already submitted A by that time. Understand that we are talking about this issue. Don't trivialize it by talking shit about weak pretests. I understand that you might get to CM after this round, because you didn't FST. But, don't lose your conscience and start acting like an asshole. Apologies if I sounded too rough, but I am calling like I see it. And by the way, this round(rated or unrated) is the same for me either ways. So, I am actually unbiased over here, unlike you.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 So, I am actually unbiased over here, unlike you.I left the contest out of frustrationYeah, totally unbiased.
•  » » » » » » 6 months ago, # ^ |   0 Well, I am unbiased in terms of this round being unrated for me regardless. I don't have anything against the setters. I thought the problems were still nice. My problem lied in the technical issues that transpired. Anyway, if you still feel like giving a nice sarcastic comment, feel free to do so, brother! :)
 » 6 months ago, # |   +2 i know i was stupid to break when i found the match , but man the pretests for "C" just sucked.
•  » » 6 months ago, # ^ |   0 Did you get why the answer to test10 is 0 ?
•  » » » 6 months ago, # ^ |   +1 my code failed on testcase 10 but i don't know why. I this its answer should be 2 not 0
•  » » » » 6 months ago, # ^ |   +1 Yea I just did, change the break statements in your submission and then see the magic
•  » » » » 6 months ago, # ^ |   +1 check their binary search. you've put if mid==pos, return; which is not the case actually acc to problem.
•  » » » » 6 months ago, # ^ |   0 I got it
 » 6 months ago, # | ← Rev. 3 →   +5 in third question for testcase 3,3,1 my output is 2 why is it wrong there are two possibilities for 3 at pos 1 1. 1 3 2 2. 2 3 1
•  » » 6 months ago, # ^ |   +1 The pseudocode they have given in the problem is a bit different. It does not find 3 at position 1 in the possibilities you mentioned.
•  » » » 6 months ago, # ^ |   0 I got it
 » 6 months ago, # |   +8 why is answer to this case 10 : "3 3 1" 0 .. Cant we have 2 3 1 and 1 3 2 ? Clarify where am I going wrong
•  » » 6 months ago, # ^ |   0 Elements at both index 1 and 2 are processed before the search stops. So, arr[2] must be greater than arr[1] to direct the search to the middle. However, this is not possible since 3 is the largest number in the permutation. So the answer is 0.
•  » » 6 months ago, # ^ |   +7 For the case of 2 3 1. First, it will set l = 0 and r = 3. Then, it will set mid = 1, check it, and update l to 2 since a[mid] is equal to 3. For the next iteration, mid=2, check, and l will be updated to 3 since a[mid] equal to 1, which is less than 3. Then, the loop is over, check a[l-1] you will get 1 instead of 3.The same scenario happens for the case of 1 3 2.
•  » » » 6 months ago, # ^ |   +1 Yes sir I just realized that I am so dumb that I put a break statement there. Oh man I am so dumb :(
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Anyway, the pseudocode itself use the right-exclusive style of indexing (I don't know the usual term, but I always call it that way), which instead of pointing the element, the index is used to point the room divider (barrier between two element). That's why in the beginning it sets l = 0 and r = a.size(). This way of viewing array is useful for the case of splitting array, so instead of being confused of using mid - 1, mid, or mid + 1, you can directly use left to mid and mid to right.
 » 6 months ago, # |   +7 Someone explain for C testcase 10, why for 3 3 1 the solution is 0 ? for this case mid will be at 1, so after putting 3 in 1, we can arrange the remaining elements in 2! ways i.e 2, since the other elements don't matter. So why 0?
 » 6 months ago, # |   +1 Pretest Sucks a lot. I lost two problems.
 » 6 months ago, # |   +3 idk if this was on purpose, but thx for nice time limit in D. My binsearch solution got 1341 ms.
 » 6 months ago, # |   0 Solved B very late. Any suggestions for me?
•  » » 5 months ago, # ^ |   0 Practice and Practice!!
 » 6 months ago, # |   +5 I didn't understand answer of test 10 for C. :( . The test was-- 3 3 1. I printed 2, they said, it will be 0. So, aren't following permutations okay? 1 3 2 and 2 3 1 ???
•  » » 6 months ago, # ^ |   0 0-based indexing
•  » » 6 months ago, # ^ |   0 The binary search is given in the question is slightly different ;_; The loop will run two more times and final value of left will be 3.
•  » » 6 months ago, # ^ |   0 Same doubt !!?
 » 6 months ago, # |   +1 Did anyone fail in Test Case 52 in problem C? Can someone explain me why am i failing this testcase
•  » » 6 months ago, # ^ |   0 I failed 51 because I forgot to take mod after 1 step. I think I am retarded.
 » 6 months ago, # |   +1 Problem C: can anyone explain test case 3 3 1 my code is giving 2 but the answer is 0.
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 So there are two permutations1 3 22 3 1Regardless of which one you consider bs will pick at 3 and move the left pointer forward So you have left=2, right=3 Then you check arr[2] (1 or 2) and bs tells you the answer is on the right, where it does not exist
•  » » » 6 months ago, # ^ |   0 thanks man
 » 6 months ago, # |   +1 why in c problem for test case 3 3 1 output is 0 ?It should be 2 , Am i right?
•  » » 6 months ago, # ^ |   +1
 » 6 months ago, # |   0 I am just feeling dumb, as I didn't submit A even after solving it, assuming that I sumbitted it and rushed to B.
 » 6 months ago, # |   -34 This contest should be unrated. I did not like it. In the starting, it took a lot of time to know the verdict. I submitted 2nd question thinking that it will be right and moved forward to 3rd question as getting the verdict was taking a long time. When I solved question 3 after then I came to know that I have already got WA on 1st pretest. This wasted my 10 minutes !! Even after then I successfully passed pretests of 3rd, but in the final checking, it gave WA on test 10. Pretests were weak and few, may be to reduce the load on the server. That's not a good idea. Completely disappointed after giving this contest!! RIP RATINGS !!
 » 6 months ago, # | ← Rev. 2 →   0 Did anyone else's D fail on test 78? If so what was the mistake you were making? My Submission
•  » » 6 months ago, # ^ |   0 Edit: Got AC, was not computing the room left after raising max correctly. AC submission- 96827495
 » 6 months ago, # |   0 Input 3 3 1 Participant's output 2 Jury's answer 0Can someone please explain this test case to me, because I feel 1 3 2 and 2 3 1 are good but the jury's answer is 0
•  » » 6 months ago, # ^ |   0 This is for question D
•  » » 6 months ago, # ^ |   +3 It seems like its for question C.If you see original pseudocode implemented on the statement, you can know that you should not get out of while if pos == mid.Neither am I know why did author implement binary search like that... but that's the reason.
•  » » 6 months ago, # ^ |   0 I'm sorry it's for question C
 » 6 months ago, # | ← Rev. 2 →   0 Can someone help me find out the problem with my submission to Problem A? My submission 96540614 is failing on test case 29.
•  » » 6 months ago, # ^ |   0 Do you think this is true?1.0f + 1.0f == 2
•  » » » 6 months ago, # ^ |   0 Yeah, it is.See this.
•  » » » » 6 months ago, # ^ |   0 1/3 can't be expressed exactly in decimal system it can be expressed exactly in a system with radix 3. Similarly, Binary also stores some decimals only to some level of precision.They should be avoided whenever possible, here there is an alternate way. The sum asked is simply the sum of all elements in array.
•  » » » » » 6 months ago, # ^ |   0 YeahThanks, for the information.
 » 6 months ago, # |   0 Can problem A have a possible arrangement such that the sum is not m but it is still ok ?
 » 6 months ago, # |   0 Still wondering what was the reason for queue
 » 6 months ago, # |   +15 For those who are interested in problem B analysis here's our short video with some logic that could have lead to a common solution.