MikeMirzayanov's blog

Codeforces Beta Round #7
By MikeMirzayanov, 15 years ago, translation, In English
The contest is rescheduled to start on 19:45.

Thank you all for participating in Codeforces Beta Round #7. I hope you enjoyed it. You may discuss the problems and system in comments. Please express your opinion, especially if you notice any inappropriate behavior. And as always, I will read with interest the suggestions for improvement.

From today on both-divisions contests ratings will be updated separately for each division. I. e. ratings will be calculated as if two contests (one per division) have taken place on the same problemset.

Also I would like to see someone who wants to write contest tutorial. This must be done in Russian and English languages. Of course you must solve the problem on either contest, or in the practice. If you have a desire to do it - write in comments. Your post will be published on the main page and later available on special link available from the contest page.

Many thanks to the contest problemssetters: RAD and e-maxx.

Good luck.

Ratings has been updated. Solutions are available for view.
Announcement of Codeforces Beta Round 7
  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can you please release the Test data?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    yeah specially 42 test case of problem B
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      your problems was with erase 0 or something like that.
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I believe this case had "erase 0" in it, where one might forget to output "ILLEGAL_ERASE_ARGUMENT".
      → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
erase 0
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there any way to see more than one page of Status?
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
How can i see the others sources in this contest?

→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    After the contest, u can enter the contest problem set, and click the tab which show the number of solvers of the problem, then u can see the sources.
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i think , i saw problem C in CodeChef.com and SGU ,
what's different between them ?

problem in SGU : http://acm.sgu.ru/problem.php?contest=0&problem=106
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why should there be any difference?

    This problem is quite standart application of linear Diophantine equations. :)
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can i see any data?
→ Reply
15 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I think this website would better if it own a forum.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It would be awesome to view source code on the standing page.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes. The best way would be after double click to see submission history and if you can get source code from there. Now you can see submissions only from one page of status, there is no good solution of problem E at the moment :(
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Sorry, I noticed that you can click people who solved the task on problems page.
      → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
sorry, I think this is not the place, nevertheless  I'm gonna ask it:

is there an available file ( or a way ) to download the problems and print them?
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
- If I want to see say Petr's  solution , anyway to see it ?
- I entered the practice contest, but am only able to see the solutions of recently submitted people , not all the ones who submitted.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can use a URL like this:
    http://codeforces.me/contest/7/status/E?order=BY_ARRIVED_ASC
    If Petr took part in the competition, he will 99% sure appear in this list ;)
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It seems that the functional Page Up/Page Down is not available yet.
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume $$$0$$$-based indexing. Let $$$dp_i$$$ denote the degree of the $$$i$$$-th prefix. The length of the prefix, $$$len = i + 1$$$. Firstly, $$$dp_0 = 1$$$, since a $$$1$$$-length string is a palindrome.

    Now, to compute $$$dp_i$$$, firstly check to see if $$$i$$$-th prefix is a palindrome or not. If it is not a palindrome $$$dp_i = 0$$$. Otherwise if the prefix is palindrome, its degree would be = (degree of the first half + 1). So, $$$dp_i = dp_{\lfloor\frac{i-1}{2}\rfloor} + 1$$$.

    To check whehter the prefix of length $$$len$$$ is a palindrome, you have to check whether the substring on the first $$$\lfloor{\frac{len}{2}}\rfloor$$$ characters is the same as the reverse of the substring on the last $$$\lfloor{\frac{len}{2}}\rfloor$$$ characters. To compare substrings, you can use string hashing. One ways is to build prefix hashes on the string and its reverse to obtain hash of any substring in a O(1) time as described in this blog.

    The answer is simply $$$\sum\limits_{i = 0}^{n-1} dp_i$$$.

    Code

    → Reply