Edvard's blog

Codeforces Beta Round #98 (Div. 2)
By Edvard, 13 years ago, translation, In English

Hi everyone!!!

It remains less than 10 hours before Codeforces Beta Round #98 (Div. 2). This round was prepared for you by me, proposed the ideas of the problems. Traditionally, RAD made sure that there is no bugs and that the statements are normal, and Delinur translated the statements into English. Thanks to them!

If you decide to participate in the round you have to help the boy Polycarpus and his classmate Innocentius in all the difficulties they face. The more you help them, the higher you will be placed in the standing.

I hope the problems will be interesting not only for Div. 2 participants, but the participants rated higher than 1699.

I will continue the story about myself (beginning of story in the previous blog entry). Besides programming I love sports. Within a few years before I started writing code, I was seriously involved in rowing. And before that I was going in for almost all sports :-): karate, soccer, hockey and so much more interesting. Now I love (especially at the training camp) to play volleyball and table tennis. I decided to prepare this round despite the fact that during the past two weeks, much has changed inside Codeforces and I took part in this.

Following the fashion trends I have changed my avatar.

Good luck for all on the round!

UPD:

Contest is finished, results are final, ratings are updated.

Top 10 (Div. 2)

3. stx2

Congratulations to winners!!!

  • Vote: I like it
  • +141
  • Vote: I do not like it

Comments Comments (60)
| Write comment?
»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Luckly,there will be not class for me in the afternoon,so I can take in the contest;thanks for your hard work!
→ Reply
»
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Thanks for your work! I think this round will be fun.
→ Reply
»
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I was going to watch Mission Impossible 4 !!! I had to change my plans because of the contest . :P 
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
after contest finishes check out organofjohannbach's solution to problem C. This guy must be real pro
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Liked the problem set, but I cant understand how to prove binsearch in E, can anyone help?


    Binary search is incorrect, can anyone explain right sol?

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      It is not correct as function is not monotonic. baaab has good string of length 5, but not of length 4
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        then my E failes, thanks
        → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Binsearch is incorrect solution for E.
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Well my solution for E works like this,
      1. Convert the string into an integer array A. convert a vowel to -1 and a consonant to +2.
      2. Calculate a sum array, where sum[i] is the summation of A[0] to A[i].
      3. Now for each i, we need to find the minimum index j<=i, such that sum[j]<=sum[i]. For this I used a binary indexed tree. So for i we found the longest good substring which starts at j.
      4. Thus longest good substring can be easily calculated in O(nlogn).
      5. The number of times can be easily calculated in O(n).
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Constant time lookup is also possible (instead of binary tree), for an O(n) algorithm.
        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I don't understand how do you find the minimum index j
        → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i also tried to use binary search but i found out mistake soon...
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Thanks to admins,codeforces was really fast today. I have participated in 36 contests but never seen cf working so fast,its great :).
→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

my C is Denial of judgement

wtf?

It's ok now, sorry
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
a lot of C recv " Denial of judgement"
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice problem set!
But I have a little question:
In a char tab[100], is the '\0' counted on the 100 ?
Because I have tried to hack a code who had a char tab[100] for the problem A, with a string "C....C" (containing 100 'C'), and it was unsuccessful...
Thanks you in advance
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    It is, but in C++ there are no range check, so trying to hack for being out of bounds for array/vector are very risky (expecially with off be one errors)
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Ok, I did think about this possibility, but I wasn't sure.
      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    '\0' would never be counted in this 100 chars since it is just implementation detail of one of variants of holding string in one of programming languages.

    Anyway char tab[100] would not necessarily yield error with 100 Cs - it is possible that 101-th '\0' was placed in spare memory after the end of the array without error...
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I also mis-hacked one solution, in which he tried to access indexes of a vector which did not exist.
      To make sure that my hack is correct , I tested it on my computer, and it caused Seg. Fault.
      And unluckily enough, got -50 During hack. :(
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It is very unstable thing. For examle suppose:

        char a[100];
        char b = 5;

        int func() {
            return;
        }

        Suppose, user made writing into a[100] - what then?

        If code is not optimized and data are not aligned, he will write actually into b.
        If code is aligned at 4 bytes border, he will writing between end of a and beginning of b - no problem at all.
        If code is optimized, b may become register variable and disappear, if code is not aligned, he will erase beginning of "return" instruction (this may lead to funny bugs).

        However this depends on actual placement of data and code, architecture etc.
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Okay, will keep that in mind.
          Thank You.
          → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
a lot of people had solution in o(n*n) but i couldn't hack because you cant send test with more than 20k memory ...
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    You can send a generator
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      When I try to upload the input, why did it not say: "Your Input is more than 20kb limit. " in RED BOLD FONT.
      When I click on Hack, it did not do anything .
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You should upload a generator, not an input
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I know now. But I want to ask , why does the interface not show that "What you just uploaded is so much large in size that we cannot handle, plz use generators" in RED BIG FONT instead of just blinking once and keeping quite.
          → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, I don't like this too... I have seen a code who use a int tab[10000] for the problem C, and I didn't can hack his problem because my input was too large....
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You can't hack not because input was large, but because you never tried sending generators, though it was discussed a lot of times.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        What is a generator? A executable who send input on stdout?
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Exactly... Read some comments above - here are examples
          → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      The reason you need generator is for large inputs,input file becomes to large,may be some megabytes and uploading them will create severe pressure on server. If you want to know how to write generators,here is my generator in div2C:
      int x=1;
          cout<<100000<<endl;
          for(int i=1;i<=100000;i++)
          {
              if(x+1>1000000000) break;
              printf("%d %d\n",x,x+1);
              x+=2;
          }
      I have hacked some n*n solutions with this today.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        if i knew that i would have more than 5 hacks :@:@:@
        → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hey guys. I competed in codeforces for the first time today. would anyone mind telling me why my submission for problem B gets a run time error? thanks!
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Look at the constraints.  You can get values bigger than N for t-1 in this line
    V[t-1] = true;
    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Y the system test didnt accept my problem A submission?
→ Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Very nice algorithmic problems! It gave me a lot of pleasure to solve them! Thanks! 
→ Reply
»
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
I like this contest.I'm happy and learn a lot after doing this contest.Thanks the author!
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could anyone please tell me why my solution got WRONG_ANSWER on this test?
Test: #22, time: 90 ms., memory: 42128 KB, exit code: 0, checker exit code: 2, verdict: WRONG_ANSWER
Input
WdYlPYGSNSGYPlYdWpIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhzVWOelUjtrMyIpZassaZBSohcqchoSBZKgKZlhMOXMoMXOMZGZvvRkqSOmHWZxSxZWHmOSrkRvvWPW
10
Output
3
WdYlPYGSNSGYPlYdW+pIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhiVWOelUjtrMyIp+ZassaZ+BSohcqchoSB+ZKgKZ+l+h+MOXMoMXOM+ZGZ+vvRkqSOmHWZxSxZWHmOSqkRvv+WPW
Answer
3
WdYlPYGSNSGYPlYdW+pIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhiVWOelUjtrMyIp+ZassaZ+BSohcqchoSB+ZKgKZ+ll+MOXMoMXOM+ZGZ+vvRkqSOmHWZxSxZWHmOSqkRvv+WPW
Checker Log
wrong output format Expected string with length not greater than 139, but string length is 140.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because you split the string into 11 palindroms, not 10.
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You have split string into 11 palindromes, while k = 10.
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    А объясните плиз, почему у меня рейтинг понизился? хотя если на прошлом контесте я 1069\2031 место с 1 задачей , а на этом  650\1324 с 2мя. потому что участников меньше ?
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Да, в процентном соотношении у вас примерно одинаковое место на обоих раундах.
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      А ещё количество зарегистрировавшихся не есть количество участников.
      → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am new to code forces. can u tell me how to view others solution??
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    lock your solution,then you can see others in your room.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      how to lock the solution??
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        At problems page a lock icon will appear if your code pass pretests,click that icon.
        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If the round is already over, then just double-click on a result in the total results table.
    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My DP solution to problem E exceeds time limit, with O(n^2) complexity (n being length of the string). 

What is the correct solution supposed to look like?
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    (c) Egor

    Let B[i] "Balance" of the position i - doubled amount of consostants minus amount of vowels in i-th prefix. Then the longest "good" substring, which begins at i'th position ends at the farest position j, such that B[j] >= B[i]. Count for each balance the farest poisition, where we can achieve it, then for each balance count the farest position, where we can achive equal or greater than it. Finally, iterate threw a string and for each position count the longest "good" string, which ends here.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    O(n^2) obviously will exceed time limit.
    Expected solution was O(nlogn) .
    One of the solution I saw, used Binary search . (Don't ask on what ;-) )
    Other used some kind of tree. Binary Indexed one. (I was never able to fully remember this thing. :( )
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My solution. Of cource this code may looks better but I'm little stuped and can't realize short and obvious solution.
    First idea. Let's substitute vovels by -1, consonants by +2, and calculate the sum on a prefix. 
    Second idea. Let's find for any position the most length of correct string which started at this position. Of cource, it's the most distant element with a larger value of sum on the prefix.
    Third idea. Let's sort our array of pair <sum on prefix, position> (with element (0,0) - null element), and will support a pointer of last not used point in our array.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      we need to keep track of the first position in the string that has a cumulative sum less than the or equal to any given cumulative sum the first time it comes up. 

      Hmm, for non-negative sums, the first position is always zero. 

      Haha, the joke is on me:  I only needed to keep track of the first position of negative cumulative sums!  the array only needs to be 200,000 elements long; the length for any non-negative cumulative sum after N characters is always N.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I said: for any position let's find the string with the most length which started at this position. What is it hard to understand? I can explain it in another variants, but I can't understand what's the trouble.


        UPD: I'm understand

        → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
after this contest Social Buttons disappered! Did admin forget to turn on all the stuff?
→ Reply
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Really nice contest......first three problems were really easy.....i should have solved them......got AC in only one.....misread one....got tle in other......it was a nice learning experience......

thank you for the contest... :)

waiting for the next contest and expecting a better performance next time..
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Оо, "Все задачи" - это очень удобно! Спасибо :)
    → Reply