On Sep/20/2018 17:45 (Moscow time) Educational Codeforces Round 51 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Ivan BledDest Androsov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space University is proud to announce new partnerships for this year’s Hello Barcelona Programming Bootcamp — VTB and Indeed Tokyo, with the addition of team sponsors Phaze Ventures and Spark Labs.

VTB, the largest international bank based in Eastern Europe, continues to be an official partner of our Hello Programming Bootcamp series, adding further quality to the 3rd edition of the Hello Barcelona Programming Bootcamp by bringing their own participants, as well as by supporting top teams from around the world.

Indeed Tokyo is Japan’s branch of the #1 employment website in the world, giving job seekers free access to millions of jobs from thousands of company websites and job boards. As they sponsor for the second year in a row, Indeed continues to offer the best job opportunities to the boot camp participants as they gather in Barcelona from September 26 to October 4, 2018.

**UPD:** There was a bug in testset and validator for problem F, we are currently fixing the issue. The statement included the correct resrictions. We will rejudge all the solutions as soon as possible. The round can become unrated, we are discussing this at the moment.

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | kmjp | 6 | 210 |

2 | MrDindows | 6 | 223 |

3 | elykuil | 6 | 242 |

4 | Nisiyama_Suzune | 6 | 274 |

5 | Fekete | 6 | 274 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | halyavin | 299:-14 |

2 | Laggy | 100:-10 |

3 | greencis | 29:-2 |

4 | Volkov_Ivan | 19 |

5 | dorijanlendvaj | 13 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | traxex | 0:03 |

B | answhldkd | 0:02 |

C | ainta | 0:06 |

D | greencis | 0:07 |

E | tfg | 0:38 |

F | baggins | 0:26 |

G | yasugongshang | 0:56 |

**UPD2:** We investigated the issue to get the following results. 10 people were noticeably affected (that took them more than 3 minutes of the working time). Round will surely be rated for other participants. As for the affected participants, we will look into the rating changes and revert them in case they are negative (set the participant into the unofficial participation mode).

**UPD3:** Editorial is out

Wish you all +100 rating!!!

because you 1501 and wanna be

ExpertThat's only a difference of 99 rating though

yes, mathematically this is 1601. but asymptotically this is

O(expert)hahaha Wish you all +100 rating

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).thanks codeforces for three contest in a row.also waiting for a div-3 contest.

Hope next div.3 will be soon :) Now I'm too busy with the studying and other activities but I'm trying to prepare it as soon as possible

happy to hear this and waiting for it.

I really need to say the amount and the quality of contests you prepare are interesting, although not each contest you prepare is perfect, but the overall desirable quality is stable, I don't know how difficult it is to prepare a contest, but I bet it is not easy at all, sometimes I notice that you give attention to negative feedback, when you should only consider the constructive one, try to avoid that, every active contestant in codeforces realizes the amount of effort and creativity you offer to the community

I haven't been able to do a contest in a while... all contests are either morning/noon on weekday or early morning on weekends (I live in US).

Me too. Unfortunately it seems early morning weekends is the only option.

Short statement and strong pretest plz.

no way

Instead of that I would ask for balanced problem-set. You know what happened in last few Educational rounds.

Pretests will indeed be strong. They will be

as strong as System Test...Every one knows how to solve

Dexcept me.I struggled a lot with brute force and DSU, trying to find smoe formula. I even put the results in OEIS to see if it matched some known sequence. Then, when all failed and Ernesta was looking at me like "what are you doing, gaucho?", I realized it was solvable with DP.

Same as you! However when I realize it could be solved with DP, I have no enough time.

Is it rated for Div. 3??

No :)

This round will be

rated for the participants with rating lower than 2100.What this means ?

Me too. I don't understand it!

It means that if your rating is <2100, then after participation it will change.

If Div.3 participants have rating which is

less than zeroand their rating is`unsigned short int`

, then it is indeed unrated for the.How about (unsigned short int)-65532?

Imagine having a rating this low. You literally had to put effort into it.

Well, check this guy out: .o.

this appears to be done deliberately

Yeah, that's my point. Effort made (yet perhaps he lost his patience too soon :D )

WTF

I have not competed in a contest in a long time. I think last time was before my sweet cow "Ernesta" gave birth to tiny and soft brown and white "Vaquita linda".

Now I'll leave the barn for a while and try to have a little fun with this contest. Or maybe I'll take my laptop to the field, and use the sheeps and cows as inspiration while I write code under the sun, gazing at the sunflowers and listening to the little singing birds.

Viva Argentina! Poder gaucho FTW!

Don't know how much truth is there in whatever you wrote but if it is true then it is friggin' awesome.

4 consecutive contests what a great week

Delay :(

How much is your RPS? (reload per second) ;D

You don't need a reload. The pop-up that informs you that the round has started won't show up if the contest was delayed.

10-minute delay. -_-

after this week my rating will be lower than ever.

D — Delay P — Problem

DP

delay in Education rounds is no more a surprise for me, It has become a trend.

Delay is for registering for next contest.

I am staying at office late to take part in the contest and it just got delayed -_- . Now I may have to miss it :(

It sucks.

is it rated?

I guess so!

Problem A was unexpectedly too much implementation based :(

I wasted time, thinking that there must be a simple and elegant solution. But I was wrong :(

i started with A but then noticed B was getting more submissions.but i got late for D

It seems to me that you can always find the answer by only looking at the first 3 characters, once you know the count of characters of each type in the string. Maybe that is a little more elegant than the solution you found?

This is my solution of A 43153166, I don't know if this is too much implementation for A.

when you finish doable problems 25 minutes before and keep on refreshing the page to see your rank falling :(

my mind just goes back to "candidate master in next contest"

It's so similar to "agla sem phod denge"(I will rock the next semester)

yeah

Is this rated!

How to solve F?

Delete a tree from the graph. You are left with a graph of at most 42 nodes. You can use distance pre-processing on the tree (lca) and on the remaining graph (floyd-warshall) to answer the queries.

For more details: http://codeforces.com/contest/1051/submission/43144878

Cut the given graph down to any spanning tree. There will be at most ~20 spare edges, you can calculate distance between any two nodes in O(log n) if you drop these spare edges out and consider only spanning tree.

Now we will have to consider edges that we dropped out. Let G be complete graph where edge (U,V) is minimum of the path between U and V in the spanning tree and the length of spare edge between (U,V) if it exists. G contains only nodes from the initial graph which have at least one spare edge attached to it, so G is not larger than ~40 nodes. Let's calculate the shortest path between any two nodes in G (e.g. using Floyd algo).

Ok, now for each query we just take the spanning tree path length between U and V as the initial answer and try to make it better by choosing every two vertices U', V' from G and taking spanning tree paths U-U' and V'-V plus G path U'-V'.

Wtf is wrong with you guys? The above explanation is detailed and perfectly fine, why downvotes?

People downvoted the post because they assumed the downvotes meant the explanation was wrong, without bothering to actually read it. Or perhaps they read it and the downvotes subconsciously made them think it's wrong. A vicious cycle.

Perhaps a bit of asch conformity

I think it's easier to think about it this way:

Let

Tbe any spanning tree of the graph,Sbe the set of edges in the original graph but not inT, andVbe the set of vertices inS. Note |V| ≤ 42. Then any path that is not entirely in the tree must pass through at least one vertex inV. So the answer for a query (u,v) ismin((dist(u,v) in the tree), (dist(w,u) +dist(w,v))) over allwinV. So you can run a Dijkstra from all suchwand compute the answers this way.this is more clear explanation ,but isn't it dijkstra instead of bfs.

Damn man, what was the pretest 6 in C ;_;

Maybe something like:

What was no 7??

Maybe you mishandled something. I haven't experienced test 7.

Is there anyone who got WA in test case 7?? upd: found my mistake. :(

Ohh looks like yes. Is answer: YES AAABA

Yup.

it can be something like 1 2 3 4 5 6 6

A huge skill gap between D and E/F :(

Don't see that much of a gap between D and E, however E is really tricky in implementation

I think A was harder than B/C/D.

not harder than D

I disagree. Spent 45mins on A, 40 mins on D.

So work hard on your implementation bro. ;D

I wasted 30 minutes trying to utilize my A's answer and thinking about what de hell I had done wrong.

swap(A, B);

more like B < D < C < A

What's test 4 in E?

try this: 101 0 101

Answer 3? Then works.

Fuck! I wrote

instead of

The difference is not immediately obvious. :'(

Can someone point out the mistake in this dp implementation for problem D ? http://codeforces.com/contest/1051/submission/43148059

Please check this when previous column layer is BW or WB then adding BB or WW in current column doesn't change number of components

i did check that and that is incorporated in the solution . l=0 implies WW l=1 implies BW l=2 implies WB and l=3 implies BB if you go through the code.

You are not doing transition f(i,0,k) from f(i-1,1,k) and f(i-1, 2,k). Similarly you are missing many transitions for each case

Got my mistake

Expected solution for C ? I used some DP .

It's pure implementation , there's no need for a dp!

Isn't C's problem statement confusing? I initially interpreted that nice numbers are only on the basis of the multiset s, not a and b.

Yes. The English problem statement is incorrect.

To quote: "Vasya has a multiset s consisting of n integer numbers. Vasya calls some number x nice if it appears in the multiset exactly once."

When you type "the multiset", it refers to some specific multiset (the one mentioned). If you were to write "a multiset", it could refer to some other multiset as well. The problem statement was unambiguous regarding which multiset is used to define which numbers are nice: "the multiset" s given in the problem statement.

Pretty annoying to spend 20 minutes of competition time just trying to figure out what kind of error was left in the problem statement.

What is wrong with 43149226 for C?

But you can ignore that number and add it all to one of the two sets if if exists more than once which won't be nice.

Got the problem. Thanks man.

The problem statement is misleading, what they mean is that can you partition the multiset into A and B so that No. of nice elements w.r.t A in A= no. of nice elements w.r.t B in B Not

no. of nice elements w.r.t S in A= no. of nice elements w.r.t S in B

Yes I understood it right. Though WA.

Everyone must be so afraid of halyavin right now XD

Already 285 successful hacks have been done

In problem F,the statement says m<=100000. However,in test 11, m > 100005.

yes, i was thinking something like this must have happened. was getting WA in the contest.

i had kept my array size as 1e5 + 5.

For problem B the solution always exists ?

Yes, it's truth.

split them like 1 2, 3 4, ..., i i+1

and gcd(i, i+1) is always 1

Yes

I think that there is an invalid test case in Problem F. It appears that the test case 11 has

M> 100000.TLE Code: 43149555

AC Code: 43144968

F,the data is wrong, since I get RE if I set MX=1e5+5, and get AC when I set MX=2e5+5

AC Code: 43149185 the test case 11 has M = 100020

Lol, F's constraint is 1 ≤

n,m≤ 10^{5}, but in test case 11,m= 10^{5}+ 20.How does hacking a solution affect the scoreboard of the hacker in educational rounds?

it doesn't affect)

how to solve D and why :P? because I didn't know what to think

You can use dynamic programming.

`dp[i][j][k]`

equals to the number of ways to coloricolumns, the last column has the statejand the total component count is exactlyk.The state is 0 if both cells are white, 1 for white upper cell and black lower cell, 2 for black upper cell and white lower cell, 3 for both black cells.

Base case:

`dp[1][0][1] = dp[1][1][2] = dp[1][2][2] = dp[1][3][1] = 1`

.You don't need to consider 4 cases, dp[i][0][j] = dp[i][3][j], and dp[i][1][j] = dp[i][2][j],

you can just consider if last elements are of same color, or different

I think I did same, but can you please tell what's wrong this submssion 43147897?

Integer overflow.

Each operation can caused your dp value to reach , which exceeds the upper bound of 32-bit signed integers (i.e. 2

^{31}- 1).Thank you for reply.

thx really good explanation and in few words

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Is validator fixed now?

How people will be affected if test cases are corrected? (In case it is fixed.)

Considering that 116 people got AC during the contest, RE(?) and WA(?).

If no of people <50 then we can probably ask those people do you want an unrated contest for you?

And it can be kept rated for others?

Validator is fixed and all the tests are also fine. The other questions are still in discussion.

If the effect of the invalid test in F is not significantly high on new rankings, please try not to make the round unrated!

I think there is something wrong with CF-Predictor. halyavin got rank 839 and it predicted that he get +65.

UPD: Actually, he got rank 835.

halyavin rank 839...are we in the real world or tron has taken over

It is rated for div 2 only, so halyavin doesn't effected

I had a meeting at work and had to start half an hour later.

Please hack as code as possible..

Also think so, CF-prediction for being #329 in Div2 was +123 while I got +15 which is about right.

http://codeforces.com/contest/1051/submission/43144963

What's wrong with my C?

It fails on Test 7

If the issue with F can be solved, please do not make this round unrated. It'll be very disappointing.

it cannot be. how can you "solve" something like this. constraints say m <= 1e5. test case has m = 1e5 + 20

remove/modify the test and reevaluate

but time wasted is time wasted right. in my case, i got AC after changing the size of array.

So did I.

Lol. all my submissions for F ACed after the test case change. It will be highly unfair keeping this contest rated (for me). My first submission for F was at 00:46. I wasted time till 01:40 on it.

That does make sense.

How to solve problem E?

Let dp[i] be the total number of ways to partition the suffix of a starting at i. And let dp[n]=1 (n is the last character index+1). To calculate dp[i], you need to know the smallest index i' (i'>=i) such that the sub-string a[i, i+1, ..., i'] forms a number >= l, and you need to know the largest index i'' (i''>=i) such that the sub-string a[i, i+1, ..., i''] forms a number <= r. dp[i] will be dp[i'+1]+dp[i'+2]+...+dp[i''+1]. To find i' and i'', you need an algorithm which finds for every i the longest prefix starting at i which is also a prefix of l, and the longest prefix starting at i which is also a prefix of r (Z algorithm does this in linear time). And to sum the dp values, you can use cumulative sum on dp as you are calculating it. There is a bunch of corner cases that need to be handled of course.

the number of people who solved F isn't high enough to make the round unrated

But some participants wasted time on F...They may got higher ratings if there was no problem

i think it's kind of trade off, anyway my solution on E probably will fail so i am not talking because of me

I think if they got RE verdict on test with high order likes 11th, then they could realize that they should change their constraint.

And i think it was better to waste time on F instead of E or G.

Can you make the round unrated for only people affected?

Problem F had the same idea as this problem, but with a slightly tricky implementation.

I know it's not fair to make it rated for the participants who wasted time on f but it's also not fair to make it unrated for all the other participants ...

If this gets unrated, it will be the first unrated educational round [rated for div2]

If this round will be unrated.It will be better for those people who have at least one submission of problem F but not for all please, since the issue created with only problem F. Thanks.

In problem F, if the condition m-n<=20 doesnt exist, how to solve it ?

Run floyd warshal or dijkstra for each pair or dijkstra on every query. There is no fast solution without that condition.

Maybe some A* or some probabilistic stuff — no idea how that works in practice.

Sorry for the F, but hope this contest will be rated...

How to solve G?

if doesn't exist any i,j(i!=j) such that a_i=a_j or a_i=a_j+1

then obviously we can't do any operations and they are pairwise different

so the answer is 0

and now consider we got a new (x,y)

lets look at the 2 conditions below:

(1) lets say that there exists a_i+1=x and b_i<y, we should apply operation(2) to x and apply operation(1) to a_i so that we can add b_i-y(which is a negative value) to our answer

(2) if there exists a_i=x, then we must apply operation(1) to one of them to make it pairwise different, and obviously, we should apply the operation to the one with smaller b

after we have done our operations, we should get something like (a_i,b_i1),(a_i+1,b_i2),(a_i+2,b_i3)....

be aware that these b are sorted so that b_i1>b_i2>b_i3 ...

To conclusion, let consider we get (a_i,b_i1),(a_i+1,b_i2),(a_i+2,b_i3)...(a_i+m-1,b_im) ,(a_j,b_j1),(a_j+1,b_j2)...(a_j+k-1,b_jk) (a_j>a_i+m-1+1)

if we get a new (x,y) that a_i<=x<=a_i+m, we should rearrange the them so that we get a new sequence (a_i,b_i1),(a_i+1,b_i2)...(a_i+m,b_i(m+1))

and if a_i+m+1=a_j

we should merge the two((a_i,b_i)... and (a_j,b-j)...) into one((a_i,b_i)...)

we could do this by using a BST and Heuristic merge in O(Nlog(N)log(N))

sorry for the bad explanation, you can check my code if you need

I had found the same solution during the contest but didn't have enough time to write the bst from scratch, I wish we had a way to use std::set for the same job.

http://codeforces.com/profile/answhldkd this account is pretty obviously a team account. look at his submissions. ( http://codeforces.com/submissions/answhldkd ) You can recognize easly that coding style of B, D, F is simillar, but for F, A, C they are very different.

Not the first time that North Koreans are cheating https://codeforces.com/blog/entry/14150

Problem F is similar with http://codeforces.com/gym/101808/problem/K which I have done 2 weeks ago. But my biggest mistake is tried to solve D before F. After contest, read F and say: OMFG!

It is not similar, in task you mentioned, there is a solution just using lca, so you need there just to code simple lca (nlog(n), log(n)), here you should code something harder, but of course they have some similar part

For us, the game started very late, we stayed up late to the early hours, so I hope this game should rated.

+205 xd

No, no, no, I am talking about the actual situation.

Hope the contest will be rated. Few people were affected by issue in F, it could be unrated only for these people

I don't remember the time, when the contest was rated for everybody except some people, because of mistakes in some problems, so in my opinion, contest would be rated for everybody, or unrated

Is it rated??

Rated!

Is the contest made unrated?

hope final testing will starting soon.its truly boring waiting a long time for testing.

they are fixing test cases for problem F, which are incorrect

is this contest rated or unrated ? for one test case in problem F round shouldn't be unrated problem F must be deleted or round became unrated for people who have solved problem F

Or maybe codeforces should first make you expert and then think about what would be the best in everyone's interests?

Longest discussions ever...

1.politics

2.arms deals

3.educational round 51 rated or not

The System Test has started!

I open Codeforces about 20 times for the result of the discussing

and check the announcement said "are discussing" or "will discuss"

this is truly awkward ,if only for problem (F) this round will become unrated.

It's not about the problem but about the number of people affected and the consequences of that issue.

is they came final decition?

why do these issues occur only when I do well in a contest ?!!!

I think there aren't lots of people affected by issue in problem F, because number of people that solved it didn't change much after rejudge, so I think it's better to make unrated only for them(If they want that ofc).

Maybe we can make the round unrated for those people affected.

Seriously, just only for few people its going to be unrated for all users? Its very unexpected from CF . Very sad. I cant believe it.

Upsolved problem

Awith adding "type" symbols after every char, which let me use backreference in regex. Solution with Perl: 43170240Spoiler/explanationAppend every char of charclasses with e.g. punctuations:

`[a-z] -> ,`

,`[A-Z] -> ;`

,`[0-9] -> !`

, they are "not word char-class"`\W`

in regex. Backreference`\1`

is to the first capturing parentheses/group`(\W)`

.`\K`

means to change only following matched substr. While some kind of punctuation is absent, insert it (with appropriate alnum) into the place matched by backref.Is it rated or unrated? Not determined yet?

I don't know how it is going. I just hope this round would be rated. :)

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).If it's unrated, it would be very sad :( I will lost the chance to become CM.

Congratulations For CM！

Thanks! I was very happy when I know the contest is rated.

Me too！Wish you another +100

Congratulations for CM!

So it is rated now? Nice.

Thanks a lot CF. Finally its going to be rated. Feeling really happy now. Again Thanks a lot.

Rated For Not Affected！ That's Really a Nice Decision

List of top hackers?

In problem A, any particular reason for not allowing T > 1 during hacking phase? Actually these 43147222 , 43149770 solutions will fail on test cases such as : http://codeforces.com/contest/1051/hacks/489717/test

By the way, they are exactly same submissions by different users but in different languages.

Our reasoning was that the other way around the whole list of 100 tricky cases might have been collected in a single file in order to abuse to hacking process.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Why does Bottom Up take much less time than top down with memoization??

In regards to 1051D - Bicolorings and following submissions:

Top Down: 43169291

Bottom Up: 43175270

Is it due to Hashing?

I have a question:

In problem F 1051F - The Shortest Statement ,it says m-n<=20,so it will be at most 21 Edges are not used after building a tree, so if every edge's u and v are different it will have at most 42 points.

I take these points out and run dijkstra to get these points to every points' shortest-path. but I only define a array dis[41][maxn], and I saved id start from 0.

I think it should get RE during system test. Why it got AC? If I use assert in my code, it got RE on test 6. I don't understand why really. (sorry for my poor English. :P)

Here's my code.43141017

use assert.43177498

Program may use some static memory that goes after your array

`dis`

. It may be free memory of memory of some other array. There are good chances that such UB will not lead to Runtime Error. You was lucky.Thanks for your explanation.

But After array

`dis`

it only follows an array`len`

which is used in the query and means points' distance on tree, if it will be changed by`dis[41]`

, then why the answer is correct? Maybe I'm too lucky. :PIn your code you have an array

`len`

after`dis`

, but in the memory they may be in any order.Oh, I understand. Thanks.

Where is editorial?

why no editorial even after 12 hours?

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).