School Individual Contest #2 (WCS 2010/11) - Codeforces Beta Round #43 (ACM-ICPC Rules)
By Nerevar, 14 years ago, translation, In English

Greetings to everybody.

I would like to invite you to take part in the next Codeforces competition, which will be held on 5th of December at 11:00 MSK. This competition will be a part of WCS olympiads (click here for details) and usual Codeforces round at the same time.

This competition, as all previous WCS contests, is sponsored by Yandex and ABBYY.

The official rules of the competition are ACM-ICPC rules. The duration of the competition is 3 hours.

Those who don't participate in selection to WCS will be displayed as "out of competition" in the result table. But everybody will get rating for this competition according to the merged result table.

This time the authors of the problems are Natalia Bondarenko and I. Thanks to Edvard Davtyan for his help in preparing the contest and to Maria Belova for translating problem statements.

Don't forget to register in order to take part in the competition. Good luck at the contest!

UPD: It will be available PDF versions of the statements during the round (you may print them):

UPD: The results of the contest. Congratulations to tourist, the winner of WCS contest, and to Petr, the winner of beta round #43.

UPD: Links to problem tutorials: A,C,F,G and B,D,E.

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

14 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it
The tasks were extremely nice. Thanks


After the end of contest please provide me with test 17 of problem D.

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    And 24, please :)
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Totally agree with you.
    Also want to know test #3 of E , that given +9 for me.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    А мне 21-й тест =) почему-то, сколько я не смотрел, решение на нем падало только у меня...
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      1000 12 16
100
1 16
1 52
1 55
2 3
2 2
2 1
1 97
1 53
1 29
2 9
1 2
1 91
2 8
2 12
1 35
1 92
1 62
2 15
2 11
2 7
1 14
2 16
1 93
1 67
1 97
1 33
1 98
1 23
1 60
1 66
1 8
1 87
2 32
1 62
1 45
2 25
2 23
1 29
2 29
2 38
1 34
1 71
1 24
2 31
1 21
1 77
1 67
2 26
1 6
2 30
2 24
2 46
1 77
2 28
1 13
2 21
2 35
1 6
1 100
1 10
1 56
1 37
2 62
1 52
1 70
1 95
1 14
2 64
1 91
1 68
1 72
2 41
1 76
1 29
1 86
2 43
1 82
2 45
2 60
2 65
1 58
1 44
2 27
1 1
1 57
1 70
1 87
1 16
1 1
1 58
1 85
1 58
1 22
1 13
1 81
1 57
2 58
1 22
2 93
1 41
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        Ой, ужас какой. А можно верный ответ к нему, а то вручную всё проверять очень долго?
        UPD. ответ можно не выкладывать. я взял верный код у тех, кто задачу сдал =)
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    and test #20:)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      50 3 1
30
1 9
2 1
1 6
1 5
1 8
1 1
2 6
1 7
2 3
2 8
1 7
2 4
2 5
2 11
1 2
2 15
1 6
1 3
2 17
1 9
1 3
2 18
1 3
2 23
2 21
1 8
1 2
2 27
1 8
2 29

      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    50 2 4
15
1 4
1 4
2 1
2 2
1 8
1 7
2 5
1 2
1 7
2 8
1 7
2 11
1 3
2 6
2 9

    → Reply
14 years ago, # |
  Vote: I like it +7 Vote: I do not like it
After all, I think it would be really nice if Codeforces publishes all test cases for all tasks after the contests.
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Why is negative result allowed in task E? It doesn't make sense. It's also sad that the solution using iostream doesn't pass the TL, because usually at CF it's OK to use iostream and some of us got used to it:)
But overall, the problems are very nice, thanks!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    I was also wondering whether a negative result is allowed or not. Had to ask this question through the system before submitting.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      According to the problem statement:

      "...Lara found a guidance note which said that to get hold of the treasures one has to choose some non-zero number of the first panels in each row of the table and put stones on all those panels to push them down."

      Given all values in the table are negative, you are forced to choose some negative values as answer.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        Yep, it's obvious. I got confused by "the maximum number of coins Lara can get" phrase though. The "number of coins" cannot be negative, assuming you treat coin as a physical object.

        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        "Lara found a guidance note which said that to get hold of the treasures one has to choose some non-zero number"

        What if I refuse to take the treasure? And how do you imagine getting a negative number of coins?
        → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it
It seems that problem G has wrong checker.
There is no way this solution could pass sys-tests (but it got AC):

    scanf("%d",&n);
    printf("YES\n");
  int s=0;
    for (int i=0;i<n;i++) {
                printf("%d %d\n",i,s);
                s+=i;
}
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Most likely they do not check a couple of (1, N).
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Not only that

      YES
      0 0
      -2 -1
      -2 -3
      0 -1

      YES
      0 0
      1 0
      1 2
      -1 1

      YES
      0 0
      1 0
      2 1
      3 2

      All of them passed the tests.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It seems true...

    For the test case n=4,I've got series of different answers for that among Accepted programs.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, there was a terrible bug in the checker. Now it is fixed, and solutions that passed after the end of the contest were rejudged. Solutions that got accepted during the contest won't be rejudged.

    I apologize for that, and also for the bug in the first sample in the problem A.

    Thank you for that comment.
    → Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Head was out when saw A's sample does not match but still some people managed to get AC. So waited.. then got the message to submit :( unfortunate lost 10min valuable time :(
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Could someone give me the test 6 for problem F?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Are you take into account that all doors in second night must be closed?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I did all checks, but I couldn't check if all doors are closed. How to do this?
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    3 3 3
    1 2
    2 3
    3 1
    a 1 1 1
    b 2 1 3
    c 3 1 2
    b 1 1 2
    c 2 1 3
    a 3 1 1
    → Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
We should change the upper bound of the graph for tourist :)
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I would like to know test number 14 of F. Can you please give it to me?

----edit: fixed I am sorry for being so stupid ! I really am ... trust me ;)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Where can results for Codeforces Beta Round #43 be found?
thanks
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can you please publish input for test 28 for problem E - Comb?
thanks
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Test 28 is a big random test with size 1000x2
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
how to solve problem E??
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    russian http://codeforces.me/blog/entry/916
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Denote F(i, j) as the maximum values that you can get from row 1 up to row i and at row i, you take ci = j. It is not hard to see that the following gives the correct value of F(i, j), for i > 1:

    F(i, j) = max{F(i-1, k)} + S(i, j)

    where k is ranged from 1 to j-1 if i is odd, j+1 to m otherwise.
    S(i, j) = sum of values at row i, from 1st column up to the jth column.
    If i = 1 then F(i, j) = S(i, j).
    Consider i > 2 as odd row. To calculate F(i, j) you don't need to rescan F(i-1, 1) ... F(i-1, j-1) to pick the maximal value, since to calculate F(i, j-1) you have found m = max{F(i-1, k)} for 1 <= k <= j-2, then in calculating F(i, j), max{F(i-1, k)} = max(m, F(i-1, j-1)) for 1 <= k <= j - 1. Hence in O(1) time you can determine F(i, j).
    For even i, you just do from decreasing j ,the trick is the same.

    Hence all F(i, j) can be found in O(nm) time.
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
What is the test 8 for F?
Could someone post it please?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    4 5 3
1 2
2 3
2 4
1 3
1 3
a 1 2 4 3
b 1 0
c 4 3 1 2 5
a 1 2 4 3
b 1 1 5
c 4 2 1 2
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
And please gimme test 25 of task B.
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
what is the test 11 for F?
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
I think i have some trivial error in E. Could you give me test case 2, please?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
    3 3
-2 1 -5
4 -5 -4
-1 1 -1
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks, my error was not in the coding, but in reading. Somehow, %lld does not work in Codeforce.
      → Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
What is the test 6 for F? Thanks...
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Just to make sure you know:
Links for tutorials B,D,E is not correct
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    The url is http://codeforces.me/blog/entry/edit/916, delete the "edit/", http://codeforces.me/blog/entry/916 is useable.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Thanks.
    → Reply