### awoo's blog

By awoo, history, 4 years ago,

Hello Codeforces!

On August 21, 18:05 MSK Educational Codeforces Round 27 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov, Vladimir vovuh Petrov, Mike MikeMirzayanov Mirzayanov and me.

Good luck to all participants!

Harbour.Space also has a word for you:

We are delighted to welcome the 2017 ACM-ICPC World Champions, ITMO, to our 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC starting September 27.

All the top Russian teams are coming, including St. Petersburg State University, MIPT, Ural Federal University, Tomsk, Novosibirsk, Saratov and Perm, as well as the world’s top universities such as Waterloo, Central Florida, Hangzhou Dianzi, Singapore, KTH and dozens of others — so far teams from 30 countries have signed up.

The event’s gold sponsor is Sberbank, the biggest commercial and investment bank of Eastern Europe and Russia. Thanks to their support we expect that the top participants will be awarded valuable prizes, alongside high-profile internship and job opportunities.

We can’t wait to see all of you coming to learn, practice and compete on the international stage, smoothing your road towards April World Finals in Beijing.

Ps. Registrations close on September 1.

UPD: Editorial is published

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 uwi 7 288
2 quailty 7 314
3 Andrei1998 7 318
4 rajat1603 7 374
5 fatego 7 374

Congratulations to the best hackers:

Rank Competitor Hack Count
1 uwi 455:-11
2 halyavin 305:-4
3 STommydx 103:-2
4 Lhtie 48:-2
5 step_by_step 44:-28

1326 successful hacks and 300 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A ksun48 0:01
B jufusong 0:03
C markysha 0:03
D EKGMA 0:10
E halyavin 0:37
F eddy1021 0:34
G const_int_magic 0:08

• +124

 » 4 years ago, # | ← Rev. 2 →   -13 why is the Announcement too late?
 » 4 years ago, # |   +1 I want nothing but a clear problem set.
 » 4 years ago, # |   -18 Is it rated?
•  » » 4 years ago, # ^ |   0 that's right
•  » » 4 years ago, # ^ |   0 its unrated contest
•  » » 4 years ago, # ^ |   -15 Lucky for you, it is!"Educational rounds" are a GREAT way to increase your rating!I wish you high rating in every upcoming educational contest!
 » 4 years ago, # |   0 What is high-profile internship?
 » 4 years ago, # |   +108 "After the exam Polycarp can justify his rule violations by telling the driving instructor that he just didn't notice some of the signs."Unfunny meme amirite
 » 4 years ago, # |   +38
 » 4 years ago, # |   +43
 » 4 years ago, # | ← Rev. 2 →   0 If contest is over someone check my code:https://ideone.com/A2YNwD QUES:C
 » 4 years ago, # |   0 How to solve E and F?Is this a valid approach for E:2D ternary search to find the placement of the (k + 1)th center of ignition and then binary search to find minimal time. The complexity will be which is about 300 mln operations and should fit in TL. The only thing I'm curious is if the ternary search will be correct.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +32 for E Consider binary search on answer Find leftmost line which will have atleast 1 unvisited cell , similarly find rightmost , topmost line and bottom-most line This is valid if (right — left) <= 2 * x and (bottom — top) <= 2 * x if we are checking for x.
•  » » » 4 years ago, # ^ |   +1 How to find leftmost line and other 3? You find leftmost of these k burning points, and then k — x but problem is if k — x < 0, i mean if that point is pretty close to left border.
•  » » 4 years ago, # ^ |   +16 for F If N > M just transpose it So now N ≤ 15 , so just do dp with bitmask
 » 4 years ago, # |   0 could anyone explain to me the first test in D ?
 » 4 years ago, # |   0 I got WA at Test Case #8 in problem D. Couldn't figure out why?
•  » » 4 years ago, # ^ |   +1 When you get new speed of car, you cant only check last speed limit. You need to have stack with speed limits. Example you have signs with speed limits of 100,120,150 respectively. Then , you drive 160 and you only check last speed limit which is 150. But you also must care about signs 100 120. So , maintain a stack of speeds, go back while speed.top() < curr_speed and increase counter. You can see my solution at my profile.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 So by that, you mean with this test case4 1 50 3 50 3 100 1 60The ans 0 instead of 1? Could you explain to make more sense to me or point out which part of the problem exactly define this criteria? Thanks
•  » » » » 4 years ago, # ^ |   0 Of course answer is 0, how can it be 1? You drive 50 while limit IS 50 so its OK, then you switch to 60 while limit is 100, thats OK as well.
•  » » » » » 4 years ago, # ^ |   0 I mean when the speed limits are 100, 120, and 150, and you drive 160, the 100 and 120 is included in the violated signs, right?But, why when the speed limits are 50, 100, you drive 60, the 50 limits doesn't noticed too (unlike above)?
•  » » » » » » 4 years ago, # ^ |   0 Never mind, I've understood it. Thanks anyway
 » 4 years ago, # |   +24 problem G is this with Q = 1
•  » » 4 years ago, # ^ |   +9 The problem was also featured in the Zagreb U Selection contest.
•  » » 4 years ago, # ^ |   0 It was also asked once in the Bayan Finals.
 » 4 years ago, # |   0 41 1003 503 501 50 why is the ans 2
•  » » 4 years ago, # ^ |   0 You only need to remove (or "didn't notice") two road signs to drive without violation
•  » » » 4 years ago, # ^ |   0 even 1 can be the ans because after the second sign he changed the speed!!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yeah, I agree that one is more make sense. But, I've clarified similar question to the problem setter, see below.Question: 3 1 100 3 50 3 50 The ans is 2Question: 3 3 50 3 50 1 100The ans is 2
•  » » 4 years ago, # ^ |   0 Because you are passing two signs with maximum 50 with speed 100.
 » 4 years ago, # |   0 how to solve G ？
•  » » 4 years ago, # ^ | ← Rev. 3 →   +9 If there is a cycle in the graph with cost C, for every path of cost x, there is one with cost x^C.So you can check out all the costs of simple cycles (get a spanning tree and check for each edge) and the shortest paths will be x^C1^C2... where x is the cost of any route you can find.To find the minimum of this value we can translate the problem to linear algebra, the XOR is the same as the addition in Z/2 space, so if we treat these costs as a vector, then we can find a linearly independent set which generate these vectors in the ZMXBITS/2 linear space using gaussian elimination.Now we can simply get any distance from 1 to n, and XOR with the elements of the basis greedily from the most significant bit to the least.
•  » » » 4 years ago, # ^ |   0 what do you mean by "Z/2 space",please?
•  » » » » 4 years ago, # ^ |   0 The Integer modulus 2 vector space
•  » » » » » 4 years ago, # ^ |   0 Is this advanced usage of linear algebra or some bacics? Are problems where u need to use linear algebra conceptually hard (for example this one) or, when u learn linear algebra, its natural after some thinking? Because when I see linear algebra im like wtf who can come up with solution for this
•  » » » 4 years ago, # ^ |   0 Can you please explain me one thing....i understand that gaussian elimination method for minimising xor value but how can we say that number of simple cycles will be atmost 30...because gaussian elimination will take n^2logn(rows=n columns=30 bits)..
 » 4 years ago, # | ← Rev. 2 →   +29 Alert!!! Alert!!! UWI started hacking!!!
•  » » 4 years ago, # ^ |   +3 How can he hack so fast? Just because he is on the leader board of HackerRank?(joking)
•  » » » 4 years ago, # ^ |   0 I taught him actually
•  » » 4 years ago, # ^ |   +3 When you have more successful hacks than penalty!
 » 4 years ago, # |   0 Anyone could kindly explain why Wrong Answer on Test Case 8? Thanks
•  » » 4 years ago, # ^ |   0 in case if t==3 you might be changing previously increased speed in query 1 to -inf and than you pushed the speed limit in stack;
•  » » 4 years ago, # ^ |   +1 Try this test case- 5 1 80 3 120 3 130 3 140 1 150
 » 4 years ago, # |   0 Can anyone tell me how there are this many solutions for G? I saw solution uses linear algebra. Isnt it really advanced topic for competitive programming? Anyone has any materials with codes for linear algebra?Problem E is much easier in my opinion, but has less AC. Also, this is maybe the case because problem G appeared on codechef before (in even harder version).
 » 4 years ago, # |   0 4 1 100 3 50 3 50 1 50 who agrees with me that the answer should have been 1??
•  » » 4 years ago, # ^ |   +6 No one. You drive with speed of 100. You see a sign with limit 50, you dont give a shit, so res++ You see one more sign with limit 50, you dont give a shit again, res++Totally, you must lie about 2 signs, because you didnt slow down TWICE, not ONCE. Result is therefore 2.
•  » » » 4 years ago, # ^ |   0 the second time i see it and change the speed!! i could just say that i didnt see the first sign but as soon as i saw the second one i changed the speed after that!
•  » » » » 4 years ago, # ^ |   0 He changes the speed only when there is a type 1 event, otherwise he keeps the same speed.
•  » » » » » 4 years ago, # ^ |   0 ok so is it like this that i should change my speed before the next speedlimit sign comes?
•  » » » » » » 4 years ago, # ^ |   0 Yes, exactly.
•  » » » » » » 4 years ago, # ^ |   0 Yes. When type 3 appears, it means you already passed sign with given limit. So you need to change speed BEFORE you see a sign.
•  » » 4 years ago, # ^ |   0 If you eliminate one of the speed signals you are left with 4 1 100 3 50 1 50 which is still a violation of the rules (when you cross the 50 limit you are travelling at 100). You need 2.
 » 4 years ago, # |   0 Why there's no sample explanation in problem A,B,C.Thinking a harder version of the easy problems took up most of my time just because I misunderstood the problems!:(
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Or maybe I'm too careless.....
•  » » » 4 years ago, # ^ |   +3 Careless I would say xD I solved first 3 problems in half an hour. This is my best contest ever (place 212. and you see how bad my rating is). So, If u just read carefully...
 » 4 years ago, # |   0 Help me, please!Here is my program for problem D: http://codeforces.com/contest/845/submission/29666261. I tried to solve it using the vector of speed limits. But I get "Wrong_Answer" when the number of events was great.Can you, please, tell me what I'm doing wrong.
•  » » 4 years ago, # ^ |   0 sort(SpeedLimit.begin(), SpeedLimit.end()); 
•  » » » 4 years ago, # ^ |   0 Thank you very much!!!
 » 4 years ago, # |   +5 Almost everone solved problem G in same fashion ( finding basis and all ), is this some standard method for dealing with this type of problems? can anyone give any link to some theory and more problems on it.
•  » » 4 years ago, # ^ |   0 I ask same question....Like LINEAR ALGEBRA WTF?! Olympiad math does not need it but Competitive programming yes..why
•  » » 4 years ago, # ^ |   +8 724G - Xor-matic Number of the Graph features the same idea.
 » 4 years ago, # |   +66 Me Right Now..
•  » » 4 years ago, # ^ |   +70 Cant hide forever :/
 » 4 years ago, # | ← Rev. 3 →   0 7 1 20 2 6 4 6 6 2 In the third example Polycarp should say he didn't notice both "no overtake allowed" that came after "overtake is allowed" sign. Any explain for me? I think it doesn't makes sense.
•  » » 4 years ago, # ^ |   0 If he doesn't say that, then the last overtake would violate the rules (he overtook another racer when overtakes weren't allowed)
•  » » » 4 years ago, # ^ |   0 Thanks, I got AC
 » 4 years ago, # |   +1 Now its halyavin.. :3
 » 4 years ago, # |   0 Can someone provide a test for which this doesn't work? http://codeforces.com/contest/845/submission/29651836
•  » » 4 years ago, # ^ |   +3 3 1 5 2 3 5 6
•  » » » 4 years ago, # ^ |   0 Yup, that's right, cheers
 » 4 years ago, # |   0 Full test cases are visible even when 24 hour hacking phase is running, but they should not be visible.
 » 4 years ago, # |   -9 Is this contest rated?
 » 4 years ago, # |   0 Could someone point out where my code for problem-D is giving error? Link is https://www.ideone.com/VjSB5c Thank you.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's not enough sometimes to delete the previous sign. For e. g. if there is a speed limit sign of 50, then a speed limit sign of 30, and after that he goes with 100 speed, then in your code he only has to say he didn't see the 30 sign, but then he should think the speed limit is 50, so he is still speeding.Also you don't reset the speed limit after deleting a sign, so if there is a 30 sign, he goes with 50, then he goes with 70, then you add 2 to ans instead of 1. Solution:You have to store all previous signs, as pointed out in the editorial.
 » 4 years ago, # |   0 I am gettting RUNTIME ERROR on test 8 Problem C . COde