mnbvmar's blog

Codeforces Round #556
By mnbvmar, 6 years ago, In English

Hi Codeforces!

I'm so happy to invite you to Codeforces Round 556 (Div. 1) and Codeforces Round 556 (Div. 2)! The rounds will be held on Apr/29/2019 17:35 (Moscow time). The round will be rated for both divisions. (At least that's what I've been told!)

The problems were written and prepared by me. Thanks to 300iq for the round coordination, and to Radewoosh for his invaluable help with choosing the problemset and testing the problems! Also, I want to give a shout-out to MikeMirzayanov for his amazing Codeforces and Polygon platforms!

My browser's tab bar, right now.

You'll work on 5 problems, and you will have 2 hours to solve them. The scoring distribution will be revealed closer to the round.

def get_end_remark():
    return random.choice([
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!"])

UPD 1: The scoring distribution time!

Div 2: 500 — 1000 — 1500 — 2250 — 2750

Div 1: 500 — 1250 — 1750 — 2500 — 2750

Also, thanks to cdkrot, vintage_Vlad_Makeev and qwertyland who contributed to the round testing!

UPD 2: The round is over! Sorry for misbalancing the difficulties in Div2, it was totally unexpected for us. Meanwhile, you can have a look at the editorial!

UPD 3: We finished the system tests. Congratulations to the winners!

Div 1:

  1. Um_nik
  2. DearMargaret
  3. maroonrk
  4. Reyna
  5. LHiC

Div 2:

  1. jiangly
  2. Simplicity
  3. Netherdrake
  4. C137
  5. kobor

Also, a shout-out to the first solvers of each task!

Div 1 Div 1 Task Div 2 Div 2
Stock Arbitraging 1:57 Ahmad
Tiling Challenge 3:43 praeda_est_supra
Petr 2:06 Prefix Sum Primes 4:20 JamesWilson
ko_osaga 16:27 Three Religions 48:20 jiangly
ainta 28:45 Tree Generator™ 109:53 lzoilxy
Petr 53:52 Abandoning Roads
DearMargaret 83:10 Election Promises
  • Vote: I like it
  • +1064
  • Vote: I do not like it

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

All the handles who were involved in the making of this round

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

It is will be a great round)

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

I think this contest will be hard because 5 problems if problems was 6 or 7 or 8 it will be easier

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

    For such a round, there would be less to worry about, because when it gets too hard for you, you won't submit any solution and it becomes unrated eventually.

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

      There are two types of cases : 1) you just saying and 2) in this case: Suddenly you got a some work and you can't able to even see the problem , Then this rule will help you and you will not get deranked.. i hope you will understand

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

    Even the strongest of rounds always has a weakness.

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

Finaly an announcement without copy pasted part!

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

It is better for me.

  • def get_end_remark():
  • return random.choice([
  • "You will get a T-Shirt"])
→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

it will be interesting problemset :)

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

First round by mnbvmar !!! Let's hope for an awesome one !!!

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

YAY! mnbvmar gets his time to shine!

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

Sorry, does someone know how to use HTML while writing tasks at Polygon?

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

From mnbvmar's browser tags, I guess there will be 8 different problems in this round. It can be inferred that Div.1's A and B would possible be the same as Div.2's D and E, respectively. So I think this Div.1 might be difficult.

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

"Please, read all the problems!"

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

Stop, that was a mistake)

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

    "The round will be rated for both divisions. (At least that's what I've been told!)" :)

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

Very Sad after not seeing Radewoosh in top 10. Hope he will come back...

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

    He can not participate in this contest because of He is coordinator in this round.

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

It's my first time to div.1

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

[deleted]

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

good luck mnbvmar in your first round ! hope it will be interesting .

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

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

Is it going to be hard?

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

The Immortal Nutellian's Round !

Problem-set might be interesting !

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

A legendary number of upvotes for any round announcement I guess. Being an LGM pays. :P

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

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

    We thought Div2-D would be much easier than it turned out to be. Sorry for that. :(

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

Never expected such an unbalanced round from red coders.

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

    I always expect such an unbalanced round from red coders.

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

The era of non-balanced rounds on codeforces has returned, no-matter who is author

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

is it speed test for div2??

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

Reds:

'You can't improve simply solving Div2As'

Also reds:

Sets contest with 3 Div2As and two Div1 problems

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

    Too true. Hopefully I can recover my rating in next contest.

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

Let's face it: most of us just stupid ;)
Seing how many solved Div2D among Div1 I'm thinking that's not such hard problem at all.

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

    The ones who could solve it were busy doing Div1

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

Solution for D? Does it have something with Binary search?

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

    Let $$$x, y, z$$$ be the current length of religions. Consider dp[i][j][k] = Minimum index of string s such that first x characters of first religion, first y characters of second religion and first z characters of third religion form disjoint subsequence in s[1..idx].

    with this Each query can be answered in O(250*250)

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

      my idea was like you. but I don't understand, how can each query be answered in O(250 * 250) ? in worst case, it will be O(500 * 500) = O(2e5) it happens when 1st string has 1 char, and others have about 500 chars ._.

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

        You can assume that no religion will have description longer than 250 characters.

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

          oh my bad :< I forgot that information, and didn't submit D ._.

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

      As I said: not such hard). Never think about dp. Instead of that tried some greedy.

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

      Could you please elaborate what dp[i][j][k] equals to? Regarding j, suppose we iterate through 1...i and 1...k, from dp[i'][j-1][k'] we find the next position which is the jth character of religion 2. But how do we assure that this position hasn't been occupied by religion 1 or religion 3 under the setting dp[i'][j-1][k']

      Never mind, I got it.

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

Nice typing speed test

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

Some unbalanced Div2.

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

How to solve Div 1 C :(

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

I’m not a writer, not a tester and I agree that the round was misbalanced. Surprisingly, in the Div. 1 the balance is admissible, but in the second division it is no good. Really, we need more testers from Div. 2. Last time we had so many excellent rating rounds for Div.2 and Div. 3 that I think there is no tragedy today. You see, sometimes it is really difficult to estimate the difficulty. It is a special skill; it is a science to think like others. In a narrow circle of coordinators every time we discuss such incidents and try to make conclusions.

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

    We all are with you.

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

    What's the way to be a tester for Div2 ?

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

    I think that before the round all type of colors should test it ;

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

    2250 looks fair enough, but it would be great to have something to solve in between C and D

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

    I feel people with various ratings should test the problems so as to get an idea on the difficulty. For someone with such high rating, it is obvious for him to feel D easy, hence we should not be blaming the setter. Hence the difficulty thing can only be solved if it is tested by the corresponding color.

    P:S- Just an opinion

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

    The idea of making Div2C = Div1A did wonders when the Div1 cutoff was 1700 — the average skill of Div1 was much lower back then, so it's OK for Div1B to be easy. Right now it's very hard to set a balanced problemset for both divisions this way. The last 5+ Div1+Div2 rounds had either (or both) of them consist of 6 problems, so that the average blue will solve 3-4.

    This round's Div1B was not imbalanced, it's just that Div2 people are too used to have 6 problems, therefore Div1B is supposed to be Div2E. I think it'd be better to just make every Div2 contests have 6 problems, and share 3 problems with Div1 (or even 2, hardly anyone solves Div1C anyway).

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

    In my opinion, the score gap between two problems should be bigger when the score itself is bigger.

    For example, having 500 — 1250 difficulties isn't same as having 1500 — 2250. It doesn't take too much time for a 2250 problem become around 1500 points, while a 1250 problem never becomes less than 500 (unless someone makes a lot of WA submissions). So if one thinks that D1A — D1B should be 500 — 1250, it's likely that D2C — D2D would be more appropriate for 1500 — 3000 or something. With this perspective, we're definitely missing one or two problems between them.

    Also the reason the number of people solved D1A — D1B looks balanced is just because most people in Div. 1 should be good enough to solve 4 problems for Div. 2, and it rather seems that D1B was quite hard for this round because only around half of people in Div. 1 could solve B, which means the other half would've solved only 3 problems if they were Div. 2.

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

    I looking forward to your Div.2 and Div.3.

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

So many people solved the problem B, but others including me and some strong coders couldn't solve it. What important points are we missing?

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

    You are missing a wall.

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

    Let $$$dp(i, j, k)$$$ be shortest prefix of long string such that it contains prefixes of lengths $$$i, j, k$$$ of three strings as disjoint subsequences. $$$dp(i, j, k)$$$ can be easily calculated through $$$dp(i - 1, j, k), dp(i, j - 1, k), dp(i, j, k - 1)$$$ by taking prefix of length $$$dp(i - 1, j, k)$$$ and finding first character after prefix in the long string that is equal to $$$i$$$-th character of first short string. So in each query you have to calculate up to $$$250 \cdot 250$$$ states of dp. I came up with this solution quite quickly but had hard time coding and debugging, so I'm really curious how could someone come up with the solution and code it in around 15 minutes.

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

    Let DP[a][b][c] indicate the shortest prefix of the string we can use to have prefixes of lengths a, b and c from the religions as distinct substrings of it. The DP is trivial to update with DP[a][b][c] = min(DP[a][b][c], next_occ(religion_a[a-1], DP[a-1][b][c])), and similarly for b and c. The DP takes 250^3 memory which fits.

    If we calculate the DP again at every step, we use 250^3 * 1000 time which is too much, but notably the only states that change are those where the last character of the changing string appears (so if we add a character to the end of religion a, then only DP states of the form DP[len(religion_a)][b][c] change), and therefore we only have to do 250^2 work every update. 250^2 * 1000 is fast enough.

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

      Thanks. I missed the sentence "You can assume that no religion will have description longer than 250 characters."

      What the stupid man I am.

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

        Yeah man it'd be much better if there was a notification about this sentence.

        Oh, wait...

        UPD: ok, I switched the language to see what this notification looked like in english. Seems to be a hint for russians lol

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

        Actually this is important only for ML. We solve one query in time proportional to product of lengths of two different strings. Let's assume that we only append symbols, it is easy to show that it is worse for execution time. Then we have numbers A, B, C; one operation does something like A++, TIME += B * C. One can prove by induction that after all operations TIME = A * B * C (cool way is to think about it as building cuboid layer by layer). So, max TIME is $$$(q/3)^3$$$ which is OK.

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

          That's nice. So if it hadn't contained such constraints, it would have been much harder although the essential idea was the same. The conclusion is that I should have solved this problem whether or not I noticed this sentence. Sad

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

            I don't think it would be much harder. You would just need to allocate array with dimensions dp[A][B][C] instead of dp[1000][1000][1000]. You can set A, B and C as number of commands regarding first, second and thrid religion respectively. I wouldn't call that "much harder", but just tedious.

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

              Yes, implementation is tedious, I just thought the value "250" made us easier to come up with the solution because when we see the suspicious value 250, we are always likely to start first thinking about constructing 250*250*250 array(dp) . The solution becomes more explicit.

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

Is D really difficult? Someone please show me how to solve it

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

    It's solved with a somewhat simple DP, but the implementation is kinda hard.

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

Very bad distribution of problems!!

There's a very big gap in difficulty between C and D. B,C are very easy compared with other B,C problems, and D,E are very hard compared with other D,E problems!!

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

    D is easy in my opinion

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

      Then why didn't you solve it :)

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

        I think it's easy doesn't mean i have to solve it. You know what is the different between you and me? You and I both didn't solve D, but instead of whining, i choose to do positive thing.

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

Balanced contest, thank you

a

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

    If you look at the Div1 contest though, 50% of the people who solved Div2 C also solved Div2 D. So I would think the problems themselves weren't that imbalanced.

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

      That's an interesting point. The probability $$$P(D|C)$$$ (where $$$C$$$ is condition where you solve Div2C, and $$$D$$$ for Div2D) greatly differs depending on one's coding ability.

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

      But We Aren't Div 1 :/

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

What is the approach to solve Div 2 c?

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

    You spend 2 first, if you dont get prime using 1.

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

    One can see that if the number of twos is 0 or the number of ones is 0 we know the answer. Else, we have at least one of both. Then we use 2 at the first position and 1 at the second. Then just use all the Twos and then all the ones, cause all the primes greater then 3 are odd, so we use 2 to reach them!

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

    put 2 1 at fisrt. and then put all 2. at last put all 1.

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

In div1D, can we do this:

  1. Find all components connected by cheap edges.
  2. Do dijkstra, with a mask indicating which components you have visited. You can't visit the same component multiple times, and cannot take an expensive edge from a component to itself.

This is too slow, but we can just not store components with size 3 or less in the mask, since an optimal path will never visit these components more than once. There are at most 17 components with size 4 or more, and 70 * 2^17 is small enough (9175040).

I did this but got WA at pretest 8 (53527044), rip rating QAQ

EDIT: I think I found the issue. I used indexes of nodes as indexes in one array, but should have used indexes of comps of nodes instead :(

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

    Try this test:

    test case

    If you don't store components of size 3, you'll say that the distance from 1 to 3 is 7. You have to make sure that if you're in a size 3 component that you don't go from one node in that component to another in the same component. I only ignored components of size 1 and 2 and got pretests passed.

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

      But if you take components of size 3 to account, then the mask has maximum size 2^23, and 70 * 2^23 ~ 5e8 doesn't fit in memory. How do you handle that?

      That test case works for me since I disallow taking expensive edges inside components. So the bug is somewhere else :/

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

      Good catch. So you don't do bitsets for components of size 3, but you remove the long edges within them.

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

      No need to keep that information about a-components of size 3 in mask. We need to just exclude possibility of using b-edge when going within one a-component, which is a simple if.

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

Didn't mean to offend。DIV2 is really boring.

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

So interesting that in Div1, ~50% of people who solved Div2 C, also solved Div2 D.

But in Div2, only 1% of the people who solved Div2 C also solved Div2 D.

The only way I can explain this is that many people in Div2 saw the numbers and overestimated the difficulty of D. And, being discouraged, they didn't think about the problem hard enough.

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

    I think I disagree with you. Div2C was easier than average, so most if not all Div1 coders solved it. However, Div2D was harder than average Div2D and it's almost Master level (Master and higher > 50% of Div1). So most CM and lower weren't able to solve it.

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

    50% of Div1 people who would have solved Div2 A also solved Div2 D.

    But in Div2, only 1% of the people who solved Div2 A also solved Div2 D.

    The only way I can explain this is that many people in Div2 saw the numbers and overestimated the difficulty of D. And, being discouraged, they didn't think about the problem hard enough.

    Can you point out logical flaw here?

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

      I had that feeling :D

      But the difference is I saw the number of participants to solve it in the DIV. 1 contest thats why I solved it in the end

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

    you are right .I even ignore the problem D and start hack work. I think it is necessary to review D again.

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

What was the hack case for Div2A?

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

    When the cheapest buying price is greater than the most expensive selling price, there's no way to make profit and you shouldn't do anything at all.

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

      that's not a hack

      it was the second sample

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

        Sorry, my bad — in this case, I don't know how to write a hackable solution (unless I have, which would be unfortunate).

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

    Someone use n instead of m incorrectly. They will fail on this case:

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

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

come on , system testing !

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

Extremely unbalanced round. Jump from Div 2 C to D was too great. Now my rating's going to unnecesarily drop :(

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

Especially since I have an extra log factor on B and I'm not sure whether it will pass or not.

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

Div2 B is the same as 389B

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

Oh my god! I realized that Div1.C is not that hard(I think it can be solved with segment tree to solve the maximum value of intervals) after I has given up for 30 min... and the contest was nearly to be over... Anyway, it's a nice problem!

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

Well anyway, R.I.P rating.

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

Can anyone tell me the meaning of "disjoint subsequence".

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

    Subsequences with no common elements.

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

People often point out weak tests, so let me do the opposite. I tried various heuristics in div1D and couldn't pass, so kudos to mnbvmar for strong tests.

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

What is wrong output format Unexpected end of file - int32 expected error. I got this error in C and once before as well.

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

    Possibly because for some reasons you printed less integers/tokens than required.

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

      My logic was: First store prime numbers upto 4e5 using Sieve, then iterate over all the prime numbers and take its difference with the previous prime number say dif and check if the difference is odd then try to form dif one 1 and dif/2 2's, if not possible then use all remaining 2's and required number of 1's. If difference is even then try to form dif using 2's only, if not possible then use all 2's and required 1's. For some cases like where count[1]==0, or count[2]==0, or the difference b/w current prime and previous is greater than 2*count[2] + count[1], then use them in any order. Is there any problem in the logic. Link to the code.

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

Congratulations C137

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

So this round didn't skip the users who break the rules?

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

I used https://ideone.com/ to code problem C but I forgot to change it to private and maybe somebody had seen my code and summit it. My code link: https://ideone.com/AIe2YT .

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

This contest kinda goes to show you the problem with having the contest split into two divisions: people from Div2 had higher rating changes than those from Div1 for the same solved problems.

Solving C and D in an hour in the Div2 contest would put you in top 5 and shoot you dirrectly from blue to orange. But solving the same problems them in an hour in Div1 contests only puts you 200-ish, which means purple, maybe low master.

In other words, someone with 1899 solving C and D in an hour would get like +250 rating, but someone with 1900 solving the same problems would only get something like +100. A difference of +150 delta just because of 1 starting rating point.

This situation seems ridiculous to me. In my opinion, if there are going to be shared problems, it"s much better to merge the two contests in a "Rated for everyone" contest. Sure, Div1 people would have to solve two extra "easy" problems, but in general this won't take them more than 10 mimutes.

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

    Isn't what you're describing just a symptom of an unbalanced div2 though? Isn't the core problem the unbalanced div2, not some kind of fundamental flaw in the rating system?

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

    Isn’t the “different rating change for solving the same problems” imbalance present in all rounds where Div1/2 are split? I don’t think it’s unique to this contest.

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

      Yes, that was my point. It's a fundamental problem of split rounds. I was arguing it would be better to always have merged rounds instead.

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

    Shared problems between divisions is not the fundamental issue. Imagine that problems C and D in Div 2 were replaced with new questions of the same difficulty levels. The issue you are describing persists: two nearly identical contestants with ratings 1899 and 1900 can perform similarly on an individual level but earn very different ranks and rating changes.

    I'm not sure it's a big problem, though. There are many factors producing noise in outcomes from any single contest, and it's not like there's any special advantage to entering Div 1 with rating 2149 rather than 2000. In the long run both contestants' ratings should converge appropriately if they are of the same skill level.

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

as for me — really good round (ez Expert:) )

→ Reply