Sereja's blog

Codeforces Round #131
By Sereja, 12 years ago, translation, In English

Hello everybody!

Welcome all to Codeforces Round #131, which will be held on Monday, 30th of July at 19:30 MSK. I am (Sergey Nagin) an author of the problems. This will be my First Codeforces round and I hope it won't be the last one :).

I would like to thank Mike Mirzayanov(MikeMirzayanov) who made this contest possible, Roman Furko(Furko) and Gerald Agapov(Gerald) for helping to prepare this round and Maria Belova(Delinur) for the translation of problem statements into English. I hope that problems will be interesting for you.

Good luck!

Problems’ point values in Division 1 are 1000-1000-1500-2000-2500. Problems’ point values in Division 2 are 500-1000-2000-2000-2500.

I strongly recommend you to read ALL the problems.

The contest is over! Congratulations' to winners!

First division:
1 place: Egor
2 place: Petr
3 place: tourist
Second division:
1 place: antimatter
2 place: c175353
3 place: takaramono

I hope, that problems were interesting for you.

You can view tutorial.

Some personal information. This year I finished school and I will go to university. I study programming during almost five years. In addition to computer science, I like sports: powerlifting, arm wrestling and swimming.

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

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

so, we are gonna have some sports flavored problems!!

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

will the scoring be as usually or dynamic ?

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

    Dynamic scoring is nearer and nearer to become 'usual & default' :)

    UPD: not this time :D

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

      Well usually when the contest only for DIV 2, it's using dynamic, and for both Division they usually use normal scorring IMO

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

      I disagree..If you browse thorough the contests after Round #113(after dynamic scoring was introduced) you will find that apart from rounds #115 and #126 and all rounds from the trio NALP- Gerald-HolkinPV (which have dynamic scoring systems) ,,the scoring system has been traditional in other rounds. So I think they leave it on the authors to decide ..

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

Good Luck And Have Fun! :)

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

hacked by hackers

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

    What said bad(he has -4)?

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

      Don't try to understand negative votes on codeforces.

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

        if comments have negative votes it is bad but lashabuxo-s comment i think is not bad.

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

          If comment have negative votes — then somebody thinks it is bad.

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

How to run my program at local machine? Above is quickly enough?

g++ xx -o exe

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

    g++ code.cpp -O2 -o exe

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

    g++ name.cpp && a.exe <in.txt ( in windows )

    g++ name.cpp && ./a.out <in ( in linux )

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

Very interesting B question in Div-2..It made me so involved that I did'nt have the time to read C,D,E..But I am happy I managed to pass th pretest finally after 11 WA..

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

    Some test example from Hacker.

    Input:

    3

    0 0 0

    Output:

    000

    Answer:

    0

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

how can This Submission Pass the preetest but got compile error while Systest ?

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

    Compilation Error на 10-м тесте facepalm

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

    How is that even possible?

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

Great contest, thanks to all of you.

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

It seems java needs more space than C++. In div1-C I initialize a 3-D array and get MLE.

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

    I did not look at your code but it may be the case of how you declared the array.

    Arrays are objects in Java, so a[1000][1000][2] creates one million objects and a[2][1000][1000] creates only 2000. There is an overhead for each object.

    If space is an issue, use a 1D array instead.

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

In the contest, I got many wrong answer on pretest 1 of problem D,.. After the contest, I found out the mistake, only one mistake: 10.0 => 1.0. And I got AC after fixing it... So sad!! :(

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

For div2 B, can someone confirm test 13 is the same with test 14, i.e. the input is ten thousand 0s? My solution passed 13 but failed on 14, quite weird.

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

    your solution didn't pass test 13. you got wrong answer on test 13.

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

      The solution I meant is below, not the one during the contest.

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

        test 13 and 14 are not identical. I suppose there is a difference between them and since we can't see the whole test case we can't see the difference.

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

    The wrong solution is here. Please give me some hints.

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

      Input can be like this
      (100000) zero for test 13
      (99999) zero + 1 for test 14
      both of them have same answer but, because is too long, it will cut.

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

      input 5 0 0 0 0 5 what answer?

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

      Thanks you guys who replied. I find the bug and get it fixed. This is the correct solution. It turns out case 13 and 14 are indeed different.

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

very nice problem set!

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

The problemsets are nice, thank you, Sereja.

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

Problem B was very confusing.. as in the problem statement, it was written: Each digit is allowed to occur in the number the same number of times it occurs in the set.

Then how the ans for second test case is: 5554443330 since in input set 4 is occurring 4 times but in output integer it is occurring 3 times only.

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

    It is permitted to use not all digits from the set

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

    They said: " It is permitted to use not all digits from the set"

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

      I took it as.. if i am not taking any digit then i am not supposed to use that digit in the output at all. Means that digit's count would be made 0. I tried other way also, but because of a very silly mistake my solution got hacked.

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

    May be you missed this -> '**It is permitted to use not all digits from the set**'

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

I Think It Would be better to increase Contest Time for some contests like this To let People have more Fun !

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

The comment is hidden because of too negative feedback, click here to view it

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

    It's interesting to see how many downvotes that comment will get, because it'll mean that some people actually care about comments that downvoted a lot.

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

    One of the advantages of being Petr is that you can make such troll-jokes without throwing your reputation towards S = {x : x < 0} where x belongs to R.

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

    When I try to click "here" the page scrolls to the top and the comment doesn't show up.

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

      I don't get how you don't get it. And I'm the "blue" one here.

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

Does the intended solution for div1 E use hashes? I saw only hash solutions and wonder if they can be hacked using ideas from recent anti-hash articles.

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

    I think that this is the reason why people submited this problem in last minutes of the competition — not to be hacked...

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

    I'm quite sure it can be solved with something similar to KMP.

    Assume we can, after preprocessing, quickly compute functions prev(k, i) and next(k, i) for a permutation P, which give the first element j in [i, k — 1] preceding / succeeding k in P.

    Let suf[k] be the minimum j > 1 such that the part of A composed of elements [j, k] is (EDIT) the same permutation as the part of A composed of elements [1, k — j + 1]. We can compute suf[] using a linear number of calls to prev() and next() on A.

    Later we can use suf[] like a KMP table to compute all shifts that match with a linear number of calls to prev() and next() on A and B. :)

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

How can I know number of 1's in testcase number 12 in div2 problem B ?

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

    There is no way to do this.

    But... You can count them, and guess counter by binary search. (For example, if cnt < 4000 then cause TLE, otherwise get WA)

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

      I found a better way compared to this. print out number of 1's for this particular case . number of 1's are 49898 . :D

      anyway thanks for your help.

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

One Does Not Simply
Update the rating quickly

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

i am new on codeforces.com and how add friend???

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

tourist lost his Codeforces Red Target :(

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

When will the editorials be available for this contest's problemset? Thanks in advance

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

Wrong answer on test 65 on problem B, div 2. Don't you know what it is?

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

    div 2,problem B: your submissions status and test 65:

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

when the Problem's Analysis will be placed ?

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

Although I liked the problems, I think problem C was a bit of a fiasco. On one hand the exact same problem has been given before in TopCoder, SPOJ, one Bulgarian competition (okay, no way to know that) and God knows where else. Thus many people had the chance to solve it in several minutes (I for one needed 9 minutes, and other people even less). Anyway, this happens (I know from bitter experience).

I also was happy to see the negative numbers (which means negative results are possible). This is another TopCoder trick I've felt for before — if you use memoization and you initialize your array with -1 (which is valid number in this case) you have a correct, but possibly too slow solution. For those of you who don't know it — if the answer to the problem is -1, then some of the states will be calculated over and over again and it can turn really slow. So I was looking for such solutions in my room, however most were using standard iterative dp (which is okay with that) and didn't have the chance to challenge anyone.

However, such a test was not present in the system tests, so some (possibly plenty) of wrong solutions passed.

The test is rather simple to create:

int n = 300;
fprintf(stdout, "%d\n", n);
for (int i = 0; i < n; i++)
    for (int c = 0; c < n; c++)
        fprintf(stdout, "%d%c", ((i + c == 580) ? -1 : 0), c + 1 == n ? '\n' : ' ');
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But, is there a way to use a smaller state (not 598x300x300) so that you don't get memory limit exceeded? Because if that can't be done then I guess that could justify the absence of such cases

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

      Yes, sure. See my solution, it uses twice smaller state (if I initialize my dyn[][][] array with -INF instead of using additional array).

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

When I click the tutorial link, I can see a tutorial, but not in English. Why? The English tutorial has been released, I think.

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

Hello! I don't know where to post my problem so i'll post it here. I apologize if posting this here is wrong.

Well i have tried the problem Numbers(D div2, B div1) and i finally solved it. The source code is here http://codeforces.com/contest/214/submission/1974583

I get WA on test 10 (100 0 0 0 0 0 0 0 0 0 0). The strange thing is that when i run the code it prints the right answer on my computer. Here when i submit it, the answer on the same test is different and i don't get it why it does that.

Please help me to see what is wrong :(

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

    In your code, len can be 0, so in Comb[len - 1][j] index goes -1 and so you get weird numbers from uninitialized memory, instead of expected 0 value.

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

      Thank you very much :) I finally got AC. I guess i missed that -1 index.

      → Reply