By BledDest, history, 3 years ago,

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

Go to form

• +123

 » 3 years ago, # |   +31 9th Nowember seems like a good date for a contest :3
•  » » 3 years ago, # ^ |   +34 Yeah, definitely)Sorry for the typo, it is fixed now.
 » 3 years ago, # | ← Rev. 2 →   -51 Is it .....??
•  » » 3 years ago, # ^ |   0 Is it amazing???
 » 3 years ago, # |   0 Andd 5 page queue during contest................
 » 3 years ago, # |   0 Why in all of your problems in stead of "if" you wrote "iff" ?
•  » » 3 years ago, # ^ |   +19 It means if and only if.
•  » » » 3 years ago, # ^ |   -33 The regular "ïf" mean the same.
•  » » » » 3 years ago, # ^ |   +5 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".
 » 3 years ago, # | ← Rev. 3 →   0 ignore pls
 » 3 years ago, # |   0 How to solve G?
•  » » 3 years ago, # ^ |   +1 I'm quite certain that it can be solved by algorithm Boruvki
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 Can you please explain your solution in a bit detail.
•  » » » » 3 years ago, # ^ |   +4 https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problemsUse 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.
•  » » » » » 3 years ago, # ^ |   0 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)?
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   +5 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 vertex cur. Now we remove nxt from trie and we choose next best edges for cur and nxt and they both point to unprocessed vertex nxt2. These edges are more expensive than edges we already have in the queue: x — nxt.Because nxt is now in mst, we have to remove all of these edges. Every time we remove edge x-nxt, we find a new minimum for x, which is nxt2.This way, before we add nxt2 to mst, we have to revisit all existing vertices. The same situation will happen for nxt3, etc.Could you please tell the difference between your approach or do you also have O(n^2) solution?
•  » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 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?
•  » » » » » » » 3 years ago, # ^ | ← Rev. 4 →   0 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 = lognSo time complexity for this approach = O(nlog^2(n))
•  » » » » » » » » 3 years ago, # ^ |   0 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.
•  » » » » » » » » » 3 years ago, # ^ |   +5 Yeah.. I am sorry, it is wrong and makes no sense. I don't know why I wrote that.
 » 3 years ago, # |   0 First two questions are way too easy
 » 3 years ago, # |   0 How to solve E?
•  » » 3 years ago, # ^ |   0 Divide and conquer, or meet in the middle. Whatever you wanna call it
•  » » 3 years ago, # ^ |   +17 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
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 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])
•  » » » » 3 years ago, # ^ |   0 Because of TLE+MLE
•  » » » » » 3 years ago, # ^ |   0 NOPE !! I don't think there is any case of TLE or MLE here.
•  » » » » » » 3 years ago, # ^ |   0 Oh wait... I didn't read your comment. It's actually WA.
•  » » » » 3 years ago, # ^ |   +8 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]
•  » » » 3 years ago, # ^ |   0 Any idea why this is getting TLE ?
•  » » » » 3 years ago, # ^ |   0 upper_bound(s1.begin(),s1.end(),r); this takes linear time, not logarithmic. Read this: http://codeforces.com/blog/entry/55450
•  » » 3 years ago, # ^ |   0 I solved it using Meet in the middle + Binary searchSplit the n numbers to 2 sets, find all the possible subset sums for every set, that can be done in O(2^(N/2)) for each setsort one of them and iterate over the other set, for every element, binary search for the value that gives the max value % m
 » 3 years ago, # |   0 HOW TO SOLVE C PLEASE TELL!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Binary Search
•  » » » 3 years ago, # ^ |   0 Can you elaborate
•  » » » » 3 years ago, # ^ |   +1 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.
•  » » 3 years ago, # ^ |   0 binary search. take substring of length k. if all substrings of length k contain a character decrease k, else increase k
•  » » » 3 years ago, # ^ |   0 THANK YOU!! But can you give an example plz
•  » » 3 years ago, # ^ |   +6 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.
•  » » » 3 years ago, # ^ |   0 I used the same idea of vector but with binary search, I couldn't think of this easy technique you used. Thanks !!
•  » » » » 3 years ago, # ^ |   0 You're welcome :)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   -15 a
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -8 THANKS
•  » » 3 years ago, # ^ |   +3 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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=2I checked for all character,found maximum of distance b/w them..And took minimumThat will be final answer...32173323
•  » » » 3 years ago, # ^ |   0 I did the same thing !
 » 3 years ago, # |   +9 Why people don't post Editorial quickly -_-
•  » » 3 years ago, # ^ |   +71 When it's your turn for preparing editorial, you will know why.
•  » » » 3 years ago, # ^ |   +25 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...
•  » » » 3 years ago, # ^ |   0 Well, if I was hosting a contest, I would make sure to have the editorial completed before the contest begins.
•  » » » » 3 years ago, # ^ |   0 yeah! me too!
•  » » 3 years ago, # ^ |   +5 For this contest open hacking phase is still going on. They can not post editorial before it finishes.
•  » » » 3 years ago, # ^ |   0 Yeah! But what about now? :/
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   +5 Yeah you should be good
 » 3 years ago, # | ← Rev. 8 →   +3 Me at problem D be like: Solution for k = 1 is obvious.using ruby to generate the permutation, and do a brute force solution (for small number)saw a pattern for k = 2.saw a pattern for k = 31 hour left to search for k = 42 minutes left (probably found a solution for k = 4)oh, it is wrong, Ok...edit: HOLY SH*T, my only mistake was the type of integer, should be int64 instead of int32.
•  » » 3 years ago, # ^ |   0 Left at derangement
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +34 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.
 » 3 years ago, # |   0 How to solve D
•  » » 3 years ago, # ^ |   0 Derangement
•  » » » 3 years ago, # ^ |   0 Can you ellaborate
•  » » » 3 years ago, # ^ |   0 i will read algorithm then
•  » » 3 years ago, # ^ | ← Rev. 3 →   +11 1) We always can get sequence 1, 2 ... n2) 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)
•  » » » 3 years ago, # ^ |   0 How did you get those constants in array arr{0, 1, 1, 2, 9}?
•  » » » » 3 years ago, # ^ |   +3 I just write bruteforce, see this numbers and use them
•  » » » » 3 years ago, # ^ |   +8 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)
•  » » » » 3 years ago, # ^ |   +3 These numbers are subfactorials.
•  » » » » » 3 years ago, # ^ |   +3 But array should be {1, 0, 1, 2, 9}. I didn't use 0 and 1 indexes
 » 3 years ago, # | ← Rev. 3 →   +5 Is the contests pages down right now?http://codeforces.com/contest/888
 » 3 years ago, # |   +11 Can anyone explain how to solve the problem G ?
•  » » 3 years ago, # ^ |   +2 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 adding value to 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: hereSorry for poor English and poor explanation :'D .
•  » » » 3 years ago, # ^ |   +1 Perfect Explanation , Thanks gasser :) !
 » 3 years ago, # |   +5 How to solve F?
 » 3 years ago, # | ← Rev. 2 →   0 I have solved C using binary search but my submission got time limit :((( can any one explain why ??
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
 » 3 years ago, # |   0 how to solve G?
•  » » 3 years ago, # ^ |   +1
 » 3 years ago, # |   0 this is weird for 2 days this problem was accepted and today it became wrong answer http://codeforces.com/contest/888/submission/32182493i tried the test case 28 on my codeblocks and my output was 2 but here they say it's 1
 » 3 years ago, # |   0 Oh look I am famous!