Hello, Codeforces!
I'd like to invite you to Codeforces Round #375 (Div. 2). It'll be held on Monday, October 3 at 14:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!
This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by me and Mike Mirzayanov (MikeMirzayanov).
Great thanks to Gleb Evstropov (GlebsHP) for helping me preparing the contest and for the idea of the most tricky problem, which was specially made for this round, to Tatiana Semenova (Tatiana_S) for translating the statements into English and to Nikolay Kalinin (KAN) for writing solutions and very helpful advices.
It will be a little unusual round — you will be given six problems and two and half hours to solve them.
Score distribution 500-1000-1500-2000-2500-3000. Good luck everyone!
UPD Editorial
An unusual round with tricky problem. Programmers be like "Brace yourself, storm is coming!"
i wonder which question is going to be tricky :D
If problem C or D are tricky then you won't be able to solve them.
if you are speaking about me then speak for yourself, you are not even rated.
Tfw CF rounds are getting earlier and earlier, from starting at mid-night (00:35) to starting at supper's time (19:35).
Good luck for everyone that's joining.
hope the translation is good enough to understand clearly, unlike last round.
I couldn't understand what Problem C was :( although I solved D. I should have attacked D earlier :(
What is the reason behind setting contest time so early?
Maybe because the unusual early time is becoming usual, lol.
Maybe because of this
This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov.
you only needed one more problem to make contest for both divisions. poor div.1
EDIT : It seems downvotes are coming :(
this contest is prepared and rated for div-2 only
What you said is exactly the point! I think you misunderstood. Sorry of my bad English.
game time is good for china
Not only for China. Eastern Siberia and the Far East of Russia are very glad too )))
yes,it's a really good time
I think if the game time in 24:00 before is very good
+1s!
My sister
Are you twins?
You're both beautiful)
salam
what does tricky means?
Is it a tricky question ?!
It means there might be lots of hacks.
"Tricky problems" --> Hacks contest xD
Finally CodeForces loaded for me :( But alas around 40 minutes are gone :(
I cant even understand the problem statement for C!
Me too :(
Programming contest turned into English contest :(
What is the problem for D? I keep getting WA on test 7.
Woah, I almost told you the answer, thinking that this is a 2hr round and it had already ended.
when i sorted my vector in increasing order i got wa and sorting in decreasing order got pretest passed
Only a few numbers of hack wow!!!
Poor English #C..
Problem statement for C was too difficult to understand
I spent some time on solving C, then decided to solve D first, and then returned back to C. What do you do if you do not have full understanding of a problem?
It was an AMAZING AND WONDERFUL contest! Problems were really interesting and pretests were strong enough.
Thank you fcspartakm
EDIT : according to zscoder pretests were strong enough for A to D!
"Pretests were strong enough"
I don't think this is the case for E and F......
My random greedy solution passed E and F on pretests. (Luckily system tests were indeed strong enough)
I agree!! The best contest!! (even though i didnt do too well...:( )
I see someone has used -1 index to access array. And he passed the test. Is it possible?
What language did he use?
Or maybe show us the submission?
http://codeforces.me/contest/723/submission/21146251
For C++, it will try to access the corresponding memory which is undefined behavior. Maybe the code will work, maybe it will output something wrong, maybe it will crash.
Yes! I tried it before in c++ and it worked!
c++
well, in C++ array is represented as pointer to begin of it. All operations with arrays are actually operations with pointers and arithmetic of pointers.
So, if you get access to p[i], you actually get access to p+i. If i==-1, you just get access to p-1 segment of memory. Yes, it will be not working when p+i points to address with too low or too hight values — for example, -1000 or even 0.
http://codeforces.me/contest/723/submission/21152846
RTE on 13 ... But I'm not sure in what situation I'll acess invalid position since everytime I get to a border cell in the first floodfill I'll stop it and wont't get to any neighboor and my second floodfill never access border cells since I only call it on lakes.
If you insert an extra border of water(`.'), presenting an ocean, around 4 sides of the area, there will be no runtime errors as "i" can go from 0 to n+1, and j from 0 to m+1. First of all, visit the (0,0) which is the ocean, then proceed with the main area. http://codeforces.me/contest/723/submission/21156099
.
how to solve C?
answer is n / m
Alternate solution to O(N2) brute. Binary search on answer, let us say current value to test is X, it is possible to get this value if there are elements that are either ≤ M and have occurrences more than X. Elements > M are always replaceable. Once you know the answer, simply change the minimum number of values in array. NibNalin has implemented this and got AC: 21146185
Or you could do it in linear time ...
http://codeforces.me/contest/723/submission/21145309
(Some comment mentioned this solution before me) You can solve it using binary search to get the maximum minimum element,
if band > m or if totalsongs of band > MID , you can take from it .
else you must give songs , if taken >= given , return 1;
next step is to just swap elements in the array until all bands from 1 to m reach MID;
Once again, very nice problemset! I really enjoyed the contest, although I couldn't do D — my approach was with DSU, however there's some tiny mistake in my code that I didn't find...
When you submit in the last couple seconds of the contest only to get WA because you put "YES" rather than "Yes"... sad times.
Is div2E a flow-related question? The small (n,m) constraints looks suspicious to me.
it should be impossible,because people who passed just used 15ms with less than 10kb
pls help me with D
I got into many dfs but failed...
http://codeforces.me/contest/723/submission/21154778
I think if lake's cell include boundary( (X, 0) or (0, X) ), it called ocean. so my solution is at first boundary DFS to remove ocean. http://codeforces.me/contest/723/submission/21152609
misread D as transforming land to water to reduce the lake number, and struggleed for 90 min to write a complicated solution and found I was so stupid...
Same issue!
I read like that at the first too XD
+1
quick editorial .
But we can't open it yet. :/
(or at least I can't. It says "not allowed")
aaaand editorial removed. ¯_(ツ)_/¯
Maybe my English is too poor. Can't understand problem C at all.
I spent 30 min understanding it too.
You can see the examples first which can help understand better.
Will system test start right away? Or With some delay? Thanks in advance
Right away. :)
The quick editorial makes this contest best ever
It's the second time that I come up with a solution to a problem several minutes after contest ends... sad :(
Look at the bright side you did come up with a solution!
in problem D:
"and it's impossible to add one more water cell to the set such that it will be connected with any other cell"
Before clarification, I overthink that statement and after complicated process implying that the river can't have hole, can't fork, and can't turn, LOL. Thanks for fast clarification btw, save me much time :)
It took lot of time to understand problem statement for C. Because of this I could not implement problem D :(
The contest has nice set of questions. Hope to see more rounds from fcspartakm
EDIT Now problem C fails System Test. I think I should have given time to problem D
It costs me much time to understand the mean of the Announcement,and i just realized that it is no use to me after passing the PTs...I think the most difficult part for me to solve the problem C is the EN. (:P)
I know that it isnt related to this contest, but I am wondering my rating is 1318 pupil even though i got specialist at my first game i am 14 years old and i honestly wonder if i am doing good of i should improve my skills to meet standards?
You are doing excellent. At your age, i had not even touched the computer,let alone programming. Just keep doing it everyday, who knows you may be a legendary grandmaster someday.
age*
Thanks.
Problems are very interesting, hope more rounds from fcspartakm!
Is anyone read statement of D and think statement require replace land by water instead of replace water by land like me ?? f*** my very bad E !! PS : Can anyone solve problem D like my mistakes =))
How to prove greedy works for E?
Randomly taking edge and orienting all edges to satisfy nodes with even degree gets AC. How to prove this is correct? Also, if this is indeed correct why is constraint on N so low? I got misled into thinking solution is something via MCMF. Example: 21156793
Maybe the low constraint is just to distract us from thinking about a greedy approach lol
Why do you have a separate account for commenting ?
Pls help me, problem D
I got WA on test 7:
http://codeforces.me/contest/723/submission/21158564
IS all python solution for D get RTE because of recursion depth limit reach ?
Very hard to understand problem C. I wasted about 30 mins after it. Then let it go, solved D. Now I regret why I did not read problem D without wasting time after problem C. -__-
Why aren't editorials written before the contest and published as it ends?
I just changed an array's size from 1000 to 2000 in problem D and got AC after the contest :((
Why do you need an array of that size ? Can I see your submission please ??
To see someone's submissions, go to user's profile Dabagh, and click the SUBMISSIONS menu item.
Nice problemset ... Specially C & E ... overall Nice contest waiting for rating change !!!!
the idea of the most tricky problem
which one was the tricky one ?i'm so hungry when i programed
The pretests for F may be too weak. With a wrong character in my program, it got pretest passed and pass 47 tests. So to me, it's a little bit surprising to see so few hacks on F after finding such a silly mistake in a pp program.
Indeed, I also did a silly mistake, I was using two variables ct and dt. ct was the counter of how many edges I have used thus far, and dt the upper bound given in the problem. I accidentally increased dt by one when adding an edge in one case and it still got to test 48.
After the contest I was able to fix the bug, it would've meant a good rating increase in my case. But to a certain extend it's our fault, Even if we get Pretest Passed we are all aware that there may be bugs in our code. I think the reason why you and me didn't get hacked is that not many people solved it, and a vast majority of the ones that did were red/yellow coders that got in for fun and not rating.
I found problem C's writing quite poor.
What was the purpose of writing "Polycarp likes bands with the numbers from 1 to m, but he doesn't really like others."? Was it to confuse people???? Why, if Polycarp does not like numbers greater than m, are there playlists with such numbers (test case 7)?
This is totally ambiguous and this should have been made explicit.
Same argument! If he did not like others then why should they be included in the playlist?
My solution for C got one line in wrong ordered which should give wrong answer to many of the tests but somehow passed the pretest then system test got me. :( Now I cannot tell whether I'm extremely unlucky or extremely lucky. Xp
FEELSBADMAN
My fortune is that I didn't read D statement. It was clear from input/output and clar.
Problem C's statement is so silly and confusing i couldn't even understand it till the end of the contest .
Falling in the deep .
This is a very, very, very exciting and thrilling round!
C is failed for...typo?(confirmed, "m" should be "per")
E is failed for missing a if statement in dfs process to judge the starting point of circle.
UPD: F is only one statement away to get Accepted (I missed a statement like "a--").
The rating, certainty, will drop. But I have got so much fun.
My problem F was one submission away to get Accepted ! In final minutes I tried to submit it but Internet connection failed !! After system test I submitted my code and I just wanted my solution to get a wrong answer and guess what, it is an Accepted :(
Horrible problem statement for C. Why are bands numbered more than m included in the play list if he doesn't like numbers > m?! I solved the question in 1h10m then got a test case for which my solution printed values greater than m.
so I tried to fix that for the rest of the contest without even trying D question.
Had the question been clear I could've used the remaining time to try D. Just pathetic problem statements.
Yes,he doesn't like numbers>m.This is why he want to change the playlist.
Same Argument!
Why does he even include bands with > m if he doesn't like them? :(
Your first goal is to make every band you like appear at least k times (k is the maximum min-value of bi, and should be ceil(n/m)).
You should assure the first goal, and then get the minimal times of operations.
In some cases, you can let go some music from the band you don't like to make your times of operations smaller.
Take this example:
n = 5, m = 2, k = 2, original list: 998, 1, 1, 2, 2.
You have already assured the first goal. Then you need to get minimal times of operations. And clearly you can just let go 998.
547D has the same idea with problem E.(But 547D have very different statement.) Everybody can try it. XD
That's an extremely exciting party!
I met a very strange problem, it cost me a lot of time and badly affect my standing. I still cannot figure out what the problem is. It's problem B. I ran it correctly locally but it could not even pass pretest 1. And When I debug it on code forces, it became very weird.
This is is my code for problem B. You can see the line I commented. If I uncomments it, it outputs correct number for pretest1. However, when I comment it, it outputs 13 or 7 sometimes randomly.
Please take a look at these submissions: my submission1 my submission2 my submission3
Is this a bug? Again, when my code runs locally, it outputs correct answer. Hope someone could help me. What's wrong? It drives me crazy!
looks like your memset isn't working correctly for characters. Here is your updated code 21171271
Thanks a lot!
I first misunderstood problem D and thought that I'm allowed to change " * " sign to ".". I found this problem interesting but couldn't come up with any solution.
My thoughts: calculate the minimal distance between each pair of lakes, and we get a complete graph with O(n2) vertices and O(n4) edges. Then the task will be to connect the vertices into k parts with these edges, with minimal cost. We apply a Kruskal's algorithm but stop after initial_lakes - k operations, thus we get a spanning forest with k trees. The overall complexity will be but with a rather small constant factor since the number of initial lakes can be at most n2 / 4.
590C - Три государства This problem uses a similar idea FYI.
Maybe there are some details in it. For instance,here is a graph.
There are 3 lakes now,but if k=1,then the best answer is to change the block in the middle. However,the distances between the lakes are all 2.
My fault - -||… The approach for handling this in 590C is doing a BFS from each cell but it doesn't seem to work with tens of lakes here, so the algorithm above doesn't work for all cases… I feel this is somehow linked to the rectilinear Steiner tree problem so will it be NP-hard?? I have to think it over, thanks for pointing out.
Yes I also think that it's similar to rectilinear Steiner tree problem. So yes, may be it's NP-hard.
It's a perfect time,especially for the Chinese! It's the first time that there's even no hacks in my room!How tricky!
Hi! I tried to attempt 375D, and this is my solution: http://ideone.com/VtXhW5
I've tried really hard to debug it and gives strange outputs on ideone and something very different(and coloured) on another online IDE. Could someone please help me out?
The bug that’s causing memory corruption is probably in line 59: you meant to compare
a[i][j]=='.'
, but you’re actually assigninga[i][j]='.'
. This probably leads your program to see parts of the ocean as lakes (because it hits previously visited cells before it has a chance of hitting the edge of the grid) and then write past the end of thea
andmark
arrays inffill
.Also, why are you iterating and searching through coordinates 0 to n inclusive and 0 to m inclusive? You visit coordinates that simply do not exist. This does not cause memory corruption, because your arrays are large and fully initialized; but
a[i][m]
anda[n][j]
are always equal to'\0'
, which means you’ll never callchecklake
on these coordinates (except in line 61 until you fix the assignment bug in line 59), which means you’ll never hit thex==n||y==m
condition in line 14, and so your program will think that any piece of ocean that touches the bottom and right edges of the grid but not the top and left edges is actually a lake and therefore produce a wrong answer. Change this condition tox==n-1 || y==m-1
and change all inclusive loop ranges to exclusive.Thankyou so much! The assignment operation was a very silly mistake. I've changed that, and I'm getting a wrong answer now. http://codeforces.me/contest/723/submission/21189917 I've realised that there's two . connected to the ocean that my code is still covering and considering that as a lake which is giving me a wrong answer. When scanning through the second row, the code should return lake as false when the call for checklake(x,y-1) would give false but the visited array already has it filled, and it doesn't check for that. What would be the best way to handle this?
Ah. You shouldn’t return immediately after setting
lake=false
. By doing so, you miss the rest of the lake. Instead, you’ll need to add an extra check to make sure you don’t go past the edge of the grid, i. e.if (x<0 || y<0 || x>=n || y>=m) return;
at the very top ofchecklake
.In this test, when you’re scanning the second row, you don’t call
checklake(x,y-1)
at all!visited[x][y-1]
is already true, as you made it so when you scanned the first row.