Hi everybody,
This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594).
Round will be held at Feb/23/2020 12:05 (Moscow time). You will be given 5 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.
Problems are prepared by KiKoS, DebNatkh, grphil, Sehnsucht, voidmax, isaf27 under my supervision.
Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.
Good luck everybody!
UPD1:
Scoring distribution: 500 — 1000 — (1000 + 1000) — 2000 — 2500
Due to the official competition source codes of other participants will not be available for an hour after the end of the round.
UPD2: Winners!
Div. 2:
Div. 1 + Div. 2:
UPD3: Editorial
Nice!The start time of this contest was very friendly to the Chinese. :-)
It's hard to see the round at this time.I hope it's easy.
Why are Chinese always ranting about start time smh ?
Most rounds start at 9-10 pm in China, which is quite late for some people
Yes, it's very friendly to the Indians as well.
Hope every Chinese who will take part in gets good grades
I still have questions...
It can be a new contest format or something like global rounds(div.1+div.2)
Not colorful testers, but good testers.
is this rated contest?
of course :)
how did you know is it written somwhere? Please tell me
5th line of the blog. you will get it. In shaa Allah
I just wanna be specialist again, so I hope it will be easy to solve C at least :)
all the best :)
Keep pushing and Good Luck. You'll be the best. And I wanna becmoe purple too :).
Seems like you have been granted your wish ...
Yep. Becoming a candidate master is the gladdest thing in these days. And good luck && high rated for you in next contest.
How do you think about (1250+750)? Perhaps solution of Problem C will be short but difficult.
bonne chance
3am for people in North/South/Central America, but I'll surely do a virtual participation when I wake up :). Good luck everyone!
It's been a long time for Chinese to participate in a proper time.:-D
why do some of the rounds listed have div1 while some don't?
as lots of people can make div.2 problems, but div.1 is something else, much harder and much more important. also if you can make div.1, then you will add two simple problems to it, then it would be div.1 + div.2, but you cant add div.1 E/F that much easily. and its the reason that we dont have too many div.1 only rounds, but we have lots of div.2 + div.1 rounds and more div.2 rounds.
One year after Codeforces Round #541?? And the same author?
Because it's based on annual event; see round 342, 401, 466, 541.
Opencup and round at the same time, not cool man, not cool
It's sort of crazy to have two rounds one after another, with an interval of only a couple of hours. I'm so excited! LOL
have the same feeling :), what if we participate in this round as a warm up for the next one?
The second round is, however, time-unfriendly to Chinese participants. Rounds like this one are known as "sudden death round" among Chinese OIers since they're in the midnight. I guess my parents won't let me take part in this round. (sad face
i havent ever seen a cf round that has bad start time for us, love Iran :D, this contest was 12AM, and the normal cf round are about 6PM here
Damned. We almost always have to burn the midnight oil to take a cf round.
Let's hope this contest has some actually good problems and not some garbage with cows everywhere.
Disagreed. Cows aren't making problems garbage. I think they are making them easier to understand.
Wish to see questions with good learning aspects.
Nice! The start time is great!
All the best everybody.
Lol, score distribution can be really useful for on-site participiantes, You know
Please let me add 5 points
The only way is to do your best in the contest.
+9 QAQ
The start time is so nice to Chinese! Hope to be a Master or a Candidate Master!
Yeah <3 I am ready and exiting to join the contest !
Hope that I can solve C or D ;-;
No Legendary registered!!!
Thanks for the Round, but I left when I failed to solve pretests for problem-A , and didnt even understood problem-B in first 30 mins :(
That's goodbye rating for you my dear son.
How come...??? Why would I make a submission if I haven't solved for the pretests.
it's too early to give up. your rating doesn't make any sense if you give up like this.
Question plz! Why is this contest Div.2 instead of the first five problems of Div.1+Div.2?
B is very nice. It should've been C though.
Annoying B.
I love these "difficulty staircases" you make after every contest
D̶i̶v̶ ̶2̶ ❌
Div1/1.5 ✔️
haha :D
I cant solve B for 2 hours ;-; How stupid I am for a math problem
dude i couldnt solve problem B, look at my rating, so that i gave up writing the segment tree on C2 and left the conest :(, the gravity is pulling my rating to newbie
Are you going to drop the rank like I am now ? ;-;
I know
B is not always easier than C
but I still try all of formula I can think to solve B first and I failed ;-;New experience for me:
Change problem if you think you cant approach furthur although you tried your best for an hour
;-; What a math problem ;-;I hope we will rank up the next contest :D Good luck <3
thx dude, no hard-feeling, its just a contest which wasnt good for us, maybe next round well get +300 rating(shotor dar khaab binad panbe dane)
Good luck ! Hope I can solve A-B-C and get +50 too
And I solved A-B-C <3, how about you
But I didn't feel too good, since it took me 40 minutes to understand B, and I submited wrong code for C because I was hurry ;-; If I have more time, I hope I can still solve D <3
How to solve C2???
B is a very nice problem :)
No, it is a horrible index fiddling with absolutly nothing to learn. You might be happy if you solve it, but that does not make it nice.
Not the solution. I meant the idea of the problem is nice. I agree. There is nothing to learn from it.
is the solution of C2 segtree+binary search.got tle with that
instead of seg tree do sparse table
Alternatively you can use a stack and just pop whenever you reach an element greater than the current, kind of like 2 pointers.
i know ! but if you dont want to use any ideas you can just change the O(logn) finding minimum with seg tree to O(1) with sparse ! memory fits too . so instead of n log^2(n) it becomes n log(n)
i used stack: https://codeforces.me/contest/1313/submission/71676035
For each position
i
you should calculate the total size of increasing buildings ending at that position.Which is equvalent to the Next smaller element problem.
My solution is O(n), you can count all values using stack
Simply segment tree will do
Can you explain the Segment Tree approach for C2?
for each element , we need the closese element on the left of it and on the right of it that has value less than equal to it.So maintain a minimum seg tree and for left and right both elements for each index, do it seperately. For elements in between ,they contribute value equal to element value to its answer. For the rest of elements,answer is already found before. Say for left partition, ansL[i] = ansL[left] + arr[left] + (i-1-left)*arr[i].Same is done for right partition. And then ans[i] = ansL[i] + ansR[i] + arr[i].
No. It is sth like lineral dp + non-decreasing stack. The time complexity is O(n). Plus, I think n=500000 is aimed at preventing some O(nlogn) solution.
I used a different approach.
I built the cartesian tree of the array in O(n). Basically, each subtree represents a contiguous sub-array. And the root of a subtree is the index of the minimum element of the subarray. It's left and right childs are respectively the sub-array to the left, and to the right of the min.
Once I have that, I compute the solution for each subtree. Noticing that the buildings size must be constant either on the left subtree, or the right subtree. So I can calculate the answer in O(n) for all subtrees.
You can do binary search on the segtree and use logn time instead of log^2n. You can check my submission https://codeforces.me/contest/1313/submission/71698666
It can be done using a stack. First, we calculate the maximum score we can make from the left side (all buildings in non-decreasing heights) and the right side (all buildings in non -increasing heights). We can do this by maintaining a stack with increasing values. Then taking maximum among all index for left[index-1] + right[index].
Link
how to solve c1 ? i got wrong answer on pretest 3 my code: 71682077
Try putting each element as peak element and the left part forms a increasing segment and the right part a decreasing segment, compute maximum answer for all peaks, and then take the maximum one.
How to solve B?
Form min place let $$$lx = min(n-x-1, y - 1), ly = min(n - y - 1, x - 1)$$$. $$$Ans_{mn} = max( y-1-lx, x - 1- ly) + 1$$$. For max place $$$lx = min(n-x, y - 1), ly = min(n - y, x - 1)$$$. $$$Ans_{mx} = max( y-1-lx, x - 1- ly) + lx + ly + 1$$$. Maybe its too complicated, but I came with only this solution
Wow! Thanks.
@kun4ik I did similar to this, can you tell where I went wrong, here is my submission: my submission
@kun4ik why dont you consider the additional
min(n-x-sg1, n-y-sg2)
which is there in my code which denotes pairing of those whose performance is worse in both contests? similarly for max?Finally found the answer : I didnt check if some terms went negative, so they needed to be 0 capped.
Wow nice <3
It will not work for a==n and b == n
How to solve B
How do you solve B? It took me over an hour to even come close to a submission. My logic was to casework on N, and the sum of A & B, but I'm pretty sure this isn't correct. This is what I came up with.
What if A = N and B = N? you get (N + 1 N). I got WA on test 3 due to this case.
Thank you!
same
I only solve the second that
Is it wrong ?
cool contest but not a good contest problem C idea were really cool but problem B....
difficulty balance be like :
What is test 8 in C1 be like ?
int overflow
I used Long Long to store everything Though
Just a guess, maybe something like this:
0 isn't a Valid Number (due to Constrains) but i got your Idea
I also get WA in test 8.
I use the maximum number to construct answer, which is totally wrong. The flaw of my solution is that it can't detect the nearby situation and went wrong, like:
10 5 64 62 62 14 84 59 13 1 15
64 should be the summit of the answer, but I got 84.
anoyne else solved c1 but couldn't A??
i got WA on some testcase in problem A.
This is what I was about to go for, then made triplets using sruct lolol
Quite tough as a Prob.B :(
I got stuck with that for 40min, with three Wrong Answers.
lol i definitely don't deserve to be CM
And I also dont deserve to be a specialist.
me too
Don't think all this nonsense ,Stay motivated and Keep Coding
i have the same feeling dude ;(, after doing nothing on B, there's no reason for me to stay violet
Is intended sol for D dp[index][mask] which means we use chosen segments, corresponding to mask, covering point of coordinate index? My code is a mess, I need to transform mask for each transition, there has to be a simpler solution.
How would you transition to a new index?
Find the intervals that cover both points, shift mask the appropriate amount
I pretty much got the same, including the mess and the fail at pretest 2 (and couldn't correct in time)
BTW, I fixed pretest2 WA by fixing test:
1 3 1
2 2
Might help you :)
You can preprocess the intervals in order and map each interval to one of the available bits:
If you want to set / unset an interval, you should use (1<<whichBit[interval]).
Problem B gave me atcoder vibes.
There is a similar problem on atcoder. But I couldn't remember problem-id. Maybe someone can find it.
well I find it, arc094b. but total score is $$$a*b$$$ not $$$a+b$$$, and $$$n\rightarrow\infty$$$
I think it's this one.(https://atcoder.jp/contests/arc094/tasks/arc094_b)
yes. find it too.
Was D something like $$$dp[pos][mask]$$$ denoting max happy children for current position and the mask of the intervals taken?
System test will run after 30 minutes? Or right now?
Reason —
"Due to the official competition source codes of other participants will not be available for an hour after the end of the round."
Once editorial is published, I'm going to learn much useful stuff
and you know, problem B, I won't let you discourage me!
Thanks for this contest. I know my real rating now. I can't solve a Div.2 B for an hour.
Haha :D
Me too ;-; I thought that B is always easier than C so I tried my best to solve it, and failed ;-;
I thought B was pure greedy.
Actually I spent almost 40 minutes on Problem A after I solved B & C. I did not see the condition that at most one portion is allowed, and was completely stuck.
Oh, and I can only solve the max position of
B
in first 10 minutes but 1h50 minutes left I cant solve the min position ;-;Hope you will solve A, B, C in 45 mins in the next contest :D
Does anyone have any ideas about div2-D/E?
D, can you explain sample test?
"In this case all children will be happy except the third." The third kid gets 3 candies, which is odd, so it should be happy. Kids 2 and 4 get two candies, should be unhappy. ???
Only 1-3 and 3-5 are chosen, so 1,2,4,5 will have one candy and thus be happy, while 3 has two candies and is unhappy.
I had a hunch that solution of C2 could be related to dilworth theorem?Is it true?
Just use a monotonic stack.
Got it, thanks!
For the problem B
The worst position is min(n,x+y-1) Reason: we can always arrange (first k natural)(we have this set 2 times) numbers with minumum sum k+1.
eg. k=5 we have set1 = 1,2,3,4,5 and set2= 1,2,3,4,5 so to get the minumum sum we can arrange 1+5, 2+4, 3+3 (=6)
so if x+y is 6 we can have at most 5 players ahead of Nikolay. in general we can have at most x+y-1 players ahead of Nilolay.
The best position is 1 if x+y<=n by the logic mentioned above
else (when x+y>n) we will try to find the number of pairs of a and b such that a+b>x+y
to do this efficiently lets have a target=min(n+n,x+y+1)
to reach the target set a=n so b=target-a
thus b is the best position achievable.
What's wrong with the following code?
It is copied, not linked.
I am not able to understand why have you written worst = min(n,1+x+y-2);
It just ended up like that while i was coming up with the idea, it's equivalent to x+y-1 anyway so it doesn't really matter, what does matter is why it's giving WA on test 3.
You have done the same thing... what I did.
Don't know why WA on test3.
Just a matter of some kind of bad luck :(
Thanks for giving it a thought, i'm really puzzled with this :/
you forgot cout<<endl; lol consider having 5 tests you need to do cout<<endl;
Omfg you are right i can't believe this ever happening
Coronavirus wins!!!!
how to solve C2 anyone?
linear dp + non-decreasing stack
The final array of the answer can of these 3 forms :
Part 1 and 2 is straight forward. For 3rd part we will do some preprocessing. Let's construct two arrays Pre, Post.
let's calculate array Pre.
Similarly Post array can be calculated. And the array will be splitted at the point where pre[i] + post[i+1] is maximum. See this for stack method.
that's what i was going to write, but i was about to use segment tree instead of the idea to move over indexes. thx for the solution
I too used Sparse table + binary search for such type of problems until i read the editorial of this problem from Codeforces.
Thank u so much. Nice explanation.
Will we get to see testcases used?
I couldn't find a O(1) math solution for first integer in B,so i just used binary search to find it :) (nice C btw)
haha, nice bro <3
;-; Sad for me trying all the O(1) formula I can think with no result
Div.2 $$$\times$$$
Div 1.414 $$$\surd$$$
Difficulty:A<C1<B<C2<<D<E
How can you solve B ?
Well...I found the formula by the samples
... My code can output as the samples but not for my own created tests ;-; Every formula I try is still fail 1 ~ 3 tests ;-;
That't too bad...
My formulas are
min(max(0,x+y-n)+1,n)
andmin(x+y-1,n)
How did you arrive at this solution? Can you please provide some mathematical proof
i guess you may solve B/C in next round if you stop wasting your time(like what i do right now) and start upsolving(like what i will do) :)
why down voting, iam just leading him to a better rate
Can any one tell the approach of A I just list out cases for it. Any other method?
I used greedy method
Notice that you should take (a-b) and (a-c) before take (b-c) else you will get
WA
When will be the rating change?
My code for C1 gave an incorrect answer on the 9th pretest. Any idea what's wrong with it? 71676960
Sorry but your code cant be read now :v
probably you should use long long instead of int
I had incorrect answer on 9th pretest cause int overflow
Thanks, it was int overflow for me too.
Why fake123_loves_me just disappeared in the standing? He was first, but he disappeared and everyone else's standing get one step upper.
I think because he is unofficial participants. You can see him if you tick on the
[] show unofficial
on the top right.Correct me if I am wrong
Yes, but he did not have star before
But I thought that join with >
1900
rating will be unofficial participant ? (he is2044
)I just think
In fact, anyone rated below 2,100 will be rated on div.2 only round.
Ok thanks ^^
B is very hard
Can anyone provide the solution for C1? Thanks in advance!
Sharing code is not appreciated here. Better share links if you really have to; even better share your approach!
I think B may change position with C1
How can you solve B ? That is nice <3
Suppose in the first round we took x-th place and in the second round — y-th place
First we consider the max: We can let the person who took (x-1)-th place in the first round took the (y+1)-th place in the second round. Then the total score of this participant is (x+y) which can contribute to the answer .Similarly, with this strategy we can know that the ans is min(n,x-1+y-1+1)
Then we consider the min: We can let the person who took (x-1)-th place in the first round took the (y+1+1)-th place in the second round. At this moment , the total score of this participant is (x+y+1) which is strictly larger than we. By doing this,now1=max(0,n-(y+1)) of the first (x-1) people's final scores are strictly larger than B.The same is true for the dimension y and the number is now2. So the number of people who may not strictly larger than we is (a-1-now1+b-1-now2+1(myself)), but this is not the optimal answer, We can make pair X and Y smaller than me in pairs and make the ans to {a-1-now1+b-1-now2-min(a-1-now1,b-1-now2)+1}
My Submission : 71671193
{a-1-now1+b-1-now2-min(a-1-now1,b-1-now2)+1}
what is "a b" means ? please
i think i know this. drl
worst pos is min(n, x + y — 1) best pos is (x + y >= n ? min(n, x + y — n + 1) : 1)
proof is left as an exercise to the reader
Can problem E be solved using suffix array?
Without samples, I couldn't solve B
Typical maths problem XD
I solve it in 1hr40min QAQ
Finally Master. Hope I can stay a bit longer.
wow, peking university, you deserve the rating
OMG, univeracist spotted!
I cant see the code of others (it is almost 2hrs)
Me too :(
Me three
I THINK I VE COME UP WITH THE ULTIMATE GENIUS 35182798 IQ THINKING PROCESS FOR SOLVING B.
First you reduce the problem to a matching problem 71692875. I copypasted preflow pushes but it doesnt really matter!!! You could use ford-fulkerson or any other algorithm.
Then you notice a pattern and write this 71692875. Then you submit it and do not lose 5512571829 rating.
I think I am a fucking genius right guys?
Proof by AC is the way to go smart people told me this!!
actually i wonder how many of those who got an ac actually know why their solution works
i dont
You didnt even submit your super solution. In both of ur submission you got AC using the same 1 line of code.
okay man thanks for telling me something i didn't know
My code for C2 (here got the wrong answer. But when I changed at line 118 from '<' to "<=", it got accepted. I tried that to handle the case of all zeros (even though it is outside the constraints). Is their test case 20 outside of constraints or am I missing something?
Does anyone have the similar situation?
The System says I may write a code very similar to other's.
But this is problem A.
I think it's because the code is too simple so that it's easy to be very similar.
What should I do?
My Submission:71656145
What the system has sent to me:
Attention!
Your solution 71656145 for the problem 1313A significantly coincides with solutions Acranker/71656145, hnust_zhouzisheng/71662017. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
you may used ideone during the contest
Why do i keep getting runtime error on test 5 in D? Here's the link to my code
EDIT: Got the mistake
When will the system tests be visible, I want to know why my C2 failed!!!!
maybe i can help you with the problem, u can pm me if u wish
tfw you're purple but can't solve div2 B...
When will submission be visible? It's nearly 3hrs instead of so-called "1hr"! And I'm anxious to see why my C2 failed!