UESTC_Nocturne's blog

Codeforces Round #201
By UESTC_Nocturne, 11 years ago, In English

Hello everyone!

Codeforces Round #201 is scheduled to take place at Friday, Sep. 20th at 19:30 MSK(23:30 CST)

Setters are: CMHJT and me.

Testers are: error202, havaliza and tourist.

Thanks to MinakoKojima for her help in rewrite the statements into codeforces style, Delinur for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

Special thanks to tourist and Gerald in giving advise about the problems so we could put them in a more proper order.

500 — 1000 — 1500 — 2000 — 2500.

We are going to use standard score distribution in both divisions. The problems are not so hard, but you need more thinking rather than coding.

Good luck!

UPD1: Congratulations to the top 5 winners in each division!

DivI

1.cgy4ever

2.rng_58

3.PavelKunyavskiy

4.Egor

5.liympanda

DivII

1.Thrax

2.renannewbie

3.socksister01

4.SJTU_WengJian

5.cat_leopard

UPD2: the editorial is published here

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

Comments Comments (94)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Thanks for the contest!

The problems are not so hard, but you need more thinking rather then coding.

It seems that the problems will be very interesting.

Good luck to all participants!

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

    Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.

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

      Are you a bot who copy automatically comments with high number of upvotes? That's why you just used tjandra comment witout any reason? Edit: After looking at your previous comments, yes, it's exactly that...

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

Good luck to everyone.Thanks to XHXJ.

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

Compact and interesting statements wanted! Thanks! :)

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

Orz XHXJ ....

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

I will definitely take part in this round because UESTC_Nocturne has given me a lot of suggestions on my computer programming. Special thanks to you and Good luck to everybody. By the way,his nickname in pinyin is "xue jie"~~~~

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

ORZ...Good luck! God bless us!

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

oh ! 26 hours remaining ! I can't wait ! :-<

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

Thanks to the setter for preparing this contest :-)

If there're some tricky case, I hope all tricky case is put on the pretest, so if my code got accepted (pretest passed) it'll accepted too after system test.

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

    Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.

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

    So, What does hacking mean then?? All of solutions will be right and no one could hack another...

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

A small question, xiaodao...her help? ^_^

tourist!!!! Always be my super idol!!!!

Hope it to be an awesome round and Everyone enjoys it!

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

Sooo you say it is going to be the best tested round?:D:D

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

I apologize for my ignorance, but I always wondered what does UESTC stand for ?

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

UESTC_Nocturne CMHJT It's first time for you in prepare a Round ?

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

Good luck to everyone!Long time no coding in codeforces.

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

Best of luck to everyone , problems set by some of the best people in the arena , looking forward to it :)

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

first time to attend div1 I know it is so hard for me but good luck

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

minus

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

today and he will codeforces 201, and involves more than 3,000 people

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

Why I always got WA on #4 on D Div2?

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

someone push Start System Testing button please

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

Great round, thanks! Problems are interesting, indeed there was no need to write big solutions, except, maybe, problem B. Seems like it should cost 1500 instead of 1000 — it's the most hardcoding problem today =)

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

Why solutions are not visible even after the contest??

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

Very great contest, problems were very intresting but not much hard. Could someone explain the solution of Div2.C / Div1.A? By induction I proved that if we have k numbers and there is no valid move, those numbers should be a, 2a, ... , ka, but couldn't find the complete solution.

Thanks in advance.

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

    Try GCD to solve this kind of tests.

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

    Let's denote g = gcd(a1, a2, ...an). It's obvious that every number in the end will be divisible by g. From other side, we can obtain g with Euclid Algorithm. Thus we can prove that resulting set is . So the answer is , where amax is the greatest ai.

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

I think the worst thing and the best thing in the world may be you HAVE to skip a high scoring solution because you find a bug in it. :D

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

had i seen the gcd part in C, it could have easily been my best! Hacked two solutions which made the same error as me. Good and false-motivating pretests!

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

After seeing the number accepted solution from the dashboard,it seems, in div-2 problem A is harder than problem B ... :(

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

In problem D, the following phrase confused me:

Please note that mzry1992 can give orders to the robot while it is walking on the graph. Look at the first sample to clarify that part of the problem.

Does it mean that our orders can depend on where the robot goes, as opposed to some set of orders fixed before the movement?

In the contest, I misinterpreted it as "the robot can receive orders only when it moves from the starting vertex", and that makes the statement controversial.

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

    Yes, you can determine whether give a order to robot on every node it pass.

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

How did you solved A ? Thanks.

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

it seems lots of people FST in problem C. :)

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

    I hate TLE! I think an O(nlogn) algorithm should pass the system test.

    However, it didn't change anything about this round being a good round.

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

      my O( (b - a + n) log n) solution works in 124ms.

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

    Yes, this is thanks to you.

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

I did not participate in this round,but i am glad to see so balanced and amazing problems thanks to UESTC_Nocturne.

I want to solve problemc C(div 1),I know only DP solution in O(n*(a-b)).what is correct solution?

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

    each time choose such x_i that makes a-a%x_i minimal and a-a%x_i>=b. the correctness can be proved by the monotonicity of your dp function.

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

Tasks are very nice, especially A, C and D. (B is a coding task and it's fine. For E, I don't know the solution yet.)

I'm very luck to win this round by finding this trick in task C: x[] can have repeat numbers.

Thanks for the writers/testers!

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

    Congratulation！For E, the standard solution is short, but need to find out something intereting, we will post editorial later and you can find details in it.

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

    I've finally solved E in upsolving :) I had the idea during the round but didn't manage to deal with corner cases in time.

    Here's my solution: http://codeforces.me/contest/346/submission/4523388

    Hopefully long method and variable names make it understandable.

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

    Oh, and congratulations on the victory!

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

When will ratings be updated???

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

Why is TL for problem C is only 1 second?

I wrote a solution in java during the contest and got TL (4522683). But when I wrote the same in c++ after the contest I got AC (4522630). This makes me sad.

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

    There exists a subtle O(a-b+n) solution.Even written in java would get accepted.

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

      Well, yes. The solution is very nice indeed. However I found an (a-b) log n solution and I settled for it, because I figured it's common sense it should pass and it didn't. There are other (a-b) log n solutions that do pass however, but have smaller constant or use less memory.

      Did you intend to only accept the linear solution? If that's the case, why not give a-b <= 1e7 so people know the log n factor is too much?

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

        No,most (a-b) log n program written in java got AC.

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

      I guess you might forget that you need to sort xi or you use radix sort instead of quick sort.

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

Great contest!! Thanks to the problem setters and testers!!

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

Cool problems. Never had so many dumb bugs in a contest in my life :S

For example, in A, I computed the gcd, but forgot to divide by it, i.e. didn't do anything with it :D

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

How to solve C (div1)?

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

    There's a apparently a linear solution, but an nlogn solution that passes in time (for example, my solution in the practice room) is this.

    First, it's very important to make the given numbers unique, i.e. eliminate duplicates. Then you take each x_i and for every multiple of x_i between a and b (call it y) update best[a-y] = max(best[a-y], x_i) (I'll explain what best[i] is in a second). This whole thing is O(nlogn) (the worst case is when X = [2, 3, 4, ... n+1], because then you have the most multiples).

    When you have that, then you process numbers from a down to b. For every such number (let's call it c), you want to compute the minimum number of moves you need to do to get to it from a (that's the 'minlen' variable in my code).

    There are two options basically for each c. You either use the solution for c+1 and reduce a by 1, or you make a "jump". You store all the minlen values for larger c values in a Fenwick tree (or some such structure that allows you to do range minimum queries). Then you use best[c-a] to know what is the largest x_i that is a divisor of c. Using that x_i, you can get to c from any number in the set {c+1, c+2, ..., c+x_i-1} in one step. So you query the Fenwick tree for the minimum in that set, and increase that by 1.

    HTH

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

My code prints output in pretest-1 in my PC BUT it prints no output in codeforces. Can anybody explain?

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

Nightmare。

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

can anyone explain me logic behind the solution of problem C of DIV 2 ? I have seen 1-2 codes , that is something i was thinking while contest, but still i am not able to get that solution. Can anyone please explain little bit ? thanks in advance.

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

    Idea: In the end of the game all numbers printed will be g 2*g 3*g ... MAX_NUMBER where g = gcd(a[1], a[2], ... a[n])

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

      This is actually not correct, though the answer with that assumption stays the same. Consider the case 2, 3, 5. Here g=1, but you can't make any moves, i.e. can't add 1 or 4.

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

        I can add 1 = 3 — 2 and then 4 = 5 — 1.

        Also, obviously we may get g because of Euclid algorithm. After that we may get all the numbers up to MAX_NUMBER using - g

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

          Ah, you are correct, my bad :)

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

    I guess this is problem A from div1 (the Alice and Bob one)?

    First, notice that it is never possible to get a number that is not a multiple of the gcd of all the numbers (let's call the gcd d). That's because if d divides both a and b, it will divide |a-b| as well. Therefore, you can divide all the numbers by d.

    Also, you will never be able to get numbers larger than the max number (obviously), or lower than 1. Now, the key thing to notice that out of the remaining numbers from 1 to MAX, the numbers you can't get always come in pairs. That is because if you have three numbers a<b<c and a+b=c, you can't get either c-a or c-b. Therefore, the solution depends only on the parity of the number of missing numbers.

    Edit: actually, you can get all the numbers from 1 to MAX (after dividing by d) -- see the answers above.

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

Problem 346C - Преобразование числа has already been used on Baltic Olympiad last year link.

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

    Sorry but .. what is the connection between this two problems? ..

    And ... is there any website I can submit these problems?

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

      The differences are that in BOI task you have to transform n into 0 (also there is many n's), you can use only second type operations and all x[] values are prime (but it doesn't really matter). When I saw problem C, I wondered that I just know the solution, which should also get AC.

      I don't know if it is possible to submit BOI problems somewhere, but here are statement + test data + solution. So, it was possible to find the solution during contest, which is not so good, I think.

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

        There are literally thousands or even tens of thousands of problems with solutions on the web. Sometimes duplicates will occur, there's nothing really wrong with that. Probably 99% of the competitors in this round never saw this particular BOI problem.

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

        Since b is no longer always zero, there are more necessary tricks to avoid getting TLE.

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

Div2 D, had around 140 submissions , but only 10 got AC. Mine failed on #30 test case and cant seem to figure out a way around it. Any hints on how to solve it ?

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

    You can do dynamic programming where the state (a, b, v) solves the subproblem where you're at index a in s1, at index b in s2 and the first v characters of virus are the suffix of the subsequence you've found in the prefixes of s1 and s2.

    I assume many solutions failed on updating v. When you take a character (s1[a]==s2[b]), it is not enough to check if (virus[v]==s1[a]) and then either increase v or set it to 0. Instead, you must do something very similar to Knuth Morris Prat, i.e. there might be a smaller prefix of virus present in the new subsequence (i.e. the new v value may be smaller than the old one, but not 0). See my code in the practice room for details if you like.

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

4519236

Hacked by this test:

ZZZZZRR
ZZZZZRR
ZR

4520203

Accepted but wrong output for same test. I think CF should add hack tests to final tests like TC.

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

Problem A (Div 2): why "lexicographically smaller"? Simply "smaller".

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

When will we get Editorials for this Round? Nice Problem Set :)

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

What deceptive pretests... originally accepting my brute force on E xD

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

This round was so good. "The problems are not so hard, but you need more thinking rather than coding" was true. Thanks for the setters :D

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

can somebody expain how to use KMP for tracing virus growth in DIV2 Problem-D

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

    Когда выйдет разбор?

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

    not necesary at all , naive string matcing O(N ^ 3 * 26) for this problem , which is fast enough:)

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

      can you explain how to define third dimension in dp corresponding to virus string

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

        dp[i][j][k] , we'are at 'i' in string1 and 'j' in string2 and soltuion string has suffix with maximum lenght k , such that prefix of virus.

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

It was very intersting! Thanks!

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

The robot is so cute, isn't it?

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

I love this competition。

→ Reply