Всем привет!
Сейчас проходит первый тур Открытой олимпиады школьников по программированию, а уже завтра состоится второй. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541)
Открытая олимпиада составляется из самых интересных и сложных задач, которые были предложены многочисленным коллективом наших авторов, поэтому мы решили провести рейтинговый раунд Codeforces, который состоится 08.03.2019 12:05 (Московское время) и будет основан на задачах обоих туров олимпиады. В каждом дивизионе будет предложено 6 задач и 2:30 на их решение.
В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.
Задачи соревнования были подготовлены vintage_Vlad_Makeev, isaf27, Flyrise, cdkrot, GlebsHP, ch_egor, Zlobober, qoo2p5, grphil, achulkov2, Schemtschik, akvasha, mingaleg, V--o_o--V, wrg0ababd, под руководством ch_egor, cdkrot, GlebsHP, Zlobober и Андреевой Елены Владимировны.
Задачи для второго дивизиона были доработаны KAN и MikeMirzayanov, которому мы также говорим спасибо за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.
Всем удачи!
UPD: Поздравляем победителей!
Div.1
Div.2
Разбор скоро появится
UPD: Разбор
Раунд состоиться
fixed ;)
Раунд. (состоиться)
You mean round #545?
Edit: got fixed.
stop flaming people for no reason, you're not perfect either!
The title was #544, and I pointed it out so they would fix it.
i wish this contest will be my chance to become candidate master
I wish this comment is your chance to get out of the negative :p Good luck bro <3
Just be careful with any streams.
Oopsie? https://olympiads.ru/zaoch/2018-19/editorials.html
The editorial you linked is unavailable in my country, so at least they have that handled.
Link redirects to "Rick Astley — Never Gonna Give You Up (Official Music Video)".
You must be fun at party
parties*
it is like asking thieves not to steal.
Hopefully this contest will not end up with "Let's solve problem just for fun"
is it rated?
if god loves me nope
Another potential unrated round :)
Hope not two unrated contest happening in a week..
Looking forward to solving a problem by kun :D
Not a good timing for Indians. :(
We should believe in Codeforces that they won't make mistakes any more. (ง •_•)ง
Not a suitable contest timing for Indians. :(
Why? It'll be at 2:30 pm. I don't see a problem.
oh, so poor
He meant IST (Indian Standard Time).
Why everyone should know that this contest is based on Moscow Open Olympiad in Informatics? I think it is better to hold information like this in secret or announce it after the end if the cheating is possible.
Well you need to be able to tell people that know the Moscow Open Olympiad problems not to take this contest. There's no easy way to tell people this without outright saying that the contest shares at least some problems.
I believe there are better ways than make it public. Even if you know the solution but the statement is changed it will take some time to realize it. But there won't be enough time (and purpose) to spread it across the community.
Best contest time for Japanese! Yeah!!!
And for Chinese too :D
但是横跨了我的吃饭时间
But we cooked it while eating instant noodles.（fog
So this is the reason that you only solved one problem?
orz sxz，i have FSTx2 on this contest
╮(╯_╰)╭, just have fun~
When will the editorial be published?
Meanwhile in my timezone
Scoring distribution?
О да, и раунд напишу, и с девушкой вечером погуляю...
getting "you have already submitted this code" for all submission I'm making .-.
CF rounds quality is coming down everyday and we see more and more(unbalanced,unrated,unusual,...) rounds...
Today's contest is easy as I raised 5 rank.
У автора закончились идеи на новые задачи , так что теперь он просто изменяет текст условий предыдущих
ewww moscow
Can't solve last 2, but all problems were interesting. :)
(Also need to go back to sleep now).
A few unbalanced round. (maybe not a few).
Is it only me or every one that thought this contest was unbalanced?
I dont know, i didnt have any ideia to solve b, c or d
Kudo for the pretests :D
Btw, anyone have any ideas of pretest 16 of Div1C? :D
I fixed RE16 with #pragma comment(linker, ”/STACK:36777216“) (using MS C++17)
Woah, that doesn't work for me. Must be some other segmentation fault I haven't figured out :<
Still, thanks, I didn't expect this one anyway ;)
How to solve Div2. B?
Saw a bug in my A after I locked in. Feelsbadman
How do you do Div. 2 B? :O
Is it just some nasty casework?
No just find all four types and use two for loops such that you check all the possibilities, by using the given conditions and two FOR loops you'll be able to check all the possibilities if nothing satisfies, print -1.
The four types are
Now use two FOR loops to check the number of type 2 people and number of type 3 people in group 1, then you can figure out type 4 needed.
but i can't solve this problem by this way,could you explain it more clearly? Thanks
You can go through My submission
Was Div2 F only simulation of tortoise and hare algorithm?
I tried to hack one of the solution, I uploaded script (which generates testCase) several times, but all the time, there was Generator compilation error. Could you teach me how to hack using generator scripts?
You must strictly follow the format of the input data up to spaces and line breaks; For example, in problem Div2 A script generator would be
make sure that you have cout << endl; in the end of the code and spaces in right place; here is a generator that will not compile (because of unnecessary spaces int the end of line)
How to solve Div2. B?
I solved (pretest passed) it this way:
Let a, b, c, d be number of index with (0, 0), (0, 1), (1, 0), (1, 1) respectively. If you select A, B, C, D of the types in the order, then these should hold: A + B + C + D = N / 2 and C + D = b - B + d - D. Using the second one you can say that A - D = N / 2 - b - d.
Now, you can brute force on A, D and whenever you find one brute force on B, C.
How would you account for the complexity of the solution ?
O(N2) with very low constant. I think it can be optimized to O(N) if you find A, B, C, D mathematically instead of brute-forcing.
That moment when you solve C and D but cant solve B :(
Was Div2 F(Div 1D) only simulation of tortoise and hare algorithm?
It took me 30 minutes to realize that in C the tour can last more than one week. Granted, if that wasn't the case, the problem would be equivalent to Hamiltonian path, and in the second sample the path lasts 6 days, but I still think that the problem was unclear. Nowhere in the statement does it say that the tour can last more than one week :/
I had the same problem with not understanding it at once.
Exactly, I was scratching my head for long time as well figuring out why are they asking me variation about k-path problem which I know is pretty hard to solve. Need to look up explanation of sample as well.
B on div2, is hardest B question I ever see in codeforces . what's the goal of designing such question ?
Thanks for an amazing contest!
Solution for D:
Move (0, 1) and (0) (2 operations) while their positions don't coincide. If we have done k such operations we must have 2k ≡ k(mods),
. Now start moving all the pieces together. After t moves they all will be at the desired point: as 2k + t ≡ t(mods), pieces 0, 1 will get there, while 2, 3, ..., 9 will obviously get there for the first time.
How do we determine t?
The first value after which all pieces are at same point
Oh shoot what a retard i am thank you
D was a very nice problem, kudos to the author.
Can you explain what this notation means?
k is divided by s (k = 0(mods))
I haven’t seen that written with vertical ellipses before, so I was confused. Thank you.
I solved A, and then I just read problem B -> C -> D -> B -> C... again and again...
CF 545 made me iterator function...
B on div2, is hardest B question I ever see in codeforces . what's the goal of designing such question ?
It is certainly harder than C which is just knowing about ordered sets.
Lol you don't even need ordered set. Sorted array with binary search is enough.
:|
I solved it with just sets...
How to find t in div1D? (if I not mistaken we can find c due to fixed players on positions with index 2^i, before first time we meet fixed player)
Hint: You don't need to find it to solve the problem.
Hmm... I thought about this but I have no clue, how to find exact point in cycle?
Fun fact: Problem D is used as a subroutine in algorithm for subset sum in O(20.86n) time and polyspace.
I have seen this on a lecture a few days ago, which explains why I was so fast in solving this problem :P.
also a subroutine in Pollard's Rho algorithm.
In div1C was O(N*D) the correct time complexity of the solution? I had TLE 11 witk making a graph with nodes associated with pairs of cities and days ( n*d nodes, m*d edges) What were other aproaches?
Exactly :|... Got this solution pretty fast and sank for a long time in microoptimizing it and didn't make it pass 11th test :|...
For any strongly connected graph there exists a number g such that, for every vertex v and sufficiently large k there exists a cycle of length gk which passes vertex v. Intuitively you can think about the GCD of all cycles. It is not, but something similar.
If you decompose a graph into SCCs, you can calculate such g in linear time. Now you can do a DP with a state as (vertex, length mod d), and transited for every edges and SCCs. This is O((n + m)d), but the DP routine is just array scanning, so my non-optimized code runs in 0.3s.
thank you
Good solution! I tried to solve it in this way but failed in the contest.
Good solution! I tried to solve it in a stupid way but failed in the contest.
You are a Pinkie Pie too? And you are repeating my words!
Didn't Twilight return all my clones back to the Mirror Pool, did she?
To compute that value
gfor every connected component you haveD*(number of nodes of CC)? Can you do better than this?For all cycles created by back edge take its length. For all two disjoint path created by forward edge take the difference of length of two paths. g is a gcd of them. So it is simple dfs.
Even additional half an hour didn't help me to solve B and C. I guess they were hard not only for me.
Div1 AB may be a little bit too easy.But I just have no idea about Div1C...
When I see a problem
from school olympiadin which you have to optimize constant for O(dn) solution...Do you have an idea what caused "Runtime error on pretest 16" ?
Lmao, no clues at all. I just tried changing vectors to arrays
Maybe its because of recursion and too much memory in stack (in my case)
It may be, but it should have been the case in the solution which got TL 18 as well.
And it seems to be some compiler related stuff because same submission get AC on MS C++ -_-'
Link
51016217, 51038646. same code, same compiler.
Am I the only one that thought that D was easier than A, B, and C :)
WA on test 70 bro, FeelsBadMan
I cry everytime :(
Yeah, you basically just have to know a O(n) string matching algorithm. At least that's the way I did it.
can you explain which algorithm u have applied!!
I used Z-algorithm to find the longest suffix is t which is also a prefix. I learned it from here, page 247.
thanks bro!! i got it.
What is solution for C div 1 ?
Build a graph where the vertices are (u, t) where u is the node and t is the time modulo d. Then, connect (u, t) to (v, (t + 1)modd) for all edges
. Compress the SCCs of this graph and do DP on DAG. The key fact is that if there is a path from (u, j) to (u, j'), then there is also a path from (u, j') to (u, j) (by going through the cycle more times), so you won't overcount cities.
I had to do a lot of optimizations to get pass the pretests though, maybe there's a simpler method........
Do I also have to do DP in the SCC?
Nope, in the new graph you can take all the vertices in an SCC if you ever reached it.
Really what if the length of the cycle is a multiple of D
"I had to do a lot of optimizations to get pass the pretests though, maybe there's a simpler method........" — actually you don't need simpler method, you need harder one :P. At least that's what my friends did in order to omit recursion on 5mlns vertices. It seems you can divide just original graph into SCCs and then do some weird shit with remainders like counting GCDs of all cycles within every SCC etc. Overall complexity is O(nd) anyway, but recursive part is only O(n) and that's supposedly a profit xd.
I tried some optimizations to PP but I got FST:( I think both the time limit and the memory limit are too tight.
my simple O(n*d^2) got AC :3
that contest was tough one..
can anybody help me in knowing why my solution to div2 d is giving wrong answer on pretest 6. sol link : https://mirror.codeforces.com/contest/1138/submission/51026146 Thanks in advance
I also kept getting WA test 6 but then I realized that there is an edge case. Consider the input:
00001111
101
With my original code it would have outputted: 10110100 and it would have only contained 2 instances of t.
But you can actually get more than 2 instances of t because the strings can overlap, so the optimal result would be: 10101010 which is actually 3 instances of t.
Thanks .. got it now
Div1 D is basically Floyd's cycle finding algorithm
Oh, I knew this algorithm. Too bad I wasted the whole contest on C...
I also know the algorithm but as i suck at interactive problem, i didn't even bother reading it
That's a bold statement. I knew this algo and couldn't solve this problem for more than half an hour.
Floyd's algorithm is the first thing that popped up in my mind seeing the problem. I wonder if anyone solved it with a different approach.
That's weird, I see no difference between this algo and problem D xd.
My bad. I knew the idea about moving two pointers with speeds 1 and 2, usually that's enough for all things like Pollard-rho.
wanted just 2 or 3 secs more. Coded the correct solution for B, going to submit and contest over.
:(
Please judge my first prepassed solution on Div2D! The difference between my first solution and second solution is just number of comparisons of hash value of intervals.. I got TLE on second :(
very nice contest ^_^ thank you all
I got WA on test 70 for D :( I knew it was too good to be true.
Why it always have to be so long time after a contest to wait to submit my solution
how to solve div2 D?
Maybe : Find first position i in string t such that t[i...n] is equal to some prefix of t i.e equal to t[1...n-i+1]. Then build new substring from that position keeping count of zeroes and ones left. Hashing can be applied.
you can solve it very easily using some help of Z_function algorithm which tells you which idx can be prefix of the same string example:
string s="11000110"
you can see that at idx 5 will have a prefix to the main string which is 110 (that's what the z_function get) so from here you can deduce that after you made up the first string just concatenate the remaining string starts from idx 3. i hope you understand what i meant to say.
I tried to hack one of the solution, I uploaded script (which generates testCase) several times, but all the time, there was Generator compilation error. Could you teach me how to hack using generator scripts?
What's with upsolving?
Hi guys, I hope you enjoyed round!
In case you wonder why upsolving is not available yet -- it's intended, since the onsite events haven't finished yet. It will be open in roughly 2-3 hours.
About editorials, we will be happy to publish them after we finish with the onsite as well.
Thanks!
Thank you for the great round! I think Div1C is an amazing problem!
Will upsolving be available soon?
Here is the link to results of the onsite event. Could you please post the matching between tasks codenames (bering, krusenstern etc) and their cf positions?
AFAIK:
1137A - Skyscrapers -- polo
1137B - Camp Schedule -- gagarin
1137C - Museums Tour -- dezhnev
1137D - Cooperative Game -- cook
1137E - Train Car Selection -- magellan
1137F - Matches Are Not a Child's Play -- bering
correct
My Solution For Problem E can be hacked by n = 1, m = 3e5. Then we preform 299998 times 3 1000000000 1000000000, and then we perform 2 999999998 (10^9 — 2) and then go 2 1. In this way my solution (and many of solutions that get passed) will get a number exceeding the upper bound of the type long long. I think the test is too weak.
This is forbidden, isn't it?
Sorry, maybe I don't think my data is forbidden. For example, in your code.
~~~~~ pts.push_back({r, -overall_b — overall_s * (r — l)}); ~~~~~ "-overall_b — overall_s * (r — l)" this sentence will lead to a exceeding of long long.( And This is not the real value! It's just a tag.) And I have carefully checked that my data satisfies the conditon mentioned in the statement.
^_^
Is here any other guy's solution for 2c/1a is O(n^2*log(n)) and got tle? I used treap and the time limit seems too tight for me,LOL My brain is quite strange :\
I have used set and binary for each a[i][j] in row i and column j
Time complexity :- n*m*(log(n) + log(m))
Yeah, me too. I passed pretest 8 and failed on the same during main tests.
I passed pretests with 1996 ms, after using a back_inserter() :p
I passed test8 with 1949ms，LOL
https://mirror.codeforces.com/contest/1138/submission/51021650
https://mirror.codeforces.com/contest/1138/submission/51062541
Same TLE solution gets AC :(
Why god Why :(
What is test 70 on Div2D/Div1B?
Same problem :(
I think it counter some common hash mod, example 10^9+7
Well that's sad.
Well I used KMP but also failed on this test 51057303. Anybody has an idea?
I think there's a mistake with your program. For example
Your Answer is
But this is not the optimal solution. （During the contest I want to hack it but it's too hard to construct a set of data... XD
I found a mistake in my KMP and fixed it. Thx!!
-100 rating hmm nice number that made forget how terrible I did
The contest has ended and it shows Final standings but I am unable to make any submissions. Is it a bug or am I missing something here? It says you need to be registered for the contest. Edit1: I believe I am not the only one who might have missed kun's comment. For those who have gone ahead to downvote, it would be helpful if you could mention the reason for the same.
From kun's comment above
"In case you wonder why upsolving is not available yet -- it's intended, since the onsite events haven't finished yet. It will be open in roughly 2-3 hours.
About editorials, we will be happy to publish them after we finish with the onsite as well."
Thanks a lot for the clarification.
when it will be available to submit a solution?!!
It will probably take a couple more hours since the onsite event hasn't ended yet as kun has mentioned above.
Tricky Contest##!!##
How can I submit my code after the contest? It says I am not registered for the contest :(
I missed the contest. Is there any way to participate virtually? I see no options there.
Edit : Thanks. Got it.
Beat this
Hello, What is the souliton of div1 C, div2 E?
Does anybody know how to get/copy a test case that is finished with the ellipsis "..."?
You really want to debug your code on a test case that is finished with the ellipsis "..."?
I think there is now way now.. but you can go through other test cases from a AC solution and get a smaller test case that gives WA for you
div2b can anyone plz tell me what's wrong with my 51023192 . the basic idea is:
for 1st performance i iterate over all possible clowns (clowns+both_skilled).all the other both_skilled goes to 2nd performance. then i take some acro in the 2nd to make it equal . then rest of the acro goes in 1st performance. and rest of the clowns go the 2nd. and fill others with no skill actors. if all verifies i take that number of clown and print
try this test: 6 111000 111110
How to solve div2D / div1B?
Ahhhh...
Finally that's my best rating change (+318) ever...
Here is my personal log on the contest:
Before the contest I wanted to get around +200 to get myself a yellow, but the result is really good for me. Thank you all for the fun and exciting round!
How to solve D1C/D2E?
What is test 73 for div1C？
It looks like many people failed on it (including me)
cdkrot, I found some accepted codes of F is quiet similar, why no skip? 51026411 51023578 51025400 I don’t believe that there is such a coincidence.
Why I get RE on test 8 for div2 problem B ?? https://mirror.codeforces.com/contest/1138/submission/51062872
Why I get RE on test 8 for div2 problem B?? https://mirror.codeforces.com/contest/1138/submission/51062872
cdkrot MikeMirzayanov KAN
https://mirror.codeforces.com/contest/1138/submission/51062541
https://mirror.codeforces.com/contest/1138/submission/51021650
are exactly the same for the problem 1138C, yet I got a TLE during the contest.
Any chances for getting it rejudged?
If you get AC during a contest and TLE in upsolving with the same code, do you want a rejudge too?
I think CF already runs a solution a second time if it gets TLE.
Never happened with me before, just asking :p
so, where is the editorial? it's about two o'clock(UTC+8).
Now that's a first...
I got Accepted in 1138B - Circus in Div. 2 with Brute force on a, b, c, d (which are the numbers of different types of artists).
I just want to know how to prove the time complexity of this algorithm?
My submission is 51069702.
Thanks for everyone. :)
The
if conditionin your second nested for loop is a bit unintuitive, but apparently squeezing the search space considerably so that you solution passes. Also you don't need the 4th for loop (overcnt[2]), you can simply assign the value ofcusingn, a, b and dI have been understood your reply.
So I can easily prove that the time complexity of my solution is O(n2).
Thank you, sincerely. :)
My O((N + M) * d) solution for Div2 E. / Div1 C. times out on test case 18. Could anyone tell me what is causing this? https://mirror.codeforces.com/contest/1137/submission/51080307
Edit: TLE resolved by making the DP iterative.
In question 1.C I got RE The main problem is
If you change the vector to an array, you can get AC
In fact, the dfs depth of the program can reach 5000000
Why is that?
Specific can see
51145858 51016401
-
ohhh thats so cute of you to congratulate me, you didn't have to, <:)
I don't think it is a cute act to report cheating. I think everyone wants the game to be fair, so I don't think it is unnecessary to report cheating