Nerevar's blog

Saratov school team programming contest 2011
By Nerevar, 13 years ago, translation, In English

The X regional school team programming contest will be held in Saratov on Tuesday, 18 of October. The jury has prepared a set of interesting problems. We came to conclusion that it will be unfair if these tasks are available only for the onsite school teams. That's why we decided to organize a contest with these tasks on Codeforces.

The contest starts at 10.30 MSK (half an hour later than the start of the school contest: it is done to give the organizers some time to ensure that everything goes well) and will last 5 hours. The rules of the contest are official ACM ICPC rules. Both teams and individual participants are allowed to take part in it. For individuals the contest will be rated. Registration will be open until the end of the contest.

The contest was prepared by members of the best teams of the Saratov State University: Gerald Agapov, Polina Bondarenko, Ivan Fefer, Artem Rakhov, Nickolay Kuznetsov, Edvard Davtyan, Pavel Kholkin and Igor Kudryashov, as well as by our "veterans": Natalia Bondarenko, Michael Mirzayanov and me, Dmitry Matov. Maria Belova also did an excellent job and translated the statements into English. 

Enjoy the contest!

The statements will be available as PDF via links:

It will be file input-output in these problems. Read statements carefully.

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

13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Thanks for leaving registration till the end of contest and thanks again for making it rated for individuals!
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I am getting this verdict "Idleness limit exceeded on test 1"

what does it mean?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I am also:(
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    You need to use files "input.txt"/"output.txt" for input/output
    → Reply
13 years ago, # |
  Vote: I like it +37 Vote: I do not like it
I liked the contest :) Thx for making it rated :)
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
In problem H. How does the judge solution say "v" is accepted for "java" for test case #1. The English version of the text says, you are allowed NOT to change the word if its length doesn't exceed 4.
Am I missing something here?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    But you may shorten it. "You are allowed not to shorten the initial word if its length does not exceed four characters."
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Edit. Ok I see: "allowed not" not "not allowed"...

      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh x-( .Now, I understand what you'll intend by "allowed not"! I assumed you'll meant it to be "not allowed" during contest. Thereby, getting WA during contest.
      Thanks, for the clarification.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone give a simple proof for problem E? I solved it by trying on chessboards of size 1,2,3,4, then I "supposed" it could be "that" easy and submitted. I was very surprised when I read "Accepted" (because I wasn't able to understand why it works)
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
well you can see that if it is even:
n = length of the board.
  if the first player play x,y then the second player play n-x,n-y and it is free     because with this way to play the board will be symmetric.
  
the other case it is odd the first player play the center point ((n+1)/2,(n+1)/2) and he does the same that the second player in the other case.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the basic idea of solving problem H? I can't get it even if seeing other's solution.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Consider two sets of strings S (the original words) and T (the possible representations of all words). Construct a node in a graph for each word in each set. Connect a word in S to all possible representations of the word in T to form a bipartite graph. Then just compute the maximum matching in that graph (matches each word with its representation).
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I've tried to solve problem F (Spiders).
I got a solution that is accepted with Visual Studio, but gets WA on test 1 with GCC 4.6
Locally I tested and it worked with gcc 4.2 and 4.5
I had an array and had to get the maximum value. When I printed the array it showed the right one (on codeforces) but when I try to get the max value ... It just gets a different answer.

Can someone look at my source code... maybe I'm doing something wrong and not respect the standards ?
http://ideone.com/LWbY8

Thanks in advance
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    You forgot to initialize a[] before reading edges.

    Never mind.


    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I think that this buggy GCC optimizer is guilty. If you change your for with iterators to
    for (int i = 0; i < a[u].size(); i++)
    it'll work.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Yes, you are right. Just got accepted.
      It's pretty weird. Got to remember that!

      Thanks a lot :)
      → Reply