Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

savinov's blog

By savinov, 5 years ago, translation, ,

Hi, Codeforces!

Codeforces Round #285 will be held at 12 January, 12.00 MSK. Problems are authored by me, Evgeny Savinov. This is my first round at Codeforces. I hope that this isn't the last one.

I want to thank sokian and Golovanov399 for help in preparing and testing round, Zlobober for invaluable help in preparing round, AlexFetisov for testing round, Delinur for translating problem statements in English, and of course, MikeMirzayanov for great systems Codeforces and Polygon.

By the way, today(11 January) is MikeMirzayanov's birthday. Happy birthday, Mike!

The round will be for both divisions. Information about score distribution will be posted just before the round starts.

UPD1: Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

UPD2: The editorial can be found here. I'm sorry for the delay.

• +325

 » 5 years ago, # | ← Rev. 11 →   -32 It's time is too early in our (Iranian students) timezone because we have to go to school.
•  » » 5 years ago, # ^ |   -34 I think you already are.
 » 5 years ago, # |   +3 501,504??
•  » » 5 years ago, # ^ | ← Rev. 10 →   -36 because !
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +17 Read these reviews ... he tried so hard to answer the question ...(so funny)
 » 5 years ago, # | ← Rev. 2 →   -34 85 is a holy number for Iranians :D
•  » » 5 years ago, # ^ |   0 I'm an Iranian and find this weird!
•  » » 5 years ago, # ^ |   -23 But in china 69 is holy number!
•  » » » 5 years ago, # ^ |   +9 Number 69 is holy not only in China :)
•  » » » 5 years ago, # ^ |   -8 69????You're so rude...
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   -7 Do you like big number?Or big ...
•  » » » » » 5 years ago, # ^ |   -13 Not importantCause you have small ...
•  » » » » » » 5 years ago, # ^ |   -19 Do you see it?
•  » » » » » » » 5 years ago, # ^ |   -7 No...Cause you're so ashamed to show it...
•  » » » » » » » » 5 years ago, # ^ |   +2 Shame on you guys!
•  » » » » » » » » » 5 years ago, # ^ |   -6 haha~
•  » » » » » » » » » 5 years ago, # ^ |   -6 Why?
•  » » 5 years ago, # ^ |   +4 got it :))what about 90 ?!
•  » » » 5 years ago, # ^ |   0 Oh...That's so nice too :))
 » 5 years ago, # | ← Rev. 4 →   +55 Wow ... Mike's Birthday ... That's amazing ... :] #include using namespace std; int main () { cout << "Happy Birthday Mike ! \\:D/" << endl << "Thanks For Everything !!! :D" << endl; return 0; } 
•  » » 5 years ago, # ^ |   0 use Preview button better than editing 4 times :D
•  » » » 5 years ago, # ^ |   +9 Sorry ... :-"
 » 5 years ago, # | ← Rev. 2 →   +2 Happy birthday MikeMirzayanov.BTW it seems like tomorrow will be a busy day. Topcoder SRM 645 will take place 5 hours after the end of this round.
•  » » 5 years ago, # ^ |   +250 Nice — 5-hour long team training perfectly fits inbetween:)
 » 5 years ago, # | ← Rev. 2 →   +29 Happy birthday MikeMirzayanov.
 » 5 years ago, # |   -57 dis like me pls
 » 5 years ago, # |   +17 Information about score distribution will be posted just before the round starts.Why for almost all contests score distribution reveled just before the contest? What happens if author(s) revel it early?
•  » » 5 years ago, # ^ |   +3 No intrigue :)
•  » » 5 years ago, # ^ |   +4 The difficulty of the problems are very hard to judge...
 » 5 years ago, # |   +28 Weird timing. Cannot participate due to classes. BTW Happy Birhtday MIKE!!
 » 5 years ago, # |   +1 thanks :)
 » 5 years ago, # |   +10 Happy Birthday dear MikeMirzayanov.Best wishes, from iran, Hamed
 » 5 years ago, # |   +16 The first round in 2015 :)
 » 5 years ago, # |   0 Here in Venezuela Contest will take place at 4:30 a.m T_T i hope my alarm can wake me T_T
 » 5 years ago, # |   +1 new year starts , i want to enjoy it as much as possible....:)
 » 5 years ago, # |   -22 Are the problems easy or hard?
 » 5 years ago, # |   -15 Happy birthday!
 » 5 years ago, # | ← Rev. 2 →   -15 missed contest because of class :(
 » 5 years ago, # | ← Rev. 3 →   +19 Hey savinov !You can use this tag "Happy Birthday Mike ":)
 » 5 years ago, # |   0 Score distribution?
 » 5 years ago, # |   +3 I'm so happy that I catch the contest. It was a hurry that I went home from the school.
 » 5 years ago, # |   0 In Codeforces rounds, when two or more separate contests are going to be held, the contests numbers are given by separating with comma. How to detect which contest number belongs to which one? e.g.: Today, two separate contests are scheduled for two divisions in round #285 and the contest link is: http://codeforces.com/contests/501,504. Now, my question is which division belongs to 501? is there any general way to know this for any round before its started? I think, MikeMirzayanov could say the exact answer.Thanks in advance.
•  » » 5 years ago, # ^ |   0 Maybe it was scheduled to be a div2 only contest, and a contest was scheduled after it, and then it was made for both division?just a guess.
•  » » 5 years ago, # ^ |   0 you may check the URL of list of registered lists.
•  » » » 5 years ago, # ^ |   0 AlexDmitriev,Good idea, Thanks again. :)
 » 5 years ago, # |   -11 Oh no, dynamic scoring(((
 » 5 years ago, # |   -31 Why????????
•  » » 5 years ago, # ^ |   +1 You should had registered to contest using 'register' link in contest list. Not everybody always participates, so system should know who wants to generate rooms.
•  » » » 5 years ago, # ^ |   0 thank you, I understand
 » 5 years ago, # |   -49 I registered, whyyyyyyyyyyyyyyyyy?????????????????????????????
•  » » 5 years ago, # ^ |   -41 Actually I registered
 » 5 years ago, # |   0 in first 10 minutes i was 5th...But now I'm 260th...Why I can't never solve C???? :(
•  » » 5 years ago, # ^ |   +4 In first 10 minutes I was 3) And now 349 :(
•  » » » 5 years ago, # ^ |   0 And also now you are 1200 :)
•  » » » » 5 years ago, # ^ |   +1 Yes( I write 250/p instead of p/250 :( It's very very sad(
 » 5 years ago, # |   +158 It's a very bad idea to give numbers in decimal in D :(
•  » » 5 years ago, # ^ |   +8 Looking at D — I am now surprised that numbers in C are up to n, not up to 10^18:)
 » 5 years ago, # |   0 What was the aproach to task C?
•  » » 5 years ago, # ^ |   +6 Since the graph is guaranteed to be acyclic, it is a forest and hence it has a leaf. Find one such leaf v. Its neighbor-XOR-sum is the XOR of a single number (the label of its sole neighbor u), so we know there is an edge between v and u. Now decrement u's degree count and XOR u's neighbor-XOR-sum by v (this means removing v from the forest), rinse and repeat.To avoid O(n2) time, store the leaves in a stack/queue. After a first pass through the vertices, you will only add at most one vertex at any given time (if u above has degree two, u itself is added to the stack).
•  » » » 5 years ago, # ^ |   0 The moment, when you thought that in input vertices can be shuffled.
•  » » 5 years ago, # ^ |   +1 It is similar to topological sorting
 » 5 years ago, # |   +5 How to solve problem D/B ( Div2/Div1 ) . thanx in advance :)
•  » » 5 years ago, # ^ |   +5
•  » » » 5 years ago, # ^ |   0 I've used a similar approach.However, I could only transform the permutation into a factoradic sequence in a quick way, but not vice versa.Any good approaches? Thanks much!
•  » » » » 5 years ago, # ^ |   +16 What first comes to mind is a data structure that can find the k-th smallest element stored in it. I used a binary indexed tree in composition with binary search. From what I see after skimming some of the solutions that was a common approach. The total time complexity is .
•  » » » » 5 years ago, # ^ |   +8 You can use binary search.
•  » » » 5 years ago, # ^ |   +5 My submission 9414663 used this factorial number system but TLE'd. Is there an implementation that could make my program faster or is it because I used Python (which is slow)?
•  » » » » 5 years ago, # ^ |   0 list.remove is O(n).
•  » » » » 5 years ago, # ^ |   +1 You used decimal in your math.factorial(x) line. The trick is to avoid conversion to the decimal system and compute everything in factoradic directly.
•  » » » » 5 years ago, # ^ |   +25 Guess how long it takes to compute math.factorial(200000), and repeat this 200000 times.Yes, your algorithm runs in at least time. You have to find a faster algorithm.On the other hand, my solution got TLE too in Python, so yes, you also need to move to a faster language.
 » 5 years ago, # | ← Rev. 2 →   +13 Hi,I find the English version of problem C's description is confusing: " XOR sum of the numbers of vertices adjacent to v ..."I can only understand it, after look at the Russian version: "XOR-сумма номеров вершин, смежных с v ..."Seems like google translate did bad job :DPS: I am out of this round, so I comment here. Good luck for your final rank!EDITED: The statement should be: " XOR sum of the indexes of vertices adjacent to v ..."
•  » » 5 years ago, # ^ |   +11 The XOR sum of numbers a1, a2, ..., an is simply a1 ^ a2 ^ ...  ^ an; everything XORed together.Although yes, "the XOR sum of the numbers of vertices adjacent to v" might be better phrased as "the XOR sum of the labels of vertices adjacent to v".
 » 5 years ago, # | ← Rev. 2 →   0 Can somebody please explain to me the second test case for C problem? Thanks in advance. 2 1 1 1 0 Note: (From problem statement) ...were the first integer is the number of vertices adjacent to vertex v, and the second integer is the XOR sum of the numbers of vertices adjacent to v...No idea what second integer means. I do not understand why if both vertex have the same adjacent vertex number then the second number is different.
•  » » 5 years ago, # ^ |   +1 There are 2 verticles (0 and 1) with the only edge between them, so for zero verticle degree=1 and xor of 1 is equal to 1, for the second — degree=1 and xor of 0 is equal to 0.
•  » » » 5 years ago, # ^ |   0 Thanks!
•  » » 5 years ago, # ^ |   +1 There is an edge between vertex 0 and vertex 1.so for vertex 0, degree = 1, and XOR sum = 1 (vertex 1 is the only adjacent vertex)for vertex 1, degree = 1, and XOR sum = 0 (vertex 0 is the only adjacent vertex)
•  » » 5 years ago, # ^ |   +1 second integer means the XOR sum of the numbers on the adjacent vertexes, not the number of adjacent vertexes.For example, if a vertex 0 is adjacent to vertex 1, vertex 2, and vertex 4, then the second integer for vertex 0 is "1 ^ 2 ^ 4 = 7"
•  » » » 5 years ago, # ^ |   0 Thank you. I understood now.
•  » » 5 years ago, # ^ |   0 "were the first integer is the number of vertices adjacent to vertex v""the number of vertices" means the amount of vertices, connected to this vertex.I think it's a shortage of the translation.
 » 5 years ago, # |   +198 Am I the only one that thinks that number of interesting problems in that contest equals 0 :/? Though E was interesting a bit, but also pretty tedious to code, but I didn't find anything interesting in BCD, especially D which was "change decimal to binary and do some Gauss", pls. Sorry to say that.
•  » » 5 years ago, # ^ |   +163 I have the same opinion.
•  » » 5 years ago, # ^ |   +24 I found problem Div1-A/Div2-C pretty interesting and funny (maybe because our skills differ too much).
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +87 I was finding it interesting for quite a while — until I noticed it was a forest ;)
•  » » » » 5 years ago, # ^ |   0 is it even solvable if it wasn't a forest? :v
•  » » 5 years ago, # ^ |   -17 Wow, when writing that comment I expected lots of minuses, because that's what hating posts usually get, but people seem to agree with me :P.
•  » » » 5 years ago, # ^ |   +16 Well, usually when I see some downvoted hating post, it sounds like "I got TL on B, why did you set such a small limit? And I also got WA on C because of overflow, why there are no overflow cases in pretests? And I totally screwed up today, so this contest is awful".And today I tried this round, because I've missed live edition; after that I opened comments, saw your message and thought "yeah, he is completely right...". This is the difference between that "usually" and this case.
 » 5 years ago, # |   +7 What was the approach for Div 1 C?Only observation that I could make is following. For a fixed index i, let us say there exists an index j s.t. if we can make the entire array an valid palindrome by shuffling values of array from index range [i, j], then we can also do the same for any range [i, k] where k > j. This idea can be used to do binary search over j. But I had doubts about how to check whether shuffling of current range [i, j] can make the entire array palindrome or not?
•  » » 5 years ago, # ^ |   0 This, actually, was my exact observation as well. And I have the same question; though I believe I worked out one of the two possible cases..
•  » » » 5 years ago, # ^ | ← Rev. 5 →   +13 it can be done without bin_search: i = 1 j = 1 while(i <= n) { while(i > j || !is_it_a_good_range(i,j)) { ++j; update_set_with_bad_numbers(j); update_set_with_bad_numbers(n+1-j); } update_set_with_bad_numbers(i); update_set_with_bad_numbers(n+1-i); ++i; } How can we check given range? For every position 'p' in our range:1) we increase count[t[p]]2) if n+1-p is outside this range, we decrease count[t[n+1-p]] (unless 'p' is a middle position in whole array)In std::set let's have numbers such that count[a] is odd or negative (I call them "bad" numbers). A range is good if everything is ok outside range and:1) our set is empty, or2) our set has one number and count[this number] is positive odd number (it is possible only for odd n)
•  » » 5 years ago, # ^ |   +10 If you observe more, you would found that there are only twe basic range. Let a[1+k] != a[n-k] and for every i < k, a[1+i] == a[n-i]. So the two basic range is [1+k, g] and [h, n-k]. so you don't need to binary and just iterte over g and h.
•  » » 5 years ago, # ^ |   0 I don't understand. For a string 22134 We can rearrange range [0, 2], but not [0, 3]...
•  » » » 5 years ago, # ^ |   +8 You are rearranging a segment, but the entire string should become a palindrome.
 » 5 years ago, # | ← Rev. 2 →   +34 I guess we can say that the Div. 2 3rd place account I_have_many_girlfriends (which was likely a Div. 2 account) is a cheater (because he has many girlfriends) :P
•  » » 5 years ago, # ^ | ← Rev. 2 →   +45 Which would not be very surprising because one cannot have many girlfriends without cheating on them.
 » 5 years ago, # |   +3 I think there is problem about Div1.D and E's time limit. After solved C, I found that the basic solutions for both problems are possible to get TLE. An solution O(n^3 / 64) for C and an solution O(mlogn^2) for E. But the O(n^3 / 64) for C get Ac and O(mlogn^2) for E get TLE. So unfair to someone just as me choose E to solve~
•  » » 5 years ago, # ^ |   -13 My solution needs time, solutions with bigger complexity shouldn't pass.
 » 5 years ago, # | ← Rev. 2 →   +133 Just learnt how reading bignums and asking about j-th bit looks in Java ; BigInteger x = new BigInteger(in.next()); x.testBit(j); And in C++?????Great idea to give them in decimal, that task was surely equally hard to Java and C++ coders.
 » 5 years ago, # |   +31 Whenever the system testing is fast, the rating updates are slow! :D Whenever the system testing is slow, the rating updates are fast!
 » 5 years ago, # | ← Rev. 2 →   +11 epic bug =\ this code passed 7 tests ... set::iterator it = s.lower_bound(x); s.erase(it); upd(*it); 
 » 5 years ago, # | ← Rev. 4 →   -16 thanks savinov :)your contest has nice problem :)
 » 5 years ago, # |   +21 Approach for problem B.(Explanation from adurysk) Finding order of a permutation in a factorial representationYou can represent the order of any permutation like this. If a[0...n-1] is the given array, let la[0...n-1] be another array in which la[i] stores number of j such that j > i and a[j] < a[i] now the order of permutation a[0...n-1] will be la[0] * (n-1)! + la[1] * (n-2)! + la[2] * (n-3)! +.....you can see that la[i] < n — i similarly you can calculate the array lb[i] for the permutation b[0...n-1] now sum these two to get lc[i] = la[i] + lb[i] now at some index lc[i] can be greater than n — i, you can avoid this by shifting the carry to the index i — 1 and reconstruct the array c.Getting permutation C from the lc array.This part should be pretty easy. Go from left to right. Let us consider the situation in the beginning. At index 0, our value lc[0] denotes that precisely lc[0] numbers are less than our number at current index. So we can directly say that current number will be lc[0] + 1. So if we go to next index, we need to remember this assignment done at index 0. For that we can maintain a set of remaining numbers in permutation of size n. Now we need to find lc[i]^th the number in this set. This way we can extend the approach for any index i > 0.We can use BIT for maintaining the required set.Note: By set, I mean a mathematical notation of set, Don't confuse it with set in STL.
 » 5 years ago, # | ← Rev. 2 →   0 What was the approach for Div 1 D?
 » 5 years ago, # |   +19 Wow, dreamoon back to red in no time. Congrats!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +64 His rating is like Christian Bale's transformation.
•  » » » 5 years ago, # ^ |   0 You forgot about the American Hustle.
 » 5 years ago, # |   -7 Does anyone have properly commented solution to div1 B (it would be nice if codeforces allowed us to sort searches by the "comment concentration" of code)
•  » » 5 years ago, # ^ |   +9 When competitive programming, people aren't bothered to put comments.
 » 5 years ago, # |   0 In almost all solutions of Div.2 D / Div.1 B I see magical operation x -= x & (-x) on integer x. Maybe someone can tell what is the meaning of it? And by the way, what is the data structure used? Where can I learn more about it? For me it doesn't look exactly like a segment tree.
•  » » 5 years ago, # ^ |   +9 It is the core operation in Binary Index Tree. You can see more details and tutorial here. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
•  » » 5 years ago, # ^ |   0 It is also known as Fenwick tree
 » 5 years ago, # |   +5 What are the detailed aproaches to all questions by the writer?
 » 5 years ago, # |   +16 Why no congratulations on the winners like in other rounds? :(
 » 5 years ago, # |   0 The English version of problem statements wasn't written in proper language!
 » 5 years ago, # |   0 Codechef is busy doing Hackercup, I guess. :P Server is down.