RAD's blog

Codeforces Beta Round #46 (Div. 2, Codeforces format)
By RAD, 13 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

Comments Comments (45)
| Write comment?
13 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?
→ Reply
13 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?
→ Reply
  • 13 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
    → Reply
13 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.


→ Reply
  • 13 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.
    → Reply
    • 13 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.

      → Reply
  • 13 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
    → Reply
  • 13 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.
    → Reply
    • 13 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.
      → Reply
13 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?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used a DP with states (position, color of position-1)
    → Reply
  • 13 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
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Is it unique?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        what??
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          The way to change given string into targer one.
          → Reply
          • 13 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

            → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
there seems no case for the answer -1
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is answer for C unique?
→ Reply
13 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
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is  test21 for Problem B, i am getting WA?
→ Reply
  • 13 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.

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what is test case 8 for problem D ??
→ Reply
  • 13 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!
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i didnt get it , where to see the test case?
→ Reply
  • 13 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.
    → Reply
  • 13 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)

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      write your own pow then try....
      → Reply
      • 13 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. :(

        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone give a glimpse of the solution for problem E?
→ Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Why the ratings aren't updated???
→ Reply
13 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?
→ Reply
  • 13 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
    → Reply
    • 13 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. . .
      → Reply
      • 13 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.
        → Reply
        • 13 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. . .
          → Reply
  • 13 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
    → Reply
13 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.
→ Reply
  • 13 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.
    → Reply