Hello, Codeforces!

On June 27, 17:35 MSK Educational Codeforces Round 46 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.

As usual, the round will be **rated for the participants with rating lower than 2100**. It will be held on extented ACM ICPC rules. 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 prepared by Adilbek adedalic Dalabaev, Roman Ajosteen Glazov, Mikhail PikMike Piklyaev and me.

Good luck to all participants!

UPD. The editorial is here.

I also have a message from our partner, Harbour.Space University:

Hi Codeforces!

For our programming boot camp’s next iteration of Hello Barcelona Programming Bootcamp, Harbour.Space University in collaboration with Moscow Workshops ICPC, ITMO University, Moscow Institute of Physics and Technology, Saint Petersburg State University and Codeforces is bringing the best training practices and coaches to Barcelona to prepare 150 students for winning medals in the next **ICPC World Finals**.

It's extraordinary to see the entire cultural spectrum meet at the boot camp over a common love of programming and learning, and this autumn, we will be doing it again.

Our boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

Expect the most challenging problems, surprise guests and speakers, a branded hackathon, and finally the online round held on Codeforces, so everyone can join the onsite participants, at the finale of the event.

During the nine days of the event **from Sept 26 to Oct 4, 2018 in Barcelona**, teams will be participating in practice contests, problem discussion sessions and lectures.

**Learn more about Barcelona ICPC Bootcamp**

You can ask any questions by email: hello@harbour.space

UPD: The contest is over.

Congratulations to the winners:

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

1 | Farhod_Farmon | 7 | 353 |

2 | MrDindows | 7 | 362 |

3 | tzuyu_chou | 6 | 205 |

4 | Wild_Hamster | 6 | 248 |

5 | spj_29 | 6 | 252 |

Congratulations to the best hackers:

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

1 | halyavin | 225:-5 |

2 | Marcosk | 22:-3 |

3 | sfialok98 | 5 |

4 | Rhouma | 4 |

5 | FakeGuy | 3 |

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

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

A | 300iq | 0:01 |

B | HIT_Zero | 0:13 |

C | Dalgerok | 0:07 |

D | ruhan.habib39 | 0:08 |

E | Dalgerok | 0:14 |

F | MrDindows | 0:17 |

G | chemthan | 1:13 |

Will hacking phase be just 12 hours from now on?

Hope we won't wait till the next morning of the contest to know the result and rating changes :D

We will, hacking lasts 12 hours

But usually we wait for along time after hack phase ends.

i hope we won't wait :(

But I have to wait until the next afternoon (or the next evening, for the poor speed of system testing and rating changing) as a Chinese. I just want to have a good sleep (instead of staying up late) and can see the rating changes as soon as I get up.

What does Codeforces have against Mexicans? That's two rounds at the same time as Mexico's matches in the World Cup :'(.

luckily for you they never make it past the fourth game.

Just like you'll never make it to Candidate Master

Yikes... -1

I guess he'll make it to Candidate Master lol

I guess I will.

I guess he did. Well done.

Hope to see good problems,not just implementations.

Yeah true. Problem A and B should be implementation then after all problems must concentrate only on logic.

1000th contest

yeah,how time flies!

I expected special round for anniversary contest :(

To me, all rounds are special :)

Maybe it is a special round? Maybe there will be fast syste... Oh no, fast systests won't help, there is 12 hours long hacking phase...

can i hack which problem i have not solved?

yes! you can.

And you can copy anyone's solution before you hack others.

Most of the hacking is done in first 2-3 hours. Mininize hacking phase to only 6 hours

thanks bro...

welcome & all the best for contest

I agree. It is annoying to wait 12 hours

still less annoying than ur annyoing comments

Mock him all you want, he is Numb

Still less annoying than ur usual comment

Couldn't agree more.

But then Chinese will have to not only stay up to participate in contests, but also keep staying up after the contests to hack.

Mmm... I made 16 hacks in the last 4 hours of hacking phase, and only 6 in the first 2 hours. I think 24 hours was too much, but 12 hours is not that bad!

12 hours to hack is toooooooooo long.

I agree with you. The rating changes are always come out at the second day when we have an Educational or Div. 3 round.

Messi Is back xD

What does one mean by hacking problems? This would be my first contest of this type. Can someone please guide regarding the rules and terms ?

After The Contest ended.....everyone Can See your solution and if he found anything wrong he can hack you and the problem won't be Accepted

If my solution gets hacked, it will not be accepted and I will lose points, what will the hacker get ? Thanks for the reply.

nothing

in Educational Contest He Won't Get Any Thing Except if he made a lot of hacks he will became from most hackers of Contest But Also he won't Get any Points.

But in Usual Contests He Can Hack participants in his room in Codeforces after locking his problem and if he hacked any one he will get 100 points and if he make Hack But it was unsuccessful He will lost 50 points

pleasure.

The 12 hour hacking seems to be useless as no one will waste that long time once they comes up with some hacks they tries them and leaves the site.

I can't understand why i am getting this many downvotes

Some people just want to watch the world burn!!

Seems people are agreeing on minimizing the hacking phase...

i thinks educational hacks shoud give some (points) (reduce time)

so it will encorage people to hack (like me)

*encourage :P

You hacked his comment.

Educational rounds are created to solve problems and not to hack

This is a reason why the hacking phase should be minimized.

so why rating changes .. ?!

My brother is suffering from cold, Doctor said that he will feel good if I get upvotes here. I am new to codeforces and have no friends, will you help me?

how can codeforces community help you?

keep this fb thing there itself :|

Problem A fucked me deep....

The weird thing is you commented this in the middle of the contest!! Man, during the contest you should concentrate only on solving problems.

problem E is not clear at all and explanation for the sample input/output is also missing.

code force is retarded. edu round is dumb. your all dumb

What happened to 300iq ???

Left a record in the standings of contest 1000 and plunged into problem preparation. (I guess)

Nice contest, thanks, problems B, D and E are really nice. Problem A kinda awful though.

TASK F looks for wavelet tree or persistent segtree's.

You can do F with regular segment tree.

The idea is to sort queries by start-index, and only keep indexes i, such that index i is the first time number V[i] appears in [start-index, n).

For each such number, store where the next same number is.

Now, you just want to find the maximum element in an interval. If it's not large enough, answer is 0. Otherwise, its value is the answer.

When moving to the next query, loop from last-start-index to start-index — 1, deactivate those indexes, and activate indexes of their values's next appearances.

ExampleLet's keep pairs in the segment tree to easily get what is the number with maximum index of next appearance.

Say our array is

`[1, 2, 1, 3, 2, 2, 3, 1]`

, and we have the queries 1 3, 2 6 and 3 8.Next-array:

`[3, 5, 8, 7, 6, 9, 9, 9]`

(one-indexed)Initial state (start-index = 1):Active-array:

`[1, 1, 0, 1, 0, 0, 0, 0]`

Values in segtree:

`[{3, 1}, {5, 2}, {0, 1}, {7, 3}, {0, 2}, {0, 2}, {0, 3}, {0, 1}]`

To answer query 1 3, we find the maximum in the interval [1, 3]. It is {5, 2}. 5 is larger than the endpoint of the query, so we output 2.

Now we have to move start-index from 1 to 2. To do this, we activate the next appearance of the number at index 1, and deactivate the number at index 1.

State with start-index = 2:Active-array:

`[0, 1, 1, 1, 0, 0, 0, 0]`

Values in segtree:

`[{0, 1}, {5, 2}, {8, 1}, {7, 3}, {0, 2}, {0, 2}, {0, 3}, {0, 1}]`

To answer query 2 6, we find the maximum in the interval [2, 6]. It is {8, 1}. 8 is larger than the endpoint of the query, so we output 1.

State with start-index = 3:Active-array:

`[0, 0, 1, 1, 1, 0, 0, 0]`

Values in segtree:

`[{0, 1}, {0, 2}, {8, 1}, {7, 3}, {6, 2}, {0, 2}, {0, 3}, {0, 1}]`

To answer query 3 8, we find the maximum in the interval [3, 8]. It is {8, 1}. But since 8 <= 8, no number appears only once in the interval, and we output 0.

thanks.

A very nice solution!

A & B & C are mostly implementation problems. Is this really Educational round? Educational rounds used to be different.

I think you haven't read D, E, F, G. These problems are just like what you would expect to find in a usual Educational round.

Also, I don't think the implementation in C is too heavy. A has an elegant and short implementation.

How to solve G?

What is the story behind your username mango_lassi? You don't seem Indian to me.

Key idea, in my opinion, is to calculate for each

idp_{i}— maximal profit of 2-path starting atiand finishing ati. Ifiis a root of tree, thendp_{i}is just pretty standard dp for subtrees. To calculate dp for each vertex as if this vertex is root — it's possible with technique of "rerooting" (actually, I don't know it's real name as I don't know where to find materials to this quite standart technique).How to solve C?

Classical scanline problem.

Explain pls. I know its easy (got that by seeing the number of solves) but I couldn't figure it out.

What would we do if constraints were small? Use partial sums!

So now we can do similar thing just using map instead of arrays for partial sums.

How to solve D though?

P.S : I think there is even a way of doing it without using maps. I am unaware of that sorry!

Let dp[i] denote number of good subsequences ending at i. So a subsequence will be divided into parts which are good. Now look at the last part of the subsequences which end at i. Let the start of the last part of that subsequence be j. So dp[i] = sum(((pref[j-1]+1)*ncr[i-j-1][a[j]-1])) because we have to choose a[j]-1 elements between i and j to complete that part and the subsequence can be completed by the rest of the parts ending before j.

Why are you adding +1 to pref[j-1] when taking the summation?

Suppose you have m queries with l and r.(Array of size n)

Now you can traverse the array 10 times incrementing values between l and r.It take Time Complexity O(n*m). OR u can put +1 on l position and -1 on r+1 position.After inserting u can just traverse the array a single time to get the final array.O(m+n)

No i got how to solve C. I was talking about D and T1duS's method as to why we are adding +1 to pref[j-1]. I got it though. It's because one of the subsequences would be starting at j and ending at i and we ignore the subsequences before that. Add those many subsequences to the number of subsequences starting at j and ending at i multiplied to the number of ways of ending subsequences at j-1. That will be the ans for dp[i].

You can read about it here.

For a given segment say [x y] mark x with +1 and y+1 with -1 and store it. Now just visit these points and check the running sum,and update the running sum on a array with the number of coordinates in between,i.e a[running sum]+=numberofcoordinates,print this array from 1 to n as given.

Thanks

What I did was create a map with the # of the segments that started and ended at a certain point. Then I traversed the points in order, keeping a variable that kept track of the current number of segments. I treated the intervals (spaces between points) and the endpoints separately. Make sure to use long longs.

keep a map of indices of segments and use it as partial sum. Though it struck me a little late. Solution(Easy to understand)->http://codeforces.com/contest/1000/submission/39725149

Codeforces contest is not as good as it was before .

Wanna ask a question:

What should a person do after finishing problems he can do in an Educational Round?

(As for me, only problem G left, and I have about 20 minute, then I know how to solve G but I know I can't finish in 20 minutes.

Then I have nothing to do in these 20 minutes: sitting there pushing F5 and seeing my rank falling.

So guys, how do you handle these time ? :) (One may hack in a normal round)

I would do nothing, but enjoy looking at standings (because you solved 6 problems).

But you didn't...... Edit: Oh I see what you mean, never mind

Well bro, I didn't find you in the standing ???

I don't know, maybe you are an accurate one, so waiting won't be a bad choice.

But

almost every contestI participated, I "die from" penalties(wrong submition). So even if I finished early, many who finished after me will have a higher rank than me.How should I deal with that? (Yeah, yeah, yeah, control my hands)

Here I meant you solved 6 problems.

`But almost every contest I participated, I "die from" penalties(wrong submition). So even if I finished early, many who finished after me will have a higher rank than me.`

Yeah, you're right, but if they add feature that allows to hack solutions during the contest there is no need to hold special educational rounds, so I still recommend you to enjoy from your results XD

Sorry I misunderstood you.

And feel guilty that I downvoted you yesterday. :(

Please forgive me.

P.S.: But still, I didn't solve 6 problems... :(

`But still, I didn't solve 6 problems`

I'm sorry for that :(

try to find bugs in your own solutions so they don't get hacked

You are right!

For E does this work?

1) Find all cycles, and mark each edge in a cycle with 0 (and keep all other edges marked 1)

2) Start at a random node, and find the farthest node from it through a DFS, but by "farthest" i mean weighted distance where the markings denote weight. Denote this farthest node X

3) Similarly find the farthest node from X (with weighted distance, where edges in cycles are distance 0 and edges not in cycles are distance 1), denote this node Y.

Y is the answer

Yes. Though an easier way to think about it is diameter of bridge tree.

Never thought an E problem could be explained in a single line, beautiful!

Never mind, it is indeed diameter

Hacking page is not loading..!!

Can Problem C be solved using Mo's algorithm?

C? I don't think so. Doesn't even look like a Mo problem.

Though F definitely has a Mo solution :D Our model implementation works a bit over TL (like 3.4 seconds) but couple of participants actually squeezed it.

Can you please explain how to keep answer? I used unordered set, but I still getting TL

You can store not the hashset but the whole array of number counts. Then you do sqrt decomposition over this array, you make updates in

O(1) and then ask in . I believe, the code is pretty much self-explainatory.Isn't this Mo's Algorithm?

There are both Mo's algorithm and sqrt decomposition)

What is the time complexity of such a solution, wouldn't using a set reduce it (despite large constants)?

It's , I believe. No idea how to make a good use of set in that case.

More precisely, In this task, using Mo's Algorithm, you will need to move left and right borders times, but asking for any element you will make no more than

mtimes, so using sqrt-decomposition gives you slow asking operation (), but fast move operation (O(1)). In result you will get .On the other hand, using set will give you same complexity for asking and move operation, so result complexity will be .

I tried to implement this idea but I got TLE, it seems that the comparator you used is the key to get Accepted, the solution passed in under 2 seconds after I tried it, can you explain how it works ?

Update: I figured it out, this is a very clever trick :D The parity thing makes a block continue working from the index that the previous block finished working. This means that inside some block, the right index of mo's algorithm will keep increasing until it reaches the end, for the next block, it will keep decreasing while answering queries in the opposite direction instead of removing all the elements then increasing the right index from the beginning.

in problem C it happened for the first time that PYPY gave TLE and python 2 passed in 2345ms. When I saw the accepted solutions in pypy, there were only three and their time was also quite borderline. How can pypy be slower than python 2

I would like to know the same. My submission got TLE during contest: 39712202. Fearing that the time limit is too strict I switched to C++. And here's my practice submission with an AC: 39725290

cases are too harsh I guess. I guess during main test cases after the 12 hours hacking period python solutions might also fail

Our python3 implementation of it works in 2137ms, we dicided that about 1 second off TL is fine for this.

yeah even python 2 solution worked well within TL. It's just that how come pypy gave a slower output than python. This rarely happens.

Yeah, we didn't really expect that. Unfortunately, we had no way to test it as polygon doesn't support pypy.

I thought implementation for A is too heavy (for usual A in educational) until I see this submission...

This is better, http://codeforces.com/contest/1000/submission/39704314

if only the round would be extended for 1 minute, I would solve Е :(

E is about finding the diameter of the tree of cycles, right?

But how do you find and isolate each cycle? Tarjan's algorithm only works in directed graphs and I couldn't figure out how to apply it on undirected ones..

You can find the bridges of a graph with Tarjan's like this. With them, you will then be able to combine all the nodes that share some cycle. And you will end up with a tree.

maybe i should be saying sorry for this question , but can someone please explain to me A and why n — (all the sizes that are the same in old and new t-shirts sizes) is an logical answer ?

Because you need only 1 second to change one size to another if they have equal length. The answer can't be less because you need to change at least this number of strings.

and if there a test case where input is

1

XS

XXXL

how can a code like the one i described be good ?

((sorry if i just misread or didn't understand the problem))

this one is invalid test case .

1) You can only change letters, not add or remove

2) It is guaranteed that you can get one list from another

So this test is incorrect

Thanks Numb and anno

sorry if i wasted your time with my -3 IQ.

lets take all the t-shirt name of lenght 3 that is xx_ so in old t-shirt either it will be present or absent so if it is absent so we only need to change the last character but if it is present we can use that and we cannot reduce or increase the length of the names so we will only consider length 3 similarly for all.

can anyone help me to understand the problem statement of E problem and the output of the given test cases?

You need to find two vertices

sandtsuch that the number of bridges on the way fromstotis maximized.how the answer of first test case is 2 ?

pick

s= 4 andt= 5, then you have two bridges (4, 1) and (5, 2) on the way fromstot.Thank You @numb , @jakube

May someone please tell me why my solution for A 39724005 is wrong?

Consider this test case:

2

M

S

L

M

Your output = 2; Answer = 1;

your code is failing for this 6 L L L M M M L L M M M S output should be 1

Thanks! I was looking for cause of failure of my code.

try this testcase:

I have also done same mistake in my code Now understood flaw. Thanks for the test cases.

٧_٧

Thank you all IIIIIIIIIIIIIIIIIIIII, anno and lazyc97, now I get it.

I worked during the contest on coming up with such tests, but failed with it :(.

Can anyone explain the approach to B? Thanks!

Basically you should notice that the best is to insert the new number just next to some a[i] or just before it.

So you can try all possibilites. To do that, could be a good idea to have an accmuluate array that tells how many time is on from number i to the end. Then you can go from left to right and get the answer for every possible insertion and take maximun.

Can Anyone please explain D and E.

Let's denote with

`dp[i]`

the number of good subsequences of the array`a[i...n-1]`

, and define`dp[n] = 0`

.The good subsequences of

`dp[i]`

either use the element`a[i]`

or they don't. There are`dp[i+1]`

good subsequences that don't contain`a[i]`

. So we only need to count those that do.These subsequences might contain multiple good arrays. Let's focus on the first one. Its size is exactly

`a[i] + 1`

. If`a[i] <= 0`

then there are obviously no good array starting with`a[i]`

. So assume that`a[i] > 0`

iterate over the last element in this good array. It can be any element`a[j]`

with`i + a[i] <= j <= n-1`

, and there are`nCr(j - i - 1, a[i] - 1)`

possibilities to pick the middle elements of this good array. We count this sequence alone, and we can also combine it with each good subsequence in`dp[j+1]`

.Therefore we get the recursion:

And the solution to the problem is

`dp[0]`

.Hi, I followed your solution, however the recurrence relation gave me 1 more than the answer and I don't quite understand why. Could you explain this?

Do you mean my implementation? I used a slightly different definition. I defined the empty array as a good subsequence, so at the end I have to subtract this one.

This is a submission that corresponds directly to the explanation: 39734194

Btw, there was a little error my comment above. I forgot the + 1. But now it is fixed.

Why you added +1 to dp[j+1] before multiplying to that nCr formulae. I didn't got that.

Look 2/3 comments below.

Ohh got that thanks .

That was a very pretty solution. Thanks a ton. I got that

Why have you added 1 in your formlula? I know that simply dp[j+1] won't give the right answer but (dp[j+1]+1) will give but I am not able to get the idea behind adding 1. Sorry for such a silly question

You can either combine the good array starting at i and ending at j with any of the good subsequences in a[j+1...n-1] => multiply by dp[j+1]

Or you can only use the subsequence alone (without combining it with other subsequences) => + 1

Oh okay! Completely missed that! Btw thanks for providing such a nice explanation!

Any one solved F using MO's Algo within TL ? UPD: 39735901

After contest:39725241 Hacked :D

Rofl Was unrolling these loops really necessary?

One unrolling helped to pass the time limit.

Too close TL,resubmission may get TLE!!

See this submission 39747523

Can someone please help out with

Problem C?Thanks! I don't see a way to start. The tag said "SORTING," but I am not sure how to even apply it here.

The keyword is "Sweep line algorithm".

Basically you convert each segment [

l,r] into two events (l,begin), (r,end), sort all those events and compute the answer by iterating over the events. At each event point you can compute the answer for the last interval [last_event+ 1,current_event- 1] in constant time, since the number of segments doesn't change in this interval.This is actually a classic geometry concept, which is called "Line Sweep". It's called that because we can imagine a vertical line moving from left to right, covering all the points lying on the x-axis one-by-one. What we do is, store all the segments(x, y) separated in an array, with each element being (val, isStart), where val is either x or y, and isStart is 1 if it's an x value, and 0 if it's a y value.

After storing all the segments this way in an array, we sort them according to their value. Then, we perform the sweep while keeping a counter

`open`

for the number of segments that are currently open. When we come across a value where isStart is true, that means that a segment is starting at this point, so we increase our counter`open`

. And when we come across a value whose isStart is false, we decrease the counter`open`

.This way at any point we know exactly how many segments are covering it, and using this we can find how many points have

`open`

number of segments covering them.Here is a tutorial blog about the line sweep technique: link

And, here is my code for this question: link

If you need any more explanation, do let me know!

Damn towards the end of the contest I had this idea but it was too late. Thanks for the explanation :)

That moment when your script hacks your own solution

Can I get the code for the script? Is it open source?

Could he use it in an non-educational round?

No, you cant copy solutions, and it is forbidden by rules.

And it is the first test I tried to use for hacking. If only I checked this corner case during the contest...

Ironic. He could save others from hacks, but not himself.

Do all hacks run against all submissions at the end of hacking phase?

of course

I was doubtful because I checked the contest page after 5 minutes of end of hacking phase and it said 'Final standings'. I wonder how they managed to run all the codes on all the hacks so quickly!

We need to wait for final testing. 'Final standing' is not final standing yet.

Yeah it is not the true 'Final Standing'。Maybe System will rejudge soon

Come on ! Rating changes ?

Time taken to update rating is directly proportional to the amount of rating you are going to gain xD

For problem E this is an excellent link by IIIT Hyderabad threads on quora: https://threads-iiith.quora.com/The-Bridge-Tree-of-a-graph

truly a hacker...

I'm scared about systests now :(

Yes, by this time I think they should've been updated the ratings no? Or educational rounds take this much time usually?

when can I get the solution and the rating changes?

urge..

I found two pairs of people, which have one solution — 39722722 and 39716743; 39723479 and 39714675.

i think first one from practice another from official contest

One of the best educational round I could see on codeforces, in terms of quality problems. Though I couldn't participate in the round.

The systest is really fast, but the rating changing is too slow... Maybe make it faster?

Systests were faster because they only need to check for the hack tests.

When will you publish the Editorial ?

Eagerly waiting for the editorials..when will they come?

Can F be solved with a mergesort tree? ( By keeping all the elements which occur once in the nodes. Also, merging is easy. )

Why is this code for problem C giving run time error on testcase 4?

You compare operator doesn't make any sense.

`sort`

expects that the compare operator`cmp(p, q)`

returns`true`

, if`p`

should appear before`q`

in the sorted order.But with you implementation, and using two element

`p = {1, 'l'}`

and`q = {1, 'l'}`

, both`cmp(p, q) == true`

and`cmp(q, p) == true`

. So of course C++ is confused. How can an element`p`

appear before`q`

and behind`q`

at the same time?Thanks, finally got it accepted :)

But why did it work for testcase 1, 2, 3?

Probably because there are not identical elements in those cases.

Your crafting.oj.uz ratings are updated!

When will you publish the editorial? I'm eager to read it :-)

Editorial?

I am new to codeforces. Can someone tell when we can expect editorial for this round?

The editorial is published.

It's expected a tutorial about how to solve the problems?

I tried to do problem E by compressing the cycles to a single node.My solution is running on my computer compiled with command

`g++ -std=c++14`

but on submitting it is giving an error.Here is my solution. Any help ?

I have a strange behavior for my solution for Problem 1000G - Two-Paths. If I read integers with cin my solution (39859090) is Accepted. If I use scanf (39859098) or getchar (39859106) I receive "Wrong answer on test 9". How is that possible? In getchar-version I even checked whether input is fine, which seems to be the case (otherwise I would have received a Runtime Error). Can somebody figure out the reason?

Update: Found a small bug (using index outside of range of vector) and now it works (39861715). But the question remains: How can it make a difference whether I read with cin or scanf??