Всем привет!
В этот вторник пройдет московская олимпиада школьников по программированию для 6-9 классов. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680).
Раунд состоится 23.02.2021 12:05 (Московское время). Вам будет предложено 5 задач и 2 часа на их решение. Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут написать контест вне конкурса.
Задачи соревнования подготовлены grphil, Jatana, rip, Sehnsucht, DebNatkh, KiKoS, wrg0ababd, V--o_o--V, voidmax, meshanya, vintage_Vlad_Makeev под моим руководством.
За координацию раунда спасибо adedalic, за перевод условий cdkrot и meshanya, а так же MikeMirzayanov за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.
Также спасибо Noam527 за предоставление дополнительной задачи, которая помогла составить (я надеюсь) сбалансированный проблемсет для раунда.
Всем удачи!
Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.
UPD1: Спасибо LHiC, awoo, ScarletS, adarsh7777, kassutta, raj_mehta_ за тестирование.
UPD2:
Разбалловка: 500 — 1000 — 1500 — 2250 — 3000
UPD3: Разбор
UPD4: Победители!
Div. 2:
Div. 1 + Div. 2:
thanks for this round.
me vs russian school kids i am gonna obviously loose
on the olimpiad, i made all this tasks....
Yeah, for the GREAT PRETESTS for D. :(
The competition announcement should include a link to the competition: Codeforces Round 704 (Div. 2)
But... It does
Looks like it's not obvious enough to me :/
The link says "Round".
I am curious: why do all these contests prepared by Moscow Olympiad Committee have unusual timing?
We need intersection between official contest and round because we want to prevent cheating from onsite participants.
because we have only 11:00
Will the problem score distribution be announced for this round (since there is an official competition as well)?
I believe it will be a wonderful round!
Hope all of us can get good scores!
Grades? Is there any exam?
Sorry, I've changed "grades" to "scores".
Notice the Unsual Timing.
For me living in China ,the timing is so good.
Same for Indian Subcontinent as well!
No, it's normally at night for us at just 8pm, this one will be just after afternoon which are slump hours.
Yeah!No need to stay up late!
As a Chinese coder, I'm surprised to find out it's a good time for me to participate in the contest, normally for join the contest in Codeforces, I have to stay up late.
I'm looking forward to solving the problems, it'll be another chance for me to challange and improve myself. Stay Cheeki Breeki!
Ooh
Please can the timings be changed because students of many countries won't be able to take part due to their college lectures ?
ok sorry for that.
No it can't, they need to conduct it along with the actual olympiad to prevent cheating.
ohh ok I didn't know that sorry my mistake
Note: Unusual time
Unusual timing = less competition
And more negative if you didnt get much problems;(
One of my friends is interested in setting up a round. Does anyone know typically how much time it takes for the entire process (proposal of the round to the hosting of round)?
https://mirror.codeforces.com/blog/entry/80214#comment-665044
Cheaters' brain:
I don't get it. What's the point?
Also, something special from Linus Torvalds
Nope, round #657 was vintage but this is not.
Wow!, Thanks:)
Hoping to get scoring distribution as early as possible
You guys(Russian school kids) do train hard regularly.. Nice going .. Hope to see similar things in my country too.
White hat jr. will do it, XD
At their age i used to watch doraemon.
I sense chaos
I am curious: why do all these contests prepared by Moscow Olympiad Committee have unusual timing?
Even though we have quit our music career, we will continue to give contests on Codeforces.
Woah!
Daft Punk are from SecondThread Fan Club. galen_colin would be proud.
Lazy Propagation using Sag Tree is our favorite concept.
Please share score distribution too
It hurts...
Repost
Looks like no one cares if it's a repost.. As long as it is relevant and everyone enjoys One correction in the meme .. It's for grade 6 to 9 .. The meme didn't pass the second pretest
hope green delta for all
That is literally impossible.
This timing is so much better for me. Afternoons are usually slow, this can give a nice touch. All the best to all.
I hope my rank and rating will be increase in this contest :)
How can both of them increase simultaneously?
HAHAAA.. it will ;)
HAHAHAA,you are right
I missed the time :(
*After AB
Is C DP or greedy?
answer is just
lastoccurence[t[i+1]]-firstoccurence[t[i]]
. but find occurence as if you take this s[i] there is one beautiful sequence. see my code for find first and last occurence :(except lastoccurence[t[i+1]] depends on the lastoccurence[t[i+2]] so you need to technically check the last occurence that does end up in a valid subsequence
it is not, consider testcase
ans==3, but your simple formular gives 4
A more correct solution find the leftmost possible subeq of t[] in s[], and the rightmost one. Then ans is the max of the diff in all positions in left and right.
Edit: Changed to reflect that ans==3, not 2.
hey, can u please elaborate on how the answer is 2?
We can choose the indexes of the subseq as 1,4,5, then ans==3.
You are right, it is not 2. But the point is that it is also not 4.
it's $$$max(postfix[m-i]-prefix[i])$$$ where $$$postfix[i]=$$$ largest index $$$j$$$ s.t. $$$s[j..n]$$$ contains $$$t[i..n]$$$ as a subsequence. and $$$prefix[i]= $$$least index $$$j$$$ s.t. $$$s[1..j]$$$ contains $$$t[1,,i]$$$ as a subsequence.
How to solve D ? :(
I think maximum $$$k$$$ is obtained for something like $$$a = 11111000$$$, $$$b = 10111001$$$. I may be wrong. But this seems to work. We can then shift bits in $$$b$$$ to get all smaller values.
we can get k ones if we subtract 2^0 from 2^k.
Or we can get the same if we subtract 2^(k) — 1 from 2^(k + 1) — 2.
yes, this is the one I forgot to handle during contest
first observe it, 1 -> 1 and 0 -> 0 results in 0, only you can use 0 -> 1 or 1 ->0 to have one.
secondly, if you form a pattern like this -> 111000 011001 from this pattern you can have (one + zero -1) number of 1 as k. Now think a bit more about it. Hope you'll find the answer.
if you can't still find the answer then think of it,
if you put same bit inside those like this,
then all of them will contribute in the answer except the first one. Now try rest by yourself.
Thank you dada. A good and tricky question for upsolve :D
How to solve E?
How to solve world hunger?
I guess the official contest is still running, We should not discuss the solutions now.
.
.
What was famous hack in problem D?
I didnt passed D but maybe 0 1 0
forgetting to check for a = 0 (that's what I found in my room)
Can Anyone tell me pretest 18 of the D of this contest
Hacks,hacks everywhere!!!
I got the expected output for your testcases but still failed pretest
Do you mean test 8?
I passed this one as well , I got wrong answer on pretest 18 :(
I miss the first one rip
I missed these cases :'(
Why pretests not including those cases? Seems wee need to handle them separately.
$$$"YES"$$$ and $$$"Yes"$$$, are different I think
Can anyone explain why my code for E is wrong on pretest 27?
108288547
Almost missed this round. UNUSUAL TIMING (: Started 5 minutes late with the fastest heartbeat ever.
And then killed the round like anything XD
You can say nothing before the system testing is completed... my D failed lol. I feel like banging my head into a wall
Can anyone help. Why this solution is wrong import java.util.*;
public class A {
}
Calculating with large values and floating-point numbers gets imprecise, so for example the
ceil
might not give the correct value. ExampleUse integer ceil instead:
I tried to hack A with
99999999999999998 2 2 2
but got an invalid hack erroreven though, the problem clearly says
p < 1e18
Someone from the authors, please clarify this?
Did you put in the number of test cases? The problem has T test cases as well.
Ohh thanks, my bad!!
Can anyone explain why my submission for E 108288547 have WA on pretest 27?
how to do B i'm getting tle
edit: can we do it using bitset i've got the logic but not able to implement if someone has done it using bits please do share ur code
max_element works in O(n), use set instead. AC code
Or range maximum query
How sad it is when I got the observation for D so early but kept getting WA at pretest 8 around 1 hour and half :((
The most important observation in D is that there is a good chance of bad edgecases.
How do you know about the contest, sir, you didn't participate.
I did, but did not submit anything. I was horrible slow in A and decided to try B first. That went not much better, so I solved C. Then after D I again thought about submitting the solutions...but I think I could missed some edgecases in D and the big time panalty from ABC... so in the end nothing was submitted.
Try this
try this:
1 1 1
ans: No
just now: hackforce
soon: FSTforce
Why is everyone discussing solutions and hacks... The contest for the kids is still going on in Russia.. Let's just control our curiosity for an hour
So maybe we shouldn't discuss anything about the contest especially the solutions and the hacks.
Felt more of like a Div 2.5 contest. It was great !!!
Thanks for the "strong" pretest of problem D!
Is that sarcasm ? Or they were really strong ? Above i see lot of people got hacked.
Yes, it is sarcasm. The pretest of D is very weak. These types of data aren't in the pretest :
Bloodshed incoming.
In C .. why does the logic of setting max,min for each index (keeping in mind the neighbouring char's max,min index) fails on pretest 5. You can check my submission : https://mirror.codeforces.com/submissions/indresh_0903 Can anyone please help :/
Submission viewing is off for an hour ,as official contest is still going on
Notice the condition : $$$1≤p_1<p_2<…<p_m≤n$$$ .
Yeah it was taken into consideration while calculating possible max and min index for each t[i] .. for each index .. its max is < max of i+1 (with base condition of t[m-1] )and its min > min i-1 (with base condition of t[0]) if for a particular 'i' its min and i+1's max will give me the ans, then for all index >i+1 .. there max-es will be used
max and min doesn't guarantee the right sequence.
for example,
im getting 1 as answer for this tc i guess its correct
It might work out for you. But, there would be some testcase where you calculated the difference of two illegal indices (i.e. these indices might not form a beautiful sequence) and set it as max.
Dude i have set max of index i strictly smaller than max of i+1 and min of index i strictly greater than min of i-1 .. so i dont think that would be an issue
So scary (be hacked in last 10 mins) and so rubbish pretest in D! ):
Why is this wrong for A?
I thought only C++ had precision issues :(
Guys did anyone else have this problem? When I sent a solution it said that I had already sent that solution but I was sending it first time. I did anything possible but it always said that I had already sent that solution.
you can add a comment line at the end of your code and submit again
I did, it is not working
Was D having a simple idea to trigger 1s in result starting from a pattern like
1 1 1 0 0 0
0 1 1 0 0 1.
Triggering flood of ones from right at 0,1 pair and stopping at 1,0 pair.
I didn't participated but just pondering over the idea.
That is.
Also, you can only produce 1s in that way since you have to use the same amount of 0s and 1s in x and y.
well i too thought of this idea first , then i came to know that leading zeroes are not allowed in string x and y
This gives me RE on pretest 5
whereas this gets AC on pretest
I have changed only this much part of the code and nothing else. Someone please help me out in debugging the error.
UPD: I got the mistake I was doing. Thank you all.
@Admin/@MikeMirzaynov, if a person participates in a contest, why is it that that person is not allowed to make another submission until the system testing concludes? (Obviously I'm not asking you to count submissions after contest gets over) It has happened very often that I don't get a problem within the contest time bounds but do have a solution immediately after the contest gets over — and I have to wait for a while before my submission can be evaluated (because system testing is running) — Its bad enough that I wasn't able to solve it within the bounds, worse still that I can't check if my code is right or not when I finish it. Request you to look into it if possible...
The answer is pretty obvious if you think, they want all their server power to be focussed upon system testing, so that they can be finished as fast as possible with the limited server power that they have.. The eagerness to know our solution's verdict has to be sacrificed a bit for this.. Tough world xD
But anyone can still submit concluded contest problems — server gets used for that also no? I think your logic breaks because of that...
Why was there sudden change in timings ? My midsems are approaching and had to miss 2 classes, nevermind tho, the contest was worth it. Sincere request to not change timings, old timings were perfect.
don't worry.. it's an ocassional thing
How to solve C using dp?
Is there any solution for E using graphs??
Thanks for the round though the pretests are a bit too weak...
WA on test 73 :(
me too
No, my friend WA on test 73, not me :((
good contest
Is this round "FSTForces" ?
Agree.
Agree
Fst forces
What's Fst?
Failed System Test
Poor pretest for D :(
A too :)
codefst
codefst
True.
Believe it or not, I believe that today's round is just for hackers...(At least D)
Some very weak pretests for D (:
:(
I don't know why they had single test cases for D, they should have used multitest input.
I want to know who makes problem D's data?
At least 400 coders failed system tests on this problem :)
(include me).
Thanks for the strong pretests! Love pretest producer!
Is this submission for A hackable? He used ceil and float when numbers are as big as 1e18. I got cases which fail in g++14 and couldn't find a hack case since he submitted in g++17
this submission too
qwq oh noooooooooooo!thanks for pretest!!!
Good Guy! case for a=0 not in the pretest. Fst so many people.
me too :(
Same here man, it's so irritating
Nobody:
Codeforces even after the systest: You're contestant.
Why I am not able to submit my code after system testing is over?
This Round is quite hard for me. QwQ
WHAT GOOD PRETESTS!!!!!!!! :(
Love this pretest. Expert time uwu
Corner cases should be included to the pretests...!!!
Maybe the pretests of D are too weak...
Maybe you should enhance the pretests carefully next time, otherwise people like me would be so sad to see their ratings fall...
I think the pretests of Problem D are too WEAK, many possible datas are IGNORED.
We're still unable to make any submissions post-contest. I believe, usually, we're allowed to submit immediately following the completion of system testing. Is there a reason that we still can't make submissions? I imagine there's a few people waiting to make corrected submissions following the large number of system test fails.
资瓷
CodeForces is an international CP platform, so please speak English instead of Chinese.
OK! Thank you
资瓷
May be there should be some rule like if 30% pretest passed submissions failed main tests, round becomes unrated.
Nah, official solutions are often tested very carefully to ensure that there is nothing wrong with them, especially when a problem is prepared for a major city-wide contest. If your solution fails system tests, it's safe to assume that it is wrong. Of course it can be the case that the official solution is wrong, but this has rarely happened in the past.
thanks for this round.
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Thanks for doing this everytime! You know what delta to expect!
There's a Chrome extension for rating prediction: https://chrome.google.com/webstore/detail/cf-predictor/ocfloejijfhhkkdmheodbaanephbnfhn?hl=en
Ooh Thats cool! Thanks for the suggestion!
Thanks for moving the cheaters Mike. :)
Thanks for this round.
But the pretests are a bit weak, and the problems are a bit easier than other Div.2? And I think five problems aren't enough for two hours. There are too many people solved out all the problems (even in the first hour) but failed on the system tests.
Hope there will be a better contest.
I think one should more focus on checking correctness of his/her code rather than submitting it fast.
InternetPerson10 orz
Why can't I hack solutions anymore? The button is gone although it didn't pass 7 days.
ll n, m; cin >> n >> m; string a, b; cin >> a >> b; vians; ll mx = -1e9; f(i, 0, m — 1) { char p = b[i]; char q = b[i + 1]; ll pos1 = a.find(b[i]); ll pos2 = a.find_last_of(b[i + 1]); ans.pb((pos2 — (pos1))); amax(mx, ans[i]); } // if (ans.size() > 0) { // ll anss = *max_element(all(ans)); // print(anss); // } print(mx);
can anyone tell what i am missing here? like i am finding left occurance of i and right occourance of i+1,,and taking max of them.
Your approach is incorrect. For example, try this abbbc abbc
2
I don't want to raise any negativity but submissions from LiM_256 and sawa855 are suspiciously similar. They can be found at number 614 and 617 in final "official" standings. Seems like, they tried to alter some code to get away. Obviously, I'm not mentioning them.
Don't forget to check sawa855's hacker
PS: I apologize if I bring out something incorrect.
Hi, In problem A my solution was giving wa but I am not able to find reason for that. after that i changed my code, it got accepted. I am providing links of both , if anyone knows about this do reply. Accepted Wrong Answer
I am not sure but when i used both of your code for test case : 1 1000000000000000000 3 3 3 The "Accepted" one is giving -64 and "Wrong Answer" one 0 as answer, i think its most probably because of overflow or something like that, the correct answer should be 2 for this test case.
but when I multiplied in min func, then also integer overflow should happen
I think it's because
ceil
does not return an integer, which leads to floating precision issues. As mentioned many times above, try not to rely onceil
.But on websites like geeksforgeeks, It is given that ceil returns an integer