Gerald's blog

CROC-MBTU 2012, Elimination Round
By Gerald, 12 years ago, translation, In English

Good day!

Elimination round of the CROC Collegiate Programming Competition for the MSTU Bauman students is going to be here soon. The official championship participants will take part in the competition, all others will be out of the competition in the table of results.

The contest is held by the well-known rules ACM-ICPC. Competition duration is 2:00 hours. Supported programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, and D.

This Round will be the rated for the Div-2 participants, regardless of whether one is the competition championship party or not. For Div-1 participants this round is unrated.

Please note that the official participants of the competition are not need to register for this competition they will be registered automatically (with advance registration at website).

Good luck to everyone!

UPD. Competition is completed, thank you very much for your participation! I hope that the problems with the queue is not much to spoil your impression of the contest. The results of elimination round for official participants will be announced tomorrow. Rating will be update soon. Additional information for those who are involved in this competition for the first time:

I/O is standard. A simple programs that solve the A+B problem are shown below.

Pascal / Delphi:

    var
      a, b: longint;
    begin'
      read(a, b);
      writeln(a + b);
    end.

Java:

    import java.util.*;
    import java.io.*;

    public class Solution 
    {
      public static void main (String[] argv) throws Exception
      {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(a + b);
      }
    }

С++:

    #include <iostream>

    using namespace std;

    int main(){
        int a, b;
        cin >> a >> b;
        cout << a + b << endl;    
        return 0;
    }
  • Vote: I like it
  • +88
  • Vote: I do not like it

Comments Comments (73)
| Write comment?
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Questions will be available on English, right?

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

how many problems exist?

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

rating will be updated based on div 2 users results or based on every users results?

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Problems will be sorted according to difficulties?

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

    Usually, in contests with ACM-ICPC rules problems don't sorted according to difficulties.

    → Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

why contest isn't rated for Div 1 ? will it be a bit easier ?

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I had registered in this contest, why i still see Register now ?

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

    I have this problem too, Can you solve it? Also there are different time to contest beginning, what does it mean?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      One countdown is for contest start, other — for registation.

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

        Will Registration continue till the contest's finish?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          Yep. It's because of ICPC rules without hacks therefore no room division needed.

          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It's quite confusing, I thought the contest would be starting in around 3 hours, but it's starting in less than 1 hour! (~45 minutes)

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

How many problems exist? And how long does contest take ? Thanks

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

About 200 new participants , excluding the official contestants . I hope people have not made multiple accounts like last time

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In queue 4ever...

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

    No more than 10 minutes. About 8-9 minutes mostly. We are sorry about the queue, it is the result of ACM-ICPC mode + very easy tasks for many participants. We will make conclusions and prevent this next time. Sorry again about 9 minutes queue.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Happy that contest is held on CF , upset that CF has a bit weak server. :|

    → Reply
»
12 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Its frustrating to see submission in queue for so long!! Hope admins will "Unrate" this contest. And please run cf in safe mode during contests.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    unrate because your result is unsatisfactory? conditions were the same for all of the participants, am I right?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You can disagree but it is rated just among div2 and my rating will surely increase today, so it is not unsatisfactory to me.

      → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

just fixed

→ Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I like this exam . You?

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Amazing system testing in last.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Nice problems! Any tips for C?

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

    IN EDIT

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

    just count it from behind.. if n=7 then count how much we take coin from - 3 6 7 (we must make chest-6 and chest-7 empty) - 2 4 5 (we must make chest-4 and chest-5 empty) - 1 2 3 (we must make chest-2 and chest-3 empty)

    then add the coin left in chest-1

    → Reply
»
12 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Nice problem set.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Agree, i think many other people will agree too.

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

      4 out of 8 problems were quite easy. But it's not bad, considering that it was just a qualification round.

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How long time take the Rating's Upgrade?

→ Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I like these kind of contests :-)

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

in problems F, i wonder whether "the last n seconds" means the last N seconds from the last record, or the last N seconds from any other records?

→ Reply
»
12 years ago, # |
  Vote: I like it -17 Vote: I do not like it

it was awful! wrong testcases .. long time of judging ...

→ Reply
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Wrong Wrong Wrong! Problem D input 3 -1 3 5 3 -1 4 5 4 -1 according to accepted solution like: http://codeforces.me/contest/245/submission/2591027 http://codeforces.me/contest/245/submission/2590877 out put 7 7 5 and that's WRONG if you need to reconstruct array b[][] from accepted out put it will be -1 7(7&7) 5(7&5) -1 7 5 7(7&7) -1 5(7&5) = 7 -1 5 5(7&5) 5(7&5) -1 5 5 -1 so, i think it's wrong, is it?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    It's not. Your input is wrong, since it is impossible to generate it in the way, described in statement.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    and solutions which accepted input 3 -1 1000000000 1 1000000000 -1 1 1 1 -1 out put 1000000001 1000000001 1 and problem (D) said (0 ≤ ai ≤ 109) CONTRADICTION! how to accept it?

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

      "It is guaranteed that there is sequence a that satisfies the problem conditions. If there are multiple such sequences, you are allowed to print any of them."

      So your input is wrong, because there is no answer for test case.

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

Will there be any official editorials ?? If not , please somebody take the trouble of writing it (and in English too) because I liked the problem set very much and would like to know their solutions

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

Can anyone explain the solution to problem H? I'm a big newbie (you can check by my rating ;p). It's just a simple DP O(n^2)?

thanks!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes. dp[i][j] = number of palindromes in the [i,j] substring.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    First you check this:

    isp[i][j] = "is the substring [i,j] palindrome?" After that you can try this simple DP:

    dp[i][j] = number of palindromes in the [i,j] substring.

    So it's easy to see that dp[i][j] is equal to dp[i+1][j] + dp[i][j-1] — dp[i+1][j-1] + isp[i][j].

    The intersection between [i,j-1] and [i+1,j] is equal to [i+1,j-1], so "dp[i+1][j] + dp[i][j-1]" calculates dp[i+1,j-1] twice and you've to subtract this one more time to maintain the correct result. Also, you've to add 1 in the solution if the substring [i,j] is palindrome.

    A lot of contestants solved this problem by using Manacher Algorithm + DP, but it's only a matter of time complexity.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot, nice explanation!

      At first I though that I would have to use Manacher, since I haven't study this algorithm yet, I just gave up. Later I saw others contestants solution and I saw this DP, that's why I asked.

      Thank you very much!

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, but Manacher give us the length of the longest palindrome centered at Ti. But, between both solutions there isn't a big difference in time complexity.

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

      how do you check isp[i][j] efficiently

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        isp[i][i] = 1, isp[i][j] = isp[i+1][j-1] && str[i] == str[j].

        It means, if the substring [i+1,j-1] is a palindrome one and str[i] is equal to str[j], so [i,j] is a palindrome substring.

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

      I tried solve with manacher however not work, someone could tell me that I have bad

      http://www.codeforces.com/contest/245/submission/2595260

      thx

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

      I get this solution only 5 minutes after understand this problem Anyway, one karma for you :D

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

I think that in this round there was a discrimination to some contestants. More precisely, I think that time that one was waiting in queue was calculated with the rating the contestants have.How is possible that I waited around 10 mins for every submission and some people had already solved 2 problems in the first 5 minutes. This is not a good thing, and I hope that I am wrong, because if it is true, it is really unethical.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Queue was formed based on submission times. Those that solved first two problems really fast were in the beginning of the queue.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +19 Vote: I do not like it

    It is obvious thing.. The queue was only formed becuase there were many submissions which the judge could not handle all at once. Obviously during the first 5 minutes there were very few people who made submissions and so received quick judgements. And no points for guessing that these were high rated coders.

    I hope you had done a lot of research before posting this , becuase this is a algorithmic platform , judge here is not a rascist and decisions are not taken here based on colors .**Colors only affect when you get upvotes and downvotes in the community** :P

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain the solution for problem G?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The idea is similar to the last CF problem D (div 2). There are N guys (N is at most 2*M) and M pair of friends. You just do a brute force to check for all x, how many y has the most common friends (to check common friends you need a linear algorithm, like sorting everyones friends and doing a two pointers thing, or even easier calling set_intersection ;) ). It seems to be cubic, but its not, for one guy you do at most N*A + M operations (A is the number of his friends), the total complexity will be N*A + M + N*B + M + N*C + M + ... = N*(A+B+C..) + N*M = N*M + N*M = O(M^2). Here is my implementation if it is not clear yet: http://codeforces.me/contest/245/submission/2602015

    I hope it helps :)

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

      i used another method, for each one, i get a set which has all the friend of him, so each pair in this set pair(a,b) should add one point. than i got a matrix, a[i][j] means how many friends, i and j have in common. this methods looks like n^2, but my solution time out at test 8, not sure why, anyone has any ideals? maybe stl just very slow....http://codeforces.me/contest/245/submission/2607465

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

        Try to replace strings by numbers, so you will not need map to hold the friends list.

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

          yeah, should avoid using stl in the first place :), thanks

          → Reply