Hello, Codeforces!
I'd like to invite you to Codeforces Round #386 (Div. 2). It'll be held on Sunday, December 18 at 13: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 municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU.
Great thanks to Nikolay Kalinin (KAN) for helping me preparing the contest, to Tatiana Semenova (Tatiana_S) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Vladimir Petrov (vovuh), Alexey Ripinen (Perforator), Mikhail Levshunov (Levshunovma), Mikhail Piklyaev (awoo), Aleksey Slutskiy (pyloolex), Ivan Androsov (BledDest), Oleg Smirnov (Oleg_Smirnov) and Roman Kireev (RoKi) for writing solutions and editorials.
It will be a little unusual round — you will be given seven problems and two and half hours to solve them. The scoring distribution will be 500-1000-1500-2000-2500-3000-3000. Good luck everyone!
UPD Editorial
UPD2 Congratulations to the winners!
Time of contest is clashing with https://atcoder.jp/. Please reschedule..
If you want atcoder to reschedule why you posting it here? :)
Wow, the first time I see the score distribution early like this. Hope this with be a good contest.
Wow, the first time I see blog about the contest late like this.
Sunday**
Hope the translation will be good!
Excited! My color will be changing today.
Mine will too! (I hope not though)
I hope you will
I am sorry for you bro :(
Yes, Maybe tomorrow!
Wow, seven problems!
Hope to see some data structures
haha not as you wish :)
Why so strange hours? And, as someone mentioned earlier, clashes with atcoder :c.
7 problems?!! Couldn't there be a division 1instead? :3
Maybe it's too easy for div1 users.
Then a combined round could do the trick ..
Mikhail Piklyaev awoo 's graph is so awesome :O
seriously awesome and motivating graph :)
Hard work pays off,sooner or later.
Looks like awoo have had the experience of all the ranks. From falling to grey and then rising again. Really motivating.
If only ranks up to candidate master were all of them :( It's still a really long way to grandmaster.
Luckily I didn't fall to div2 today, so I can just solve some problems and then participate ARC066 :D
Hope that Tatiana does good job or we will have problems as #385's Div2B.
I hope I can understand the statement:D
I hope no one here asking "that" usual question..
Is it rated?
Why Not ?
Because the round is based on the tasks of an Olympiad. So, unless the round is a mirror of the same contest, it should be unrated.
Do you have the questions ? LOL
I don't, but someone else might have. Don't you think that'd be unfair?
True that !
Just right after I said it. How irony...
Was supposed to be a reply on your comment only. :p
Very Unusual time :(
Wow, Seven problems. Hope it will be an exciting contest and my color will change(from green to grey or cyan).
I am confused! Is it rated or not?
Regular round always rated.
see the.......... usual Div. 1 participants can join out of competition. That means it will be rated on.y for Div. 2
Can the answer in Div2C only be integer?
yes!
Hacking didn't work for me this contest, I kept getting "Submit already challenged", and hack would not go through. :(
Also for A somehow I guess I double clicked submission button and so it submitted same code twice, with the first one counting for the resubmit penalty, does this always happen? Typically I think it prevents from submitting same code twice, but sometimes it allows?
Seriously though does anybody know what it means when "Submit already challenged", but it has clearly not been challenged by anybody else.
I was trying to hack skorpioas the whole time and it would not let me :( I tried both Chrome and Safari :(
what could be the test 9 on problem D?
Why there are some Experts participating as out of competition?
Probably because they missed the registration, which ended 5 minutes before start of contest
dude I registered yesterday ...
Add to that my submission for A was at min 3 which means I didn't register with extra registration
I tried to hack problem C with the following input 5 4 0 1 2 5 -1
And it says Invalid input with the following message = "Validator 'val.exe' returns exit code 3 [FAIL Integer parameter [name=p] equals to 5, violates the range 1, 4]"
Isn't this input supposed to be valid? Does this mean the train can only go up until point s-1?
train can go uptil 0 and s But the input constraints say current position is from 1 to s-1 So input position cannot be s
endl's between numbers
I was facing the same problem until I put endlines as they have done in the input. Also your constraints are wrong.
It was mentioned in the constraints that 1<=p<=s-1. Although the train can still go to point 0 and s, you cannot have those values as your initial position.
Oh right, I didn't see the constraint. Thanks everyone for clarifying
Editorials?
Task were much more tehnical than hard...
I was so near to solve G :(
Why this outputs are wrong for E problem ?
INPUT
6 2
5 6 7 9 4 5
OUTPUT
1
5 6 7 9 4 1
INPUT2
8 6
7 7 7 7 8 8 8 8
OUTPUT2
6
7 3 1 2 8 4 5 6
there are 4 odds (5, 7, 9, 1) but only 2 evens(6, 4).
it seems that it's valid.
Number of odd number cards should equal to number of even number cards
Why I have to choose task number every time when I submit? Because of that I sent my solution to wrong problem. So sad :(
Well, you can upload directly from the problem's page.
WTH????!!!!
I'm guessing its a glitch.
There were some reports yesterday about people who dropped below 1900 after the contest but still retained their colour.
Yesterday I got to green but my rating was still in grey. Some kind of bug I guess.
he gained the rating as well :)
Sorry about that. I've registered as usual. I wrote to Mike. Hope he will fix it and there will be no rating changes for me. Also I didn't try to hack and no one hacked me.
The same happened to me (although i lost rating) and i've wrote to mike too. I hope it will be solved or that it didn't affect others rating too negatively.
I always get too slow while implementing problems like C. Hope the editorial explains clear thoughts on how to solve such problems correctly and faster.
Yeah simulating the situation is pretty tough to implement but I'm not sure the intended solution is through simulation. I just used a bunch of if statements to solve it.
Your solution is really well analysed. My code missed AC just bcoz of single line. I forgot to check that the tram can be at x1 in the beginning. ;_;
Exactly, It seems like more of math and less of logic , but yes i too want too learn how to solve such problems. I was thinking keeping this problem As Fast As Possible in mind but solution was a bit different.
Todays problem reminded me also of the problem you mentioned. I guess implementation is still a challenging task to work upon in CP.
I believe the idea is an event queue. When the tram passes by x1 or x2, we track that event.
So, we could have 2 event queues:
We are interested in events of second type
event_time_x2
, when tram passes by our target location. We just need to simulate tram's movement until we collect 2 events in the event queueevent_time_x2
.After that we compare the times contained in the queue
event_time_x2
with the Igor's time when he is just walking to the target. If event_time_x2[0] ≥ walking_time, then there is no point in taking tram at all. If event_time_x2[0] < walking_time, then we need to track whether it was possible for Igor to get on the tram before tram has reached the target at event_time_x2[0]. To check that — we need to find the time, when the tram crossed Igor's location x1. If there was no event of crossing x1 location before the event event_time_x2[0], then it was not possible for Igor to reach target location x2 at the time the tram reached it event_time_x2[0]. After that, we check the second event.I failed on test 18, but I believe that my idea is correct. Probably I had to collect 3 events instead of 2.
UPD: Yes, we need to store 3 passes of the tram: 23107366
Same with me :(
in C turns out you only need to consider 2 cases:
walk all the way
wait in x1 untill tram comes, then ride the tram
here is my ac code
http://mirror.codeforces.com/contest/746/submission/23108354
WA problem C test 23 )= someone else?
WA too tc 19 ):
WA on 23 :'(
Noo!! it's the case when they start in the same position! I am so stupid!
I also had troubles here. Test case 23 starts with the train and the person at the same square, so that you can board the train instantly.
So I would guess that you (like me) have a "> 0" in your code somewhere that should be ">= 0"
That feeling when your solutions failed on system testing on problems C,D but submission on problem E got AC. And you went from 374 place to 1135. My ass is burning!!!
Haha, similar thing happened to me. A,B,C passed and D,E failed.
The difficulty is not sorted alphabetically.
do you mean for F and G or the whole contest?
I believe G was even easier than E... My personal opinion...
Amazing Contest...
Good doable questions...
Thank you Writers :D
The problem statement doesn't mention anywhere that the result will be an integer right? 23102907
The same reason prevented me from even starting to implement C.
same here
I think problem E has weak testcases.
Example:
The answer should be something like:
My program outputs:
Can someone explain why did my code fail?
23085756
I had the exact same doubt.
Unsigned integer underflow
When str.size() = 1, then this value goes to a very large value.
so I failed 2 contest in 3 hours ...
Access denied to editorial :(
Use this link: http://mirror.codeforces.com/blog/entry/49160
Would this contest be scored?
Is the Editorial accessible? I am receiving "Access Denied".
Use this link: http://mirror.codeforces.com/blog/entry/49160
I wish we had more time, like 3 hours.
What happens when "Bad Luck" is your best friend??? Compare these submissions- 23086486 and 23105642
Thank you for a really awesome contest!
I am getting WA in pretest 9. Can you please provide a smaller but equivalent test case? My submission: http://mirror.codeforces.com/contest/746/submission/23106759
19 2 7 12
that moment when increased rating on div2 contest being div1
Can't access editorial
Use this link: http://mirror.codeforces.com/blog/entry/49160
Thanks :)
Limits of problem C are too small ,So some solutions passed by simulation.
access denied on clicking editorial ?
Use this link: http://mirror.codeforces.com/blog/entry/49160
Thanx a lot mate :)
sorry