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 _kun_, V--gLaSsH0ldEr593--V 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:*

*Div 2:*

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 | Nazarbek_Baltabaev | ||

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 | ||

Vn_nV | 83:10 | Election Promises |

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

you'll be nutella soon :p

he (she) won't

you'll be Blue soon numb!

for you i am Mr. Master

green is the new blue

## #inZashikhinWeTrust.

users with rating <1900 should be disallowed from downvoting comments

ur not right

good avatar

Thank you!

Alicization is epic.

yes

I downvoted that comment of yours !

also users with rating >= 1900 should be disallowed from upvoting comments

users with rating <1900 should be disallowed from downvoting comments ×

you should stop writing such comments ○

I think, users with rating < 3K should be disallowed from downvoting comments. And upvoting. And writing comments.

I'll become such a Mr. Master soon too :(

Will mere mortals survive this?

It is will be a great round)

is it rated ?yeah

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

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.

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

Even the strongest of rounds always has a weakness.

Finaly an announcement without copy pasted part!

It is better for me.

lol then you're not that random guy I wish

LOL no 2.Then I wish You also.

True, man xD.

it will be interesting problemset :)

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

YAY! mnbvmar gets his time to shine!

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

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.

It's already mentioned that there will be 5 problems

I think he meant 8 different problems inclusive of both div1 and div2 problems

You're right

This is awesome blog, according to that contest will be better

"Please, read all the problems!"

Does this mean that problems won't be sorted by difficulty?

No.

Maradona > Messi

Mbappe << Messi

what about Ronaldo and Messi? :thinking:

Messi = 0 => Mbappe left shift Messi = Mbappe

Stop, that was a mistake)

"The round will be rated for both divisions. (At least that's what I've been told!)":)Very Sad after not seeing Radewoosh in top 10. Hope he will come back...

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

It's my first time to div.1

and is it rated?

Yes

Chekaden gudako!mnbvnmar

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

Is it going to be hard?

The Immortal Nutellian's Round !Problem-set might be interesting !

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

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

it's me. I don't know problem D div2, E too. so sad

Never expected such an unbalanced round from red coders.

I always expect such an unbalanced round from red coders.

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

is it speed test for div2??

Reds:

'You can't improve simply solving Div2As'

Also reds:

Sets contest with 3 Div2As and two Div1 problemsToo true. Hopefully I can recover my rating in next contest.

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.

The ones who could solve it were busy doing Div1

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

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)

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 ._.

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

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

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

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.

Nice typing speed test

Some unbalanced Div2.

How to solve Div 1 C :(

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.

We all are with you.

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

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

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

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

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).

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.

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

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?

You are missing a wall.

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.

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.Thanks. I missed the sentence "You can assume that no religion will have description longer than 250 characters."

What the stupid man I am.

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 lolActually 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.

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

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.

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.

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

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

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!!

D is easy in my opinion

Then why didn't you solve 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.

Balanced contest, thank you

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.

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.

But We Aren't Div 1 :/

What is the approach to solve Div 2 c?

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

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!

Then check primes using sieve of eratosthenes?

No need to check since we know all primes other than 2 are odd.

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

In div1D, can we do this:

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 :(

Try this test:

test case3 3 6 7 1 2 6 2 3 6 1 3 7

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.

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 :/

I use a hash table.

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

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.

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

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.

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.

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?

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

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

What was the hack case for Div2A?

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.

that's not a hack

it was the second sample

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

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

Yea, I am that man.

It's my first time to take part in this kind of competition. Wow, it's so exciting and the time, for me, was not enough at all!!

come on , system testing !

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

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

Div2 B is the same as 389B

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!

Well anyway, R.I.P rating.

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

Subsequences with no common elements.

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.

What is

`wrong output format Unexpected end of file - int32 expected`

error. I got this error in C and once before as well.Possibly because for some reasons you printed less integers/tokens than required.

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.Really problems are awesome to solve for getting a high ranking. Though I haven't got as expected. Thanks to problem setters for this spicy contest.

Congratulations C137

Thanks :D

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

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 .

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.

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?

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.

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.

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.

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