By RAD, 9 years ago, translation, ,

Good evening!

Soon many of you will have your examinations, and someone even have it now. I wish you excellent marks and many easy exams!

Thanks to Nickolay Kuznetsov, Gerald Agapov and Ivan Fefer for their help in preparation of the round.

Good luck!

Artem Rakhov and Codeforces team

UPD:

Ratings will be updated later

• +22

 9 years ago, # |   +2 Good Problems, but i have found that sentences in the question were not clear.eg.Problem C He thinks that it does "not do to arrange" the book. eg Problem B It was not written whether the numbers are Integer?
•  9 years ago, # ^ |   0 I am totally agree with you.
 9 years ago, # |   0 I didn't get the meaning of Problem C.What problem does it want us to solve?
•  9 years ago, # ^ |   +12 it just asked to minimize   number of toms that is relatively prime to its position
 9 years ago, # |   +2 Aha, a good contest with nice problems!Problem C is not so easy to understand, but really interesting.The answer looks very easy,but hard to get.Problem D confused me.I can't pass it till now. But also a good problem.Problem E is really nice, I got a O(N4) dp after long thinking.
•  9 years ago, # ^ |   0 I wonder whether problem E can be solved using BFS....if we have some string s1 we try to get shorter s2 by reverse operation described in problem. To avoid repetition we use memoization.
•  9 years ago, # ^ |   0 My solution is dp instead of BFS.I don't think BFS can work.
•  9 years ago, # ^ |   +1 can  u share me ur code for prob E plz... i don hav any idea abt this
•  9 years ago, # ^ |   0 ma mail id: venkat.june11@gmail.com
•  9 years ago, # ^ |   0 Ok.I send you the code.By the way, you can look the code of anyone here:
•  9 years ago, # ^ |   +1 ya i just found this feature! i'm new to code forces
•  9 years ago, # ^ |   0 Hey can you explain how u approached the problem E. I used kinda brute-force but got TLE on test case 8.I dont need the code; just the approach would be quite helpful.
•  9 years ago, # ^ |   0 For example:ababaaba2c->bac->ccThe answer is :ac => [a][baba][a][ba]So, we can use dp[i][j]: the shortest common ancestor of a[1]...a[i] and b[1]...b[j].dp["a"]["a"] = 1dp["ababa"]["aba"] = dp["a"]["a"] + 1If we know, "baba" & "ba" can generate by the same letter "c" , we can obtain the answer.To get that, we also use a dp.bool dp2[string][char]: can a string generate by the letter char.But it cost O(N5) in time.So we can compress it into an int.
•  9 years ago, # ^ |   0 Thanx a lot..
 9 years ago, # |   +1 I used greedy algorithm for D and got AC (?!). How did you solve it?
•  9 years ago, # ^ |   0 I used a DP with states (position, color of position-1)
•  9 years ago, # ^ |   0 We have only two possible anwers in the end:. one which starts with black and another starts with white. (sort of chess coloring)So we calculate the difference between our target string and our given string. (we choose minimal) it's easy to see there always exist way of reduction of our string to the target function
•  9 years ago, # ^ |   0 I did the same. It seemed the easiest of all. Actually saw this problem when 10-12 minutes were remaining. And solved instantly....
•  9 years ago, # ^ |   0 Is it unique?
•  9 years ago, # ^ |   0 what??
•  9 years ago, # ^ |   0 The way to change given string into targer one.
•  9 years ago, # ^ |   0 no it's noteasy way to see it:11101target string:10101we could have chosen first and second as well as second and third
 9 years ago, # |   +2 there seems no case for the answer -1
•  9 years ago, # ^ |   0 Yeah you are right, i did not use -1 in my program and got AC.
 9 years ago, # |   0 Is answer for C unique?
•  9 years ago, # ^ |   0 No, for example:n, 1, 2, ... , n-12, 3, ... , n-1, n, 1
•  9 years ago, # ^ |   0 Yeah!Thanks.
 9 years ago, # |   0 What a pity!I have thought of the easy solution,but I can't figure out when the answer will be -1.So I want to judge it by DFS,but if failed
 9 years ago, # |   0 What is  test21 for Problem B, i am getting WA?
•  9 years ago, # ^ |   0 1 999I also got it wrong, finally found that pow function was not giving desired answer.
 9 years ago, # |   0 what is test case 8 for problem D ??
•  9 years ago, # ^ |   0 You can see the test cases now if you look at your uploaded code!
•  9 years ago, # ^ |   0 Ok, Thanks for the informationi think this got introduced today...Thanks a lot, Admin
 9 years ago, # |   0 i didnt get it , where to see the test case?
•  9 years ago, # ^ |   0 click on your submitted file (its link is available on the left side).In the file look below your program...to see the test cases where ur program failed/passed....
•  9 years ago, # ^ |   0 Go to "My submissions" and click the id of your submission (in the "#" column, the first one). You can do it with others solved submissions too.
•  9 years ago, # ^ |   0 For problem B-------------------My failed test case---- Test: #21, time: 10 ms., memory: 1316 KB, exit code: 0, checker exit code: 0, verdict: WRONG_ANSWER Input 1 999 Output 3 Answer 4 Checker Log wrong answer 1st numbers differ - expected: '4', found: '3'------------------------------When i run the program on my system i get Anser as 4 not 3here is my program (i have removed the header files)
•  9 years ago, # ^ |   0 write your own pow then try....
•  9 years ago, # ^ |   0 And your program does outout 3 on my system.This erratic behavior of pow caused me WA. :(
•  9 years ago, # ^ |   0 Thanks, ManishI got Accepted by writing my own pow....Thanks again
 9 years ago, # |   0 Can anyone give a glimpse of the solution for problem E?
•  9 years ago, # ^ |   0 я бы тоже непрочь узнать логику данной задачи
 9 years ago, # |   0 Problem B get me depressed.as there's an incorrect case in the question when adding 78 and 87 in base 9.it was added in decimal notation and then a conversion is done from decimal to base 9 so 78+87=165 in base 9 = 203)9but in the same question 78+87 are added in hex as inputs are in hex and the result in hexlater the question is edited and corrected to (78+87)=176) in base 9 But after losing a lot of time and one incorrect submission :D :D Anyway i enjoyed today's round and ISA it'll be better in Monday's round.Thanks a lot.
 9 years ago, # |   +4 Why the ratings aren't updated???
 9 years ago, # |   0 I think there is a trick set by problem setter in D. Problem set says,If Petya cannot win with such an initial coloring, print -1.But actually there can not be such input.for every input Petya will win. It took a lot of time in thinking before submission
 9 years ago, # |   +1 Can anyone tell me why this output is 3:101000101001output 2 Answer 31000101001->1010101001->1010101010 =>2?
•  9 years ago, # ^ |   0 It's because Petya can recolor two cells with one color only, you had recolored 01 -> 10 at a last step
•  9 years ago, # ^ |   0 well i don't use spesial algorithm for solve this problem. Just using simple logic but I'm hard to understand it. . . and me got accepted. . . what a miracle. . .
•  9 years ago, # ^ |   +1 There is actually a simple logic to do this question,Finally the strip has to be like 1010.... or 0101.....So basically you compare the input with both the two forms of the string and see the difference. Lets say the nth block doesnt match, then that means (n-1)th block has to be the same color as nth block and thus in one step you can paint it the right color.Eg,Input: 1101011compare this with 1010101... we know the second position doesnt match, that means we simply take the 1st and the 2nd blocks and paint them the right way.If two blocks don't match in a row that means they are of the opposite colors and you can't take them together and paint it... thus needing two steps... and similarly for 3 unmatching blocks you will take 3 steps etc. So basically you count the differences from both the types of final outputs and whichever one is smaller, you output that.
•  9 years ago, # ^ |   +1 aaaaa. . . that's what I mean. . . Actualy i'm not understand about BFS or another algorithm. . . Can you help me . . . I solve all problem with simple algorithm without know what algorithm i use to. . .
•  9 years ago, # ^ |   0 BFS and DFS are two different types of search methods for graphs.This link describes both the methods. Do not worry about the code snippets if you do not understand Java. Just understand the theory and you can have your own implementations.
•  9 years ago, # ^ |   +1 In the second step,10101010[01] -> 10101010[10]This cannot be done as [01] are not of the same color.You would have to do it in this order,1010101001 -> 1010101011 -> 1010101010
 9 years ago, # |   0 Thanks all.Does anyone use BFS for prob E.My BFS for E : from S1 we create all the shortest ancestor of S1 by BFS ,the same with S2, then we compare all the ancestor of S1 and S2(using binary search) to find the result.
•  9 years ago, # ^ |   0 I am not sure, but I think it would result in a more expensive algorithm. O(N^5) I believe.
 9 years ago, # |   0 I am waitting for the solutions of round 46 coming out.