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 | ygmngm817 | 0:03 |
C | markysha | 0:03 |
D | EKGMA | 0:10 |
E | halyavin | 0:37 |
F | eddy1021 | 0:34 |
G | const_int_magic | 0:08 |
why is the Announcement too late?
I want nothing but a clear problem set.
Is it rated?
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!
What is high-profile internship?
"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
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.
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.
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.
for F If N > M just transpose it
So now N ≤ 15 , so just do dp with bitmask
could anyone explain to me the first test in D ?
I got WA at Test Case #8 in problem D. Couldn't figure out why?
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.
So by that, you mean with this test case
4 1 50 3 50 3 100 1 60
The 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
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.
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)?
Never mind, I've understood it. Thanks anyway
problem G is this with Q = 1
The problem was also featured in the Zagreb U Selection contest.
It was also asked once in the Bayan Finals.
4
1 100
3 50
3 50
1 50 why is the ans 2
You only need to remove (or "didn't notice") two road signs to drive without violation
even 1 can be the ans because after the second sign he changed the speed!!
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 2
Question: 3 3 50 3 50 1 100
The ans is 2
Because you are passing two signs with maximum 50 with speed 100.
how to solve G ?
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.
what do you mean by "Z/2 space",please?
The Integer modulus 2 vector space
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
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)..
Alert!!! Alert!!! UWI started hacking!!!
How can he hack so fast? Just because he is on the leader board of HackerRank?(joking)
I taught him actually
When you have more successful hacks than penalty!
Anyone could kindly explain why Wrong Answer on Test Case 8? Thanks
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;
Try this test case-
5
1 80
3 120
3 130
3 140
1 150
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 1 100 3 50 3 50 1 50 who agrees with me that the answer should have been 1??
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.
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!
He changes the speed only when there is a type 1 event, otherwise he keeps the same speed.
ok so is it like this that i should change my speed before the next speedlimit sign comes?
Yes, exactly.
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.
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.
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!
:(
Or maybe I'm too careless.....
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...
Help me, please!
Here is my program for problem D: http://codeforces.net/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.
Thank you very much!!!
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.
I ask same question....Like LINEAR ALGEBRA WTF?! Olympiad math does not need it but Competitive programming yes..why
724G - Xor-matic Number of the Graph features the same idea.
Me Right Now..
Cant hide forever :/
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.
If he doesn't say that, then the last overtake would violate the rules (he overtook another racer when overtakes weren't allowed)
Now its halyavin.. :3
Can someone provide a test for which this doesn't work? http://codeforces.net/contest/845/submission/29651836
3 1 5 2 3 5 6
Yup, that's right, cheers
Full test cases are visible even when 24 hour hacking phase is running, but they should not be visible.
Could someone point out where my code for problem-D is giving error? Link is https://www.ideone.com/VjSB5c Thank you.
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.
You have to store all previous signs, as pointed out in the editorial.