### dalex's blog

By dalex, 9 years ago, translation,

Hi all!

Today, June 12, when Russia celebrates Day of itself, Euro 2012 second round starts and I_love_natalia has a birthday, we present you Codeforces Round #124.

Contest was prepared by team Samara SAU Teddy Bears (craus, dalex, Hohol) and I_love_natalia. Also thanks to Alex_KPR and Codeforces team (Gerald, Delinur, MikeMirzayanov). We think that contest is very easy, and your task will be prove of refute this assertion :)

Authors think that problems are sorted by difficulty in non-descending order.

Accepted solutions and successful hacks to you!

UPD. Contest is over, congratulations to the winners!

Div-1 (full results):

1. tourist — the only one who solved all problems!
2. RAVEman
3. aropan

Div-2 (full results):

UPD 2. Tutorial is available.

• +168

 » 9 years ago, # |   -50 Will the contest be ranked?
•  » » 9 years ago, # ^ | ← Rev. 2 →   -17 contests are rated normally :-/
•  » » 9 years ago, # ^ | ← Rev. 2 →   -45 vse deleted
•  » » » 9 years ago, # ^ |   -10 Don't even think about that!
 » 9 years ago, # |   +18 In ascending order by difficulty?
•  » » 9 years ago, # ^ |   +13 The authors believe so.
•  » » 9 years ago, # ^ |   +16 No, non-descending :)
•  » » » 9 years ago, # ^ |   0 :D
•  » » » 9 years ago, # ^ |   0 I'm not sure if the smiley indicates irony or that sweet feeling of disagreeing with the master, but for me the order actually seemed descending in difficulty (div2).
 » 9 years ago, # |   0 The contest doesn't seem to me as very easy :/
 » 9 years ago, # |   0 Subject narrative is a big problem！ It's too fuzzy to read...
•  » » 9 years ago, # ^ |   -7 wo ca
•  » » » 9 years ago, # ^ |   0 are you chinese?
 » 9 years ago, # |   +1 What was the solution for Div2 problem A? I feel I'm missing something easy.
•  » » 9 years ago, # ^ |   +3 If at least one circle can be placed in the rectangle, then first wins, because he can place circle in the center and then play symmetrically. In other case second wins.
•  » » » 9 years ago, # ^ |   +1 Wow. So nice! :) (btw, we were in the same room)
 » 9 years ago, # |   0 Nice questions...Short uncontradictory statements and all requiring to think..Although I did not perform well but still I got to learn a lot :)
 » 9 years ago, # |   +1 Can someone please explain logic behind div 2 — A.
•  » » 9 years ago, # ^ |   0
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 I took few cases , and In every case If FIRST can place the circle inside the rectangle then He can win otherwise , He can not win.Some idea might be thought like if there are even no of circles possible in the rectangle , then He can just place a circle midway of two circles ,,, Means He can always change the configuration for winning move. more clearer : if in the optimal path , if there are even no of circles inscribed in rectangle , then First can change the path by placing a circle midway of two circles . otherwise FIRST will win because last movement will be of FIRST , because no of turns are odd .
•  » » » 9 months ago, # ^ |   0 if like the input is 17 6 3 then in this wherever first place the circle there are 2 circle possible so seccond win
 » 9 years ago, # |   0 for problem D , can anybody tell me whether my idea is correct ?? for grid with position S if you are able to go to another S in it's adjacant 4 grids , Then I can walk infinitely , ans will be YES, other wise No
•  » » 9 years ago, # ^ |   +3 No. 3 16 .##..##..##..##. #...#...#...#... S.##..##..##..## 
•  » » » 9 years ago, # ^ |   0 thank you for your reply , Firstly I had an idea that if an (3 * n ) * (3 * m) grid ,,, We can go from one S to some other S then we can find a infinite cycle ,, But this used too much memory and got memory limit exceeded :(
•  » » » » 9 years ago, # ^ |   0 i used the exactly idea that create an (3*n)*(3*m) maze. and while searching in the 9 times larger maze, i just terminate the process as soon as i find two 'S', then, i got an AC:) I just tried waht happened if i waiting for the searching process until it is finished, then, i got a MLE:(
•  » » » » » 9 years ago, # ^ |   0 Do you mean two 'S' including the stating 'S' (in the central block)? In other words, the starting 'S' and at least one another?
•  » » » » » » 9 years ago, # ^ |   0 Yes. Actually, which 'S' is the starting one does not matter. But when you arrived a "border" of the larger maze, you should transfer your searching position to the oppsite "border" —— it does matter a lot :)
•  » » 9 years ago, # ^ | ← Rev. 6 →   +3 No, example: ##.# ...# .### .#S. ##.# 
•  » » 9 years ago, # ^ |   -9 I think if we can go to any of the 'S' of 8 adjacent grids then it "Yes"
•  » » 9 years ago, # ^ |   0 only itself is sufficient..
 » 9 years ago, # |   +7 "We think that contest is very easy" You are kidding, aren't you?
 » 9 years ago, # |   +7 I wonder how many people just guessed the answer to div2-A, without actually proving it. (I got to a proof, after I finally submitted the guessed one.)
•  » » 9 years ago, # ^ |   0 may you explain your proof?
•  » » » 9 years ago, # ^ |   +6 If First player can place even one disc, answer is "First". Since first player can always win by placing first plate at center of board. Then he can copy the moves of second player . (Because there will always a similar space available due to symmetry)
•  » » » » 9 years ago, # ^ |   0 WOW, nice proof :)
•  » » » » 9 years ago, # ^ |   0 brilliant, love it!! so elegant!
•  » » » » 9 years ago, # ^ |   0 i tried hard to got the logic.finally i got it by your nice idea.
 » 9 years ago, # |   +14 Happy birthdays dalex and I_love_natalia! The problems are nice. By the way, the start time is unusual, that makes me late for some minutes.
•  » » 9 years ago, # ^ |   +5 Actually, only I_love_natalia has a birthday today...
•  » » 9 years ago, # ^ |   0 1 hour after contest is a football match in group A in Euro2012. In this group is Russia too :)
•  » » 9 years ago, # ^ |   +3 ...I started the contest about 15 minutes later... To my surprise, I was in the top 20...... I had once thought that my rating would have descended dramatically... So strange...
 » 9 years ago, # |   +1 Div1-A is exactly the same as SRM 518's Largest Subsequence, except that the constraint is larger... This might have given unfair advantage to those who have seen it before.
•  » » 9 years ago, # ^ |   0 And there's also one task from COCI that's really close to it.
 » 9 years ago, # |   0 You will have to add a new level above IGM.
•  » » 9 years ago, # ^ |   +64 I think that the only way is to add 'tourist' level for tourist.
•  » » » 9 years ago, # ^ |   0 An extra problem, only for tourist... Almost half an hour he was free, after solving the five problems.
•  » » 9 years ago, # ^ |   +29 Aliens.
 » 9 years ago, # |   0 Hello, I suppose it's better if you use just ordinary math. not something that like limit. I don't have any information about it. It's better if you would use some algorithmic problem or other problems related to programming instead of pure math. just my recommendation. I'm not a very professional participant. just participating here and don't know about other places. it's just a recommendation. and anyhow I appreciate your hard work for creating such a great contest. thanks.
•  » » 9 years ago, # ^ |   0 Actually, the solution was given in the link below the test cases explanation.
 » 9 years ago, # |   +6 really liked the content, although i found it difficult. particularly task A, which in my opinion was rather the hardest than the easiest... good job, guys!! :)
 » 9 years ago, # | ← Rev. 3 →   0 Any idea why my practice solution for div1 E TLEs (http://codeforces.com/contest/196/submission/1798783 ), while RAVEman's (slightly modified version: http://codeforces.com/contest/196/submission/1798819) easily passes? Both use Prim's algorithm in almost the same way. I went over his code line by line and can't find the key improvement.
•  » » 9 years ago, # ^ | ← Rev. 2 →   +9 I found 2 reason. 1. set is slightly slow than priority_queue so you solution take much more time. 2. test case is not strong enough. the way you choose start vertex is different from RAVEman (Reminder : portal might not be in order in input), he's lucky so choose largest portal number pass in time, but choose lastest portal number (in input) not.After I fix #2 in your code to the same way as RAVEman , it's TLE at test case #39 1799522 and after I fix both #1 and #2 it's pass in 300 msUPD. fix font size
•  » » » 9 years ago, # ^ | ← Rev. 3 →   0 That's bad, I was too imprudent :( These solutions get TLE on 'reversed' test 36 where any vertex i is renamed to n - i + 1.UPD: New tests (76-95) were added. Try to pass them.
•  » » » 9 years ago, # ^ |   0 Thanks!! I'm surprised set vs priority_queue would make such a big difference. TopCoder's STL tutorial says "the difference is about ~%0.1 of time", yet RAVEman passed test case #39 in only 50 ms. When I tried his code with set 1798838, it failed case #39.As for the other reason, it seems the problem is that non-portal vertices can be visited multiple times. I haven't thought of a solution for this yet...
•  » » » » 9 years ago, # ^ | ← Rev. 6 →   +8 Actually, the set vs priority_queue issue might just be another vertex ordering problem in disguise. Submission 1801347 also fails case #39 even though the only change from the "modified RAVEman code" in my first post is changing the priority_queue< pl > to a priority_queue< pl, vector< pl >, greater< pl > >.
•  » » » » » 9 years ago, # ^ |   +8 Alright, someone explained the real solution so I went ahead and implemented it! The trick is to make a sparse version of the graph of vertices which have portals. The "edges" in the portal MST will be shortest paths between pairs of portals in the original graph. There could be n^2 of these, but we don't actually need them all. MST edges are always minimum weight among edges in some cut of the graph. This solution is guaranteed to include all such edges.
•  » » » » » 9 years ago, # ^ |   +9 Yeah, I just got lucky. I had just 15 minutes after I submitted D till the end of the round, so I decided to submit the most stupid solution that I could think of... Usually that strategy works pretty well for me :)And thanks for noticing the crap I wrote. This made me read the editorial to understand the intended solution.
•  » » » » » » 9 years ago, # ^ |   0 Defeating the judge in 10 minutes is quite amazing ;)It's nice to see a growing community around programming competitions; I still have lots to learn from all of you! (this was my first time coding MST)
 » 9 years ago, # | ← Rev. 2 →   +1 In Div-2 Problem-B:Test Case: 8 3 2 4 3 1 2 -5 7 0 Why the answer is "-Infinity" instead of "Infinity"?
•  » » 9 years ago, # ^ |   0 Look at this: Evaluating limits at infinity for rational functions
•  » » 9 years ago, # ^ |   0 Because n > m and a[0] * b[0] < 0
•  » » 9 years ago, # ^ |   0 You can simply draw a chart ;-) for example for x in ( 10, 30, 100, 300, 1000 ).
 » 9 years ago, # | ← Rev. 2 →   +20 InputcantouristsolveitlessthaninoneminuteOutputunfortunately, he can'tbut he solved all problems less than 100 minutes
 » 9 years ago, # | ← Rev. 3 →   +4 /*found my mistake*/
 » 19 months ago, # |   +3 right
 » 5 weeks ago, # |   0 Can any one tell what i did wrong in infinite maze problem ? some test cases are failing public class Div2D197 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); char[][] arr = new char[n][m]; int si = 0; int sj = 0; for (int i = 0; i < n; i++) { String s = sc.next(); for (int j = 0; j < s.length(); j++) { arr[i][j] = s.charAt(j); if (arr[i][j] == 'S') { si = i; sj = j; } } } boolean[][] vis = new boolean[n][m]; boolean ans = getAns(arr, si, sj); String op = ans == true ? "Yes" : "No"; System.out.println(op); // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // System.out.println(arr[i][j]); // } // } } static int xdir[] = { -1, 0, 1, 0 }; static int ydir[] = { 0, -1, 0, 1 }; public static class Pair { int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } } public static boolean getAns(char[][] arr, int si, int sj) { Queue qu = new LinkedList<>(); qu.add(new Pair(si, sj)); while (qu.size() > 0) { // rmwa Pair rem = qu.remove(); // mark if (arr[rem.x][rem.y] == '1') { return true; } arr[rem.x][rem.y] = '1'; // add for (int d = 0; d < 4; d++) { int ni = rem.x + xdir[d]; int nj = rem.y + ydir[d]; if (ni == -1) { ni += arr.length; } if (nj == -1) { nj += arr[0].length; } if (ni == arr.length) { ni = 0; } if (nj == arr[0].length) { nj = 0; } if (arr[ni][nj] == '.') { qu.add(new Pair(ni, nj)); } } } return false; }}