Hello Codeforces!

On November 09, 18:05 MSK Educational Codeforces Round 32 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.

The round will be **unrated** for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day 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 Mikhail PikMike Piklyaev and me.

Good luck to all participants!

UPD: Editorial.

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

Thank you for taking part in the 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC. It was a pleasure to have you on board. We hope you enjoyed it and we would love to have you back next time.

Congratulations ITMO and Harbour.Space University teams for winning divisions A and B! It was amazing watching the scoreboard throughout all nine days as teams from New South Wales, Saint Petersburg, Tokyo, among many others, challenged the top spots. Watch the recap here!

``Geometry is the key to success in modern contests'' states Andrey Stankevich, coach of 7 ACM-ICPC World Champions

Lecturing both divisions A and B, Andrey brought a vast wealth of knowledge to the boot camp, and shed light on how to better tackle the problem sets that teams will face in their upcoming regional competitions.

“What technology should we use to analyze big data?” asks Alexey Dral, Head of Data Science School at Corporate University of Sberbank

Leisure day was a full one, with bus city tours, to gaming, to lectures and workshops. We had many special guests Sberbank, including Alexey Dral, who talks about the impact of a boot camp that is not only focused on the coding aspect, but the machine learning, the data processing and the practices that each participant can utilise to become an ACM-ICPC competitor to be reckoned with.

**Scholarship Information**

We are offering a Scholarship for each of our three tech programmes: Data Science, Computer Science and Cyber Security — fill out the Form for the January 2018 programme start period or the September 2018 programme start period. We will contact you soon. Can't wait to see you here!

9th Nowember seems like a good date for a contest :3

Yeah, definitely)

Sorry for the typo, it is fixed now.

Is it .....??

Is it amazing???

Andd 5 page queue during contest................

Why in all of your problems in stead of "if" you wrote "iff" ?

It means if and only if.

The regular "ïf" mean the same.

It's different, if x then y can't be said as, "if you get y, then you can get x". But, x if and only if y, you could say, "if you get y, you can get x".

ignore pls

How to solve G?

I'm quite certain that it can be solved by algorithm Boruvki

I used tries, but it passed with just 150 ms left, will probably give TLE on hacks. Also, weirdly, none of test cases have n = 1.

Can you please explain your solution in a bit detail.

https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

Use the technique in the above mentioned thread to find minimum edge between two nodes, one of which is already visited. We can find minimum among possible edges by using priority queue.

I think I might have done something similar. However I'm not sure what the complexity is.

Basically every time I select the existing vertex with the smallest edge. However it may be an edge to the vertex which is already in the tree. Then I have to remove that edge and find a new one to non visited vertex. I am not sure what is the limit of such edges. Isn't it O(n^2)? I can get an edge to already visited vertex either when I found a new non visited vertex -> O(n) or when I removed the edge to the visited vertex -> O(n^2)?

Ok, here is my accepted O(n^2) submision. Algorithm: at each step choose the minimum edge to connect a vertex to already constructed mst.

Counterexample:

At some point we have some mst and the vertices in it are processed. Let's say that all of these vertices point to unprocessed vertex:

nxt.Now we choose the minimum edge to

nxt, from already processed vertexcur. Now we removenxtfrom trie and we choose next best edges forcurandnxtand they both point to unprocessed vertexnxt2. These edges are more expensive than edges we already have in the queue:x— nxt.Because

nxtis now in mst, we have to remove all of these edges. Every time we remove edgex-nxt, we find a new minimum forx, which isnxt2.This way, before we add

nxt2to mst, we have to revisit all existing vertices. The same situation will happen fornxt3, etc.Could you please tell the difference between your approach or do you also have O(n^2) solution?

I did the same thing, however I dont think it is O(n^2). I think it is O(nlog^2(n)). I mean it can only be O(n^2), if all/most numbers keep getting the same number as their minimum edge.(all vertices point to same nxt) But can that happen? Or can it be shown that vertices pointing to the same number will be O(logn)?

I can't prove it, but I can't think of an example where all numbers get same minimum. What do you think?

Edit: Please Ignore. It is wrong.

I think I found a proof:

Suppose there are k numbers pointing to the same number nxt. We try to prove that k = O(logn)

Lemma 1: For each bit i, there can only be one number in which the ith bit is different from ith bit of nxt and all previous bits are same.

Proof: Suppose there exist 2 numbers and first x bits of the numbers match with nxt, and (x+1)th bit is different from nxt. Then the numbers will match to each other since xoring different bits always gives 1, and 2^c > 2^(c-1)+2^(c-2)+...+2^0 for all c.

In a number n, there will be logn bits. Let us define a function f(i, nxt) which will return all numbers who have exactly first i bits same as nxt, and point to same nxt.

So, Maximum number of numbers that can point to same nxt will be: Sum of f(i, nxt) for all i belongs to [0, logn]

From lemma 1, f(0, nxt) = f(1, nxt) = ... = f(logn, nxt) = 1.

So maximum vertices that can point to nxt = k = logn

So time complexity for this approach = O(nlog^2(n))

I'm not sure that I understand Lemma 1 and its proof. I don't understand why can't you have 2 vertices already processed which have the same x+1 bits, the same x bits matching with nxt and x+1 bit different. They can't match with each other (or they already did) as they are both processed and in MST.

Yeah.. I am sorry, it is wrong and makes no sense. I don't know why I wrote that.

First two questions are way too easy

How to solve E?

Divide and conquer, or meet in the middle. Whatever you wanna call it

Meet in the middle technique:

Divide the array into two smaller ones of size n/2. Now you can brute-force all the possible combinations of values you can get by choosing subsequences of each array. Store them in two sets. This step takes O(2^(n/2))

Now iterate through the first set. Our goal is to get the closest number to m-1 (which is the best answer possible). So, for each number x in the first set, we can binary search for the best value y of the second set that gets us closer from m-1. Keep track of the maximum x+y gotten, that is the answer

Why DP doesn't work in E ?

We take %m of each element before storing in array, then sort the elements followed by L to R DP which says dp[i] = max(dp[i], (arr[i]+dp[j]) % m ), for all j < i. Before running dp[i] is initialized with max(arr[i], dp[i-1])

Because of TLE+MLE

NOPE !! I don't think there is any case of TLE or MLE here.

Oh wait... I didn't read your comment. It's actually WA.

because there is no optimal substructure. To solve for i, you are taking (arr[i]+dp[j])%m, which might be less than (arr[i] + suboptimal[j])%m, where suboptimal[j] < dp[j]

Any idea why this is getting TLE ?

`upper_bound(s1.begin(),s1.end(),r);`

this takes linear time, not logarithmic. Read this: http://codeforces.com/blog/entry/55450I solved it using Meet in the middle + Binary search

Split the n numbers to 2 sets, find all the possible subset sums for every set, that can be done in

for each setO(2^(N/2))sort one of them and iterate over the other set, for every element, binary search for the value that gives the max value % m

HOW TO SOLVE CPLEASE TELL!!Binary Search

Can you elaborate

Sure. If you do not know about binary search better learn it from top coder or some other popular resources.

After that, notice that if you can find an answer for length k, then as well for any length > k, so it's a go left binary search. You try to reduce values of k, and keep validating it as long as it is possible, once you see no more left movement can be done you return.

binary search. take substring of length k. if all substrings of length k contain a character decrease k, else increase k

THANK YOU!! But can you give an example plz

I used simple greedy. Mark positions of occurrence of each letter in vector v[ch]. Additionally, add -1 and n to it (indexing begins from 0). Now calculate the max distance between 2 elements in each v[ch]. Take min of all these maximums.

I used the same idea of vector but with binary search, I couldn't think of this easy technique you used. Thanks !!

You're welcome :)

a

THANKS

For every letter from a-z that exists in the string find the maximum k such that any substring of length at least k contains that letter. Or in other words find the maximum difference between two contiguous occurrences(or boundary) of that letter. Report the minimum k as the answer.

I did without B.S.

what I did is:

For any String minimum k value goes to l/2+1 where l is length of string...

For ex:abcde k=3 and abcd k=2

I checked for all character,found maximum of distance b/w them..And took minimum

That will be final answer...32173323

I did the same thing !

Why people don't post Editorial quickly -_-

When it's your turn for preparing editorial, you will know why.

May be :(

But when I am waiting to read the editorial and solve the problems after the contest but the editorial isn't appearing, :/ I forgot to solve it later. For me, Later is never :( I don't know about others...

Well, if I was hosting a contest, I would make sure to have the editorial completed before the contest begins.

yeah! me too!

For this contest open hacking phase is still going on. They can not post editorial before it finishes.

Yeah! But what about now? :/

I found some mistake in one of my submissions and resubmitted it before the contest ended. Will it be considered in case 1st one is hacked?

Yeah you should be good

Me at problem D be like:

Left at derangement

unfucking belivable you just copy people problems and don't mention their name. It was a couple of months ago i send problem F to Edvard.

The thing is that Edvard doesn't take any part in preparing Educational Rounds now. He doesn't send me any problem proposals or anything. So the fact that we have prepared a problem that you sent him is just a coincidence.

How to solve D

Derangement

Can you ellaborate

i will read algorithm then

1) We always can get sequence 1, 2 ... n

2) Then calculate answer for each k from 1 to k (from input). We can swap C(n, k) sets of positions. Numbers of swaps for each set is !k (subfactorial).

ans = 1 + ∑ C(n, i) * !i (i from 1 to k)

How did you get those constants in array arr{0, 1, 1, 2, 9}?

I just write bruteforce, see this numbers and use them

those are the number of permutations of k elements where no element stays in his original(fixed) postition. you can find them yourself by hand for small k's or use this formula

`a(k) = k*a(k-1) + (-1)^k`

(proved by Euler)These numbers are subfactorials.

But array should be {1, 0, 1, 2, 9}. I didn't use 0 and 1 indexes

Is the contests pages down right now?

http://codeforces.com/contest/888

Can anyone explain how to solve the problem G ?

Let's say that you have a lot of groups and want to merge them together with the minimum answer. You know the very base case that every node in a separate group, but how we will continue a lot of xor problems solve by trie store binary bits instead of strings.

Trie or prefix tree store one copy of every same prefix of the number, here we will put every number from the most significant bit to least significant bit. start traverse through trie all the numbers will have in common the very first node in the trie every node we will have 2 choices in this node (1 or 0) we need to merge the 2 groups by each other, every group of them will connect internally by each other later by the same way and its very obvious because every time we move in the trie the value that we add to the answer will decrease. We will connect the 2 groups by a search for every number in the first group and try to find the minimum number to it in the second group so now we connect the first group to the second group, but internally nothing happened we will move to the first and second group and do the same

algorithm.Algorithm: when traversing the trie if there is one edge only(1 or 0) you will go through it without adding anything to the answer if there are two edges(1 and 0) you will go through the two edges with addingvalueto the answer.Value: as we said before we need to connect the two groups together with the minimum value, for every element in group 1 we will find the minimum element for him in the second group and take the minimum one.Simplest code: here

Sorry for poor English and poor explanation :'D .

Perfect Explanation , Thanks gasser :) !

How to solve F?

I have solved C using binary search but my submission got time limit :((( can any one explain why ??

Your function fun() has two loops which will take max k*n steps and hence the TLE. You can make it run in linear time by maintaining the frequencies of letters in each subarray of size exactly k. My submission based on binary search: http://codeforces.com/contest/888/submission/32166677.

how to solve G?

here

this is weird for 2 days this problem was accepted and today it became wrong answer

http://codeforces.com/contest/888/submission/32182493

i tried the test case 28 on my codeblocks and my output was 2 but here they say it's 1

Oh look I am famous!