KAN's blog

Codeforces Round 517 (and Technocup 2019 — Elimination Round 2)
By KAN, 6 years ago, translation, In English

Hi all!

This weekend, at Oct/21/2018 11:10 (Moscow time) we will hold Codeforces Round 517. It is based on problems of Technocup 2019 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2019 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The round authors are Kostroma, Golovanov399, komendart, Denisson and Dashk0.

Have fun!

The round is over, congratulations to the winners!

Technocup 2019 - Elimination Round 2

  1. Holidin
  2. receed
  3. Sonechko
  4. radoslav11
  5. scanhex

Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2)

  1. Radewoosh
  2. ainta
  3. 300iq
  4. TLE
  5. RAVEman

Codeforces Round 517 (Div. 2, based on Technocup 2019 Elimination Round 2)

  1. cz_yixuanxu
  2. orbitingfIea
  3. I_Love_Irelia
  4. djq_fpc
  5. buaads

The editorial is published.

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

Comments Comments (96)
| Write comment?
»
6 years ago, # |
  Vote: I like it +67 Vote: I do not like it

CF rounds on weekends are the most fun.

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

Perfect time for Chinese users!

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

..

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

This weekend,

It's not a weekend in most Arabic countries XD

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

How many problems? When do we know the score distribution?

PD: Just a joke: Where is thanks to Mike and Polygon and ITMO??

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

Elimination round(not CF) will be rated or no?

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

very less participation :(

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

Delayed by 5min!

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

    Before the contest 00:01 remaining

    Me: Let's bring it on!

    Before the contest 04:59 remaining

    Me: Oh f**k.

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

    At least 5 min

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

    Thanks, I afraid something went wrong with my connection

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

delay :(

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

Score distribution?

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

I love contests at 3 am :)

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

I am not able to submit code, getting error "you have submitted exactly the same code before". Please someone look into this matter. I have not done any submission in that problem.

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

div2D was dp or bfs?

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

    Both of them :)

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

    I spent so much time on this problem and didn't manage to do it in the end, is there a way to compute for each i, j the lexicographically smallest path from i, j to n, n?

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

      I did it with dynamic programming. For each field you just need to know if you want to go right or down. So create a table int dp[2001][2001] with 3 possible values: 0 — go down; 1 — do right; 2 — it doesn't matter (both going down and right will produce same string). We fill entries of dp from n, n to 1, 1 (backward). how to fill this array? For boundary entries (i = n and j = n) it is obvious, for others dp[i][j] = fillDp(i + 1, j, i, j + 1);

      //(x, y) - pointer which is lower, (b, a) - pointer which is to the right
int fillDp(int y, int x, int b, int a) {
    if (arr[y][x] < arr[b][a]) return 0; //you can only go down
    if (arr[y][x] > arr[b][a]) return 1; //only right
    if (b == y && a == x) return 2; //doesn't really matter which way
    //if letters are the same and we check different fields
    //we either move according to dp or (if dp == 2) we move pointers closer to each other
    if (dp[y][x] == 0) y++;
    else x++;
    if (dp[b][a] == 1) a++;
    else b++;
    return fillDp(y, x, b, a);

      Edit: arr = original array with letters

      Computing path is just going with pointers in dp.

      I can't actually prove it works in O(nm) but I got accepted. Here is my solution — a little more verbose: 44647952

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

What was pretest 15 in div2 C? :(

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

    Something like 147694707 63714381

    The sum m + n in this case should be 20562.

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

      It works for me, and I got pretest 15 wrong. What's special about this test case?

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

        I stress-tested my WA on pretest 15 with the solution that passed that test case to get that. I'm sorry that I don't see anything special about this test case :(.

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

    Got 6 WA in that. But, figured it out. It was because of not using long long int.

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

300iq Becomes Legendary Grandmaster!!

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

How do you solve div2B?

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

    DP by O(16n) I'm not sure it's a correct algorithm.

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

    DFS is enough.

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

      Sorry! I find a hack data to hack DFS. It is:

      100000
3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 ...(repeat)
0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 ...(repeat)

      answer is:

      YES
1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 ...(repeat)

      I have hacked lots of codes using DFS to solve problem B. If we add this data for judging, a lot of codes will be hacked.

      The reason why it can hack DFS is when a = 3 and b = 0, t can be 0, 1, 2, 3.

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

      Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

      Because if ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 1.

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

    Brute force the value of tn. Given ai, bi, and ti + 1, it is easy to show that there can be at most one ti that satisfies the given constraints.

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

      Yes, and ti equals ai + bi - ti + 1. Because x&y + x|y = x + y.

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

        How did you get this relation?

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

          By Binary Numbers.

          x + y = x + y — x & y + x & y = x + (y — x & y) + x & y

          Because any digit of x and that of (y — x & y) are different,

          So x + (y — x & y) = x | y

          So x + y = x | y + x & y

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

Div2F / Div1D was bfs?

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

I finished fixing div2.D and the contest is over

Now, I hope my solution is not correct ...

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

Lose to constructing.

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

How to solve div2-C , i tried bin Search but i knew it's not working good ,, any hint ?

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

    Let k be the largest integer such that 1 + 2 + ... + k <= a + b. Then it's always possible to construct an answer with n + m = k.

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

      thank you :D

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

      Can you explain how?

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

        Like before, we have S = 1 + 2 + ... + k <= a + b. Just iterate over i = k...1 and greedily subtract from a whenever i <= a. If S < a, then we're done, otherwise it should be easy to see that we can always get a subset of elements that sum exactly to a, in the end, so the sum of remaining items is S - a <= b.

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

      Then it's always possible to construct an answer with n + m = k

      Why is it so?

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

in B all a[i] and b[i] gives only two numbers except when a[i]=3 and b[i]=0 then t[i]=1 and t[i+1]=2 or t[i]=0 and t[i+1]=3 right?

I couldnt submit my last solution because I did not understand my new stupid error while debugging which is we can't write cout<<1&3; that gives an error and Idk why

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

    when you type cout << 1&3 compiler reads << as bit shifting

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

      man if my solution was right and i couldnt submit it because of that ... meh

      edit: it's wrong anyway:P

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

I slept just 3 hours to take this CF, let's see how my C fares the system tests :Dd. Already had to resubmit once during the contest

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

    How to solve it?

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

      I use bfs for n ≤ 12. If n is greater than 12, find the last 1 appearance and modify it to make sure that at most two steps would be used to set the last 6 positions 0.

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

        So did bfs on bitmask for n<=12 ?

        Also when is answer "No" ?

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

          When n >  = 8, answer is always YES. So you can just brute and check if it's no for n < 8.

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

What was pretest 8 for div2D ?

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

How I solve Div2-C/Div2-A:

  • Write a greedy solution, get WA on test 15.

  • View submission detail and realize the checker's answer is not the same as the sample answer. Screenshot from 2018-10-21 05-32-10.png

  • Analyze the pattern and write a new solution.
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wow, very weak pretests again

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

Full Feedback contests are the best.

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

    But remember that in most rated Codeforces round, you don't receive full feedback, especially when the pretests are weak :D.

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

    I'm of the opinion that problems which are going to have very few solves anyway almost always ought to have virtually full feedback, i.e., the systests should not have anything special (new cases, etc) that the pretests don't have, especially considering that if you fail systest you get a score of 0.

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

It seems that div2C/div1A system tests are weak. After the contest I found a bug in my code that makes it fail : for the test
7 1 it gives the following output : 

3
2 3 4
1
1

which is obviously wrong. And still my solution got AC. (tmw when you think that the pretests are weak but after the systests it turns out the systests are weak too xd)

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

    Solutions should be rejudged if that's the case.

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

What is the answer to this case for C? LHiC's AC code gives NO.

7
1 0 0 0 0 0 0
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    My AC code gives

    YES
3
3 5 7
3 4 5
1 4 7
    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it 
    YES
3
5 6 7
1 4 7
4 5 6

    Weak tests ¯\_(ツ)_/¯

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

    Similarly, I resubmitted because my first submit uses too many operations in the case

    100000
0 1 0 1 0
...
0 1 0 1 0
0 0 0 1 1

    (line breaks added for clarity)

    But turns out my first submit would also have passed :/

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

Waiting for tutorial.

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

Waiting for my new rating... And of course waiting for tutorial....

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

The tests for div1 C seem to be so weak that some wrong codes passed.

44641451 The hack data is : 1 1 0 1 0 1 0 1 0 1 0 ...

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

    Uhhhh that is the obvious "naive" solution that I didn't bother coding because surely it wouldn't pass right?.... but it does.

    And then I didn't find a good solution during the contest :/

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

    After more thinking I realise this solution is quite solid with a small tweak. If try it twice and take the best solution, once normally and once ignoring the first 1 (and do the first 1 manually later) then it is perhaps not possible to make a counter case.

    Anyway there are like dozens of solutions and I came up with zero of them during the contest.

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

can someone plz tell me whats wrong with my code for Div2D?? 44650538

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

As I see, the problems and the score distribution in the Technocup Round and in the Div 2 version were the same. However, the scores obtained in the Technocup Round were smaller compared to the Div 2 version. For example, score 2500 is in top 40 in the Technocup, whereas in the Div 2 version, someone with 2500 is on the 200th + position. So I guess that participation in the Technocup would have helped you increase your rating more than in the Div 2 version.

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

Maybe the tests for Div1C are not strong enough

these solutions were hacked by my data.

44638710

44641451

44641456

data:

125
1 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0

Update: Oh, after posting this review, I found that cuizhuyefei has already mentioned it

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

Well, after contest, I have found a hack data to hack DFS solution in Div2.B.

We just use a form like:

100000
3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 ...(repeat)
0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 ...(repeat)

answer is:

YES
1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 ...(repeat)

If you use DFS to solve this, you will get Runtime Error.

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

    If possible, please add this data to hack someone who didn't solve the question well, including me :-) . Thanks.

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

    Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

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

I faced problem in B when ai =3 and bi=0 then ti and ti+1 can take 0,1,2,3 .can anyone help?

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

    You can try to make first t( t1 ) be 0, 1, 2, 3. And the sequence will be constructed.

    We can think about this:

    If t1 has been determined, t2 will also be determined. Obviously, if ti has been determined, ti + 1 will be determined, too. For example, if ai = 3 and bi = 0, ti can take 0, 1, 2, 3. But don't forget that ti has been determined. ti will only has one value to choose, and it's easy to solve. Hope I can help you :-).

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

the rating changes is unfair. in official round if you solve just 3 problem you will get high rating changes but in Div2 round if you solve 3 problem your rating change is not as high as rating chane in official round.

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

I noticed that the announcement and editorial are not linked to the problems, can some admin do this? Thanks

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

Does anyone know if there will be a parallel open round again for the upcoming Technocup Elimination Round 3 in a few days?

→ Reply