map's blog

Codeforces Round #289 (Div. 2) + qualifying round for the WCC
By map, 9 years ago, translation, In English

Hello, Codeforces! I'd like to invite you to Codeforces Round #289 (Div. 2). It'll be held on Saturday, January 31 at 15:00 MSK and as usual Div. 1 participants can take part out of competition.

This round will be carried out according to the ACM rules, which means that you get verdict of your solution on-line, and the duration time is 3 hours.

These differences in the rules are caused by the fact that this round is the second qualifying round for the WCC, which stands for Winter Computer Camp and can be also mentioned as ZKSH. Official school website — hhttp://it-edu.mipt.ru/en/zksh2015. There you can find the selection rules for WCC.

If you are a school student and you want to participate in the selection to WCC here are the steps:

  1. Sign up for the school at http://goo.gl/kz2qSf, if it was not done earlier.
  2. Create a free account at codeforces.com, if it was not done earlier.
  3. Sign up for the round on the link http://codeforces.com/contestRegistration/509. You should put a tick in the box "Do you want to participate in the selection to WCC?", and provide your last name, first name and email, which you entered for registration in the first step.

If you have any questions feel free to write to the address of the organizing committee: [email protected].

The authors of the contest (WCC technical committee) are really grateful to Max Akhmedov (Zlobober) for the help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for contribution to the development of programming by creating systems Codeforces and Polygon.

UPD. Tutorial — http://codeforces.com/blog/entry/16119

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

Comments Comments (99)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I have 2 question :

1)Are there any T-shirts ?

2)rated?

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

    1) According to the results of the competition, top 5 students, who will take part in WCC, will receive prizes. 2) Rated, I hope =)

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

    if it is not rated then why it is div2 only?

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

      it is rated only for div2 participants

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

You can use this picture :)

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

Can Div1 contestant participate in the selection to WCC?

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

The sign-up is in Russian. Is the WCC available only for Russian speaking students?

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

    If you look closely, there are English translations below each Russian statement.

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

I want to know how many questions are there?

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

I think 5000 users register for contest :)

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

During the contest I can realize that I am in Computer AGE.

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

Will the problems be arranged according to the expected order of difficulty? Also will there be a scoring system or we'll be rewarded on problem count and submission times with 20 mins penalty for wrong submissions?

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

    "we'll be rewarded on problem count and submission times with 20 mins penalty for wrong submissions" is correct. I can't promise anything about tasks.

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

I hope that these rules used in all contests on codeforces ..

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

Standard input/output?

How many tasks?

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

Hacks or no hacks?

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

is this rated?

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

Can I participate in this contest without signing up/registering for WCC?

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

What time during the contest will the scoreboard be frozen?

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

Hope to become expert this round))

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

你好

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

    Are you sure that people in here can understand what you say?

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

By using ACM ICPC rules, does it imply that the language restricted (only C, C++, Java)? I hope it does not.

UPD: my bad. I just opened the rules. We can also use Pascal and Python.

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

    I think, every language supported by Codeforces, will be available.

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

let the game begin.. Good luck for all

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

It's 15 minutes past the contest .. and I can not submit my code for A :/

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

Nice System Of A Down reference in Problem E :)

(IEAIAIO and BYOB are both songs by System Of A Down)

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

And dreamoon_love_AA finally has done it! Congrats!

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

Nice problem :)

thanks map

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

Sorry to say this but, imo(i dont know about others) your problemset was the worst i've seen in codeforces.

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

    Why do you think so? I really liked problems, especially F, even though I have no idea how to solve it.

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

      Well i myself dunno how to solve F but A-D were really bad

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

        What are you talking about? They were really good problems. Also, problemsetters put a lot of their time and effort into making such problems. Try to be grateful and don't dishearten them with such comments.

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

        What is bad in D?

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

        F was nice, but yeah I didn't really like many of the others.

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

    That problem C -_-

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

what is the 7th test case in problem C?

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

    same problem

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

    I don't know the test itself but what's your soln for this input?

    2 300 300

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

      3999999999999999999999999999999999 4899999999999999999999999999999999

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

    Try 10 38 38 38 38 38 38 38 38 38 38

    answer: 29999 38999 39899 39989 39998 47999 48899 48989 48998 49799

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

      my code prints the same as yours, but still wa at 7

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

        what about 8 1 1 1 1 1 36 20 21 answer: 1 10 100 1000 10000 18999 19019 19029

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

How do you solve E ? I feel it is dp but not sure how.

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

    you can have a look at my solution .. i did it so simple you even can't believe .

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

    Let call ai = 1 if si is a vowel else ai = 0.

    sumi = a1 + a2 + ... + ai

    Number of vowels in all sub-strings with length x is:

    Pi = (sumx — sum0) + (sumx + 1 — sum1) + ...

    = (sumx + ... + sumn) — (sum0 + ... + sumn - x)

    The result is sum of Pi / i

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

    there can be something like this http://pastebin.com/E2pCyWmu

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

    I didn't solve it either but I think it's dp too. We look at each letter independently and if it's vowel we add to answer sum of some harmonic serieses (we can calculate it using this value for last letter and array of prefix sums of harmonic series)

    UPD: now I see that I was wrong and it can be solved easier another way.

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

    Consider the vowel in the string at the position i. It contributes to the answer only addends of the form , where k ≥ i and j ≤ i, because it is only contained in the substrings of the form si..j, j ≤ i ≤ k. After what, we can sum this expression for all i, j, k such that si is a vowel and j ≤ i ≤ k. Plugging this into WolframAlpha, we can get the final formula for the answer: , where Hi = 1 + 1 / 2 + ... + 1 / i is the i-th harmonic number.

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

When will we be able to look at others' solutions?

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

How to solve problem C? I saw a lot of accept is this problem, but I didn't know how to do it.

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

    At the each step remember a last output value and a sum of digits in it. Then add 1 to last value and try to get the smallest integer which has the desirable sum of digits. To do it basically set less significant digits to 9 if you need to make sum of digits larger or set them to 0 (and +1 to digits before them) if you need to make it lesser.

    Use bignum arithmetic.

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

Hi, when will the practice problemset become unlocked?

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

Any idea about how to solve prob. E ?

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

    Magic 9648904

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

      Why magic? :)

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

        It`s my code: 9652904 I have no idea about how you code works. My solve calculate count of intervals with length one divided by one, length two divded by two (etc.) for all positions (array VAR).

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

    It took me half an hour to push formula...And I solved this problem. answer=(1/2 + 1/3 + ... + 1/n)(a[1]+a[n])+2*(1/3 + ... + 1/n)(a[2]+a[n-1])+...+(n-1)(1/n)(a[n-1]+a[2])+a[1]+a[2]+a[3]+...+a[n] if a[i] = I or E or A or O or U or Y then a[i] = 1 n means length of string And it's my code: http://codeforces.com/contest/509/submission/9654437 :-)

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

I really wrote bad and long solution for C but finally I got accepted :D

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

    I also wrote bad and long solution for E and I got accepted :-)

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

When clicking on submit button on the right, I sometimes had to wait around 3-5 minutes before my solution got accepted since previous 3 contests. :(

All other websites were working in a decent speed on my internet connection during the time of the contest.

Has somebody else faced this lag, or I do I need to get an alternate connection.

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

    same here site page for submit will not open..

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

    It is always laggy for me too while I am in college but works fine when I am at home . You could go to IPC or library for faster speed.

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

map, when the editorial would be available ?

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

    Part of tutorial is available

    We hope to finish it today.

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

      riadwaw, Your llink is the link of this post, no editorial. :(

      UPD: I think Now it is fixed.

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

        Fixed, thanks

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

          riadwaw, Thanks for the link and a big hand for the editorial. :)

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

          Hi, do you happen to know when the problemset part of the site becomes unlocked?

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

            Unfortunately, I don't know it. Probably some action from administration is needed.

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

http://codeforces.com/contest/509/submission/9645857 Why am i getting Wrong Answer on test 1, output is correct on my pc.

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

    But in the system and ideone, your program gives "NO" as the output of the first test case, while the answer should be "YES"

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
     FOR(K, 0, 102) {
   if(abs(c1[K]- c2[K]) > 1) {
     f = false;
     break;
   }
}

    but your array sizes are 102 and your for loop define is <=.

    Don't try to use defines if you are not familiar with them.

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

Nice contest. Me mostly enjoyed problem C, stringy one.

→ Reply