RAD's blog

By RAD, 8 years ago, translation, In English,

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
 
 
 
 
  • Vote: I like it  
  • +22
  • Vote: I do not like it  

8 years ago, # |
  Vote: I like it +2 Vote: I do not like it
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?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I didn't get the meaning of Problem C.What problem does it want us to solve?
  • 8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    it just asked to minimize   number of toms that is relatively prime to its position
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it
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.


  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My solution is dp instead of BFS.
      I don't think BFS can work.

  • 8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    can  u share me ur code for prob E plz... i don hav any idea abt this
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      For example:
      ababa
      aba
      2
      c->ba
      c->cc
      The 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"] = 1
      dp["ababa"]["aba"] = dp["a"]["a"] + 1
      If 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.
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I used greedy algorithm for D and got AC (?!). How did you solve it?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used a DP with states (position, color of position-1)
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I did the same. It seemed the easiest of all. Actually saw this problem when 10-12 minutes were remaining. And solved instantly....
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Is it unique?
      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        what??
        • 8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          The way to change given string into targer one.
          • 8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            no it's not
            easy way to see it:
            11101
            target string:
            10101
            we could have chosen first and second as well as second and third

8 years ago, # |
  Vote: I like it +2 Vote: I do not like it
there seems no case for the answer -1
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yeah you are right, i did not use -1 in my program and got AC.
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is answer for C unique?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is  test21 for Problem B, i am getting WA?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 999

    I also got it wrong, finally found that pow function was not giving desired answer.

8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what is test case 8 for problem D ??
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can see the test cases now if you look at your uploaded code!
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Ok, Thanks for the information
      i think this got introduced today...

      Thanks a lot, Admin
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i didnt get it , where to see the test case?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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....
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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 3
    here is my program (i have removed the header files)

    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      write your own pow then try....
      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And your program does outout 3 on my system.

        This erratic behavior of pow caused me WA. :(

        • 8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks, Manish
          I got Accepted by writing my own pow....

          Thanks again
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone give a glimpse of the solution for problem E?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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)9
but in the same question 78+87 are added in hex as inputs are in hex and the result in hex

later 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.
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Why the ratings aren't updated???
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Can anyone tell me why this output is 3:
10
1000101001
output
2
Answer
3

1000101001->1010101001->1010101010 =>2?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It's because Petya can recolor two cells with one color only, you had recolored 01 -> 10 at a last step
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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. . .
      • 8 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        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: 1101011
        compare 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.
        • 8 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          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. . .
  • 8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    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
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I am not sure, but I think it would result in a more expensive algorithm. O(N^5) I believe.
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am waitting for the solutions of round 46 coming out.