MikeMirzayanov's blog

Getting ready for ACM-ICPC: weekly trainings on Codeforces
By MikeMirzayanov, 11 years ago, translation, In English

The new season of a collegiate team championship ACM-ICPC is about to start. For example, the registration for the Southern (Saratov) Subregional Contest is already running. I am sure that many participants of the Codeforces rounds will take part in ACM-ICPC this year.

We are launching a series of weekly practice trainings on Codeforces. Naturally, they will be held within Codeforces::Gym. Feel free to participate!

The practice starts at about 12:10 PM (UTC), which is 16:10 Moscow Time. We are going to practice using the problems of different contests of the past years. All you need is common sense and observing these simple rules:

  • We will not publish the problem source before the practice starts. We want you to solve the problems on your own in a fair competition. If you use somebody else’s code or cheat in any other way, you will be disqualified. If you don’t want to solve on your own, that’s fine, you don’t have to. But spoiling the practice for others is unacceptable.
  • Do not discuss the problems till the practice ends.
  • We will rarely answer the questions about problems. If you’ve found some obvious bug, please let me know. We will fix the bug and send everybody the note about the fix.
  • If you have a coach account (and you do not participate in the practice), we will be grateful for your help.
  • Please register for the practice with the people from your team who actually participates in it.
  • From time to time, I am going to ask some of the jury of the past contests or coaches from other higher educational institutions to help with preparing or share materials — your understanding and help will be greatly appreciated!
  • if you solved the contest problems before just switch to another training or inform us via problem questions form, we will move you to out-of-competition role.

The first practice takes place on September, 11, at about 12:10 PM (UTC).

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

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

this contests would be really useful. thanks for this.

If there is good amount of participation, try to increase frequency of contests.

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

Are the problems original or from past regionals?

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

    Sorry, I didn't read the announcement carefully. They are from past regionals.

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

Great work !

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

what will be the difficulty of the problem set in comparison with Codeforces's regular contest ??

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

    It depends on a contest. I hope in most cases it will be interesting for the wide range of participants.

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

Will these be rated in any way?

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

Thanx a lot... We were really waiting for this wonderful oppurtunity... :)

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

I know you guys probably know, but,

This is awesome. round of cheers

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

Can I participate in the Pratice without team?

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

looks like a good training for icpc…

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

This should be really helpful. Thanks a lot!

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

how many episodes are in a season ?:D

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

how can i participate to this contest when i click contest area threre is no contest availble.

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

    re i found it :D it was in the gym section

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

Will the editorial of these problems be published after the contest?

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

    I doubt it... editorials aren't normally published for gym trainings. But you can try googling the contest that the problems are taken from, there should be an analysis or something...

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

When can we get to see the test cases?

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

    Tests and other's solutions are available if you solved the problem.

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

      How does one view the test cases? They're not below the source code even for problems I have solved.

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

    You can get test cases of problem in GYM only when your max rating is greater than 2200 (When you become Grandmaster).

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

Did anyone get javascript alert box when announcement came? Somehow i didn't get it and it cost me problem B. I thought long means 64bit, at least in my compiler it is 64bit.

Edit: What is the best way to solve B? I've pre-generated all the k-gon numbers and searched in them, runtime is not good.

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

    My solution: we store one polygonal number for every "index", in a heap, starting with the smallest ones  ≥ s (we can binary search or bruteforce those). Along with the value in the heap, we remember the "index" and order (as in "this is the k-th smallest") of the polygonal number, so we can easily increment it — change it to the k+1-th smallest.

    Now, we keep looking at the 2 smallest entries in the heap; if they're equal, we have one of the numbers we need — take out of the heap all the entries with value equal to that, print them, increment and return them to the heap. So the time complexity, if x =  how many polygonal numbers are  ≤  the largest one we print, is per test case.

    Why should this work? We have guarantee that the largest number we print, L, is at most 232; polygonal numbers grow quadratically (and with large constant for large indices), so it's . For small n, that's enough. For large n, we find out that L is much smaller than 232, because there are quite a lot of chances for poly-poly numbers to occur if we have many polygonal numbers to choose from. So the constants play in our favor if we cut down our searches to the range we need :D

    Surely you notices how many polygonal numbers there are in total for indices  ≤ k: . Despite the good constants for large indices, those are too many if there's a log-factor or bad constant added. Maybe you could make such an idea pass the tests, but it must be hard.

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

      "We have guarantee that the largest number we print, L, is at most 2^32" But in the question it was mentioned that the solution that we will print will fit in long. Then how the 2^32 assumption ? Any intuition would help

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

        It's a 32-bit "long" (the one in C++, not Java). That's at most 2^32.

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

          C++ long is 64bit too, at least in modern compilers. I am using g++ 4.7.2 , before writing the solution i wrote following lines to check

          long int x=1000000000000000000;	
cout<<x<<endl;

          This works fine,no overflow. So i obviously assumed problem setters meant 64bit. I saw the announcement when there was 6-7 minutes left, so i couldn't finish coding.

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

            C++'s long int is only guaranteed to hold values up to 231 - 1. Also, on many modern platforms it is 32-bit.

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

Is each episode about a particular topic or like regular contests there are questions from different topics in each episode?

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

Is it possible to see contestants' solutions?

→ Reply