Привет, Codeforces!
9 ноября в 18:05 по Москве начнётся Educational Codeforces Round 32.
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной готовил Михаил awoo Пикляев.
Удачи в раунде! Успешных решений!
UPD: Разбор.
У меня также есть сообщение от наших партнёров, 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 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?
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.
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.net/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 O(2^(N/2)) for each set
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 C PLEASE 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.
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 :)
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
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.net/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 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: 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.net/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.net/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!
Почему не показываете людей, отправивших первое полное решение на каждую задачу?
Can you fix the typo in the statement of problem D? Double f's in if.