Neon's blog

By Neon, 7 years ago, translation,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #298 (Div. 2). It will be held on Sunday, April 12 at 19:00 MSK and Div. 1 participants are invited to join out of competition.

Problems have been prepared by Maxim Mescheryakov (Neon) and Danil Sagunov (danilka.pro). We hope you'll find them interesting.

Great thanks to Maxim Akhmedov (Zlobober) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon systems and ideas of some problems. Also thanks Vitaliy Aksenov (Aksenov239) for writing solutions.

You will be given six problems and two and the half hours to solve them.

UPD: Scoring system 500-1000-1500-2000-2500-3000

UPD2: Competition completed! Thank you all!

UPD3: Congratulations to the winners!

UPD4: Editorial here

• +203

 » 7 years ago, # | ← Rev. 3 →   -14 Why minus ? When I wrote this comment, scoring system wasn't announced. Also there wasn't even a " scoring system will be announced later " message
•  » » 7 years ago, # ^ |   -27 I'm not a racist, but just because of your color :D
 » 7 years ago, # |   0 Scoring system will be announced later :/
 » 7 years ago, # |   -25 It should be Dynamic Scoring :)
•  » » 7 years ago, # ^ |   +21 So , people don't like dynamic scoring?? Every new thing is hated in the beginning :p
 » 7 years ago, # | ← Rev. 8 →   -38 Ok,you are right
•  » » 7 years ago, # ^ | ← Rev. 2 →   -20 OK. I don't have any thing to say.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -17 Ok
 » 7 years ago, # | ← Rev. 2 →   -15 :) Good luck
•  » » 7 years ago, # ^ |   -24 add me, i am blocked
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Nothing
 » 7 years ago, # |   +1 don't mind me : http://codeforces.com/blog/entry/16607
 » 7 years ago, # |   -6 I think it will be a good contest wish succes for every EXPERT
•  » » 7 years ago, # ^ |   0 Why only experts??? O_O
•  » » » 7 years ago, # ^ |   +1 They want it ...
•  » » » » 7 years ago, # ^ |   +3 XD
 » 7 years ago, # |   -21 i hope you all know who is going to win this round!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Iam sure you are the winner :P
 » 7 years ago, # |   0 Specialist Let's Muster...
 » 7 years ago, # |   0 So is there a dynamic scoring system or not? Does this mean that if I submit a 2000 point system even almost at end of contest, I get 2000 points if its accepted?
 » 7 years ago, # |   +5 I hope to participate in Round #299 with (div.1) :)
 » 7 years ago, # |   -9 six problems.Time duration 2.5 hours.
 » 7 years ago, # |   0 Coding Time
•  » » 7 years ago, # ^ |   0 yes
•  » » » 7 years ago, # ^ |   -24 There is some issue.. i m always getting wa on pretest 1.. i checked my ans
•  » » » » 7 years ago, # ^ |   -14 i m sorry.. it is my mistake.
 » 7 years ago, # |   0 GLHF guys :)
•  » » 7 years ago, # ^ |   -29 Sadly Codeforces system seems not working properly as my submission gives wrong ans before starting evaluation :(
•  » » » 7 years ago, # ^ |   -14 i m sorry,, it is my mistake
 » 7 years ago, # |   -23 The statments was very dificult to understand. problems are good but it takes very large time to understand a problem. Agree : +1 Disagree : -1
•  » » 7 years ago, # ^ | ← Rev. 3 →   +16 Disagree -1 XD It's so clear to me. But I can't solve problems. I'm a noob :(
•  » » » 7 years ago, # ^ | ← Rev. 3 →   -21 I will see you soon....... Every body, Ehsan.poursaeed wants that you give me -1 and give him +1. see his conspiracy. Don't give him +1. but if you like give me -1
 » 7 years ago, # |   +18 The pretest #15 of problem E doesn't have the visited stop list sorted. This costs me 45 minutes :( Was any one affected by this?
 » 7 years ago, # |   +8 I liked the problems :)
 » 7 years ago, # |   0 How to solve second problem?
•  » » 7 years ago, # ^ |   -11 It's dynamic programming. DP[current second][last speed]. But I spent a lot of time on understanding the statement.
•  » » » 7 years ago, # ^ |   +6 You don't need the dynamic programming. You just need to run from zero to t and update the speed using greedy approach. Check out my solution.
•  » » » » 7 years ago, # ^ |   0 Exactly. You just need to always increase the speed until it's possible to get to the required final speed in the remaining time.
•  » » 7 years ago, # ^ |   0 V increasing while we can decrease V to Vlast
•  » » » 7 years ago, # ^ |   0 I think this idea in contest,but can't implement.How to implement?
•  » » » » 7 years ago, # ^ |   0 You can see my submission. I used exact this idea :)
•  » » 7 years ago, # ^ | ← Rev. 5 →   +2 print(sum(min(v1 + d * i, v2 + d * (t - i - 1)) for i in range(t)))increase our speed as fast as we can. Also with decreasing(can't code without brackets highlighting :( and forget we need sum it, not print :( )
•  » » 7 years ago, # ^ |   0 This problem can be solved without using dynammic programming .. just traverse first from left to right and then right to left maintain minimum of both side at each second . sum them up :)
•  » » 7 years ago, # ^ |   0 if v1 + (t-1)*d <= v2, we know the best way is to increase the velocity by d every second. Otherwise, the speed would first increase to a top speed, let's say Vmax, then decrease to v2. We can enumerate the top speed Vmax to find the answer.
•  » » 7 years ago, # ^ |   +3 maintain 2 arrays of size t.first has first element as v1 and contain maximum speed that can be attained at any time by increasing previous element by d.second have last element as v2 and contain maximum speed that can is possible at any time by increasing later element by d.example- if v1=10 and v2=30, t=5 and d=4array1- 10 14 18 22 26 array2- 14 18 22 26 30add elements from array1 to answer untill array1[i]<=array2[i], then add elements from array2.
•  » » 7 years ago, # ^ |   +1 int main(){ int v1,v2; cin >> v1 >> v2; int t,d; cin >> t; cin >> d; int ans=0; while(t--){ ans+=v1; v1=min(v1+d,v2+((t-1)*d)); } cout << ans << endl; return 0; }
•  » » » 7 years ago, # ^ |   0 bayram98 could you please explain the logic used in the code ?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 you only need know how far is your v2: #include using namespace std; typedef long long ll; int main() { int rem,v1,v2,t,d;ll ans; cin >> v1 >> v2 >> t >> d; rem = v1; for(int i = 0 ; i < t-2 ;++i) { int max = v2 + (t-2-i)*d; v1 = (max > v1+d ? (v1 + d) : max); // cout << v1<
•  » » 7 years ago, # ^ |   0 i did it without dp.... simply take a array 'A' of size t; A[1]=v1; A[t]=v2;for<- 2 to t-1 A[i]+=d;and traverse from back and check if abs(A[i]-A[i+1]>d) make abs exactly d...by changing A[i];then add all A[i];
•  » » » 7 years ago, # ^ |   0 thnx, can you give correctness proof?
•  » » 7 years ago, # ^ |   +1 You can solve it by 2 pointers..
•  » » » 7 years ago, # ^ |   0 arr[0] = v1; arr[t — 1] = v2; int s = 0, e = t — 1; for (int i = 0; i < t-2; i++) { if (arr[s] <= arr[e]) { arr[s + 1] = arr[s] + d; s++; } else { arr[e — 1] = arr[e] + d; e--; } } ll ans = 0; for (int i = 0; i < t; i++) ans += arr[i];
 » 7 years ago, # |   0 How to solve D? I think that I got the idea but I had 4 unsuccessful attempts. I know that we have to change the remainders in order 0-1-2-0-1-2-0-1-2-... but maybe I implemented it wrong.
 » 7 years ago, # |   0 how to solve problem D handshakes ?
•  » » 7 years ago, # ^ |   -21 Bipartite matching !!
•  » » » 7 years ago, # ^ |   0 can you please explain the idea ?
•  » » » » 7 years ago, # ^ |   0 let's suppose the entering position are from 0 to n-1...since a team of 3 can be formed, so in general student with 'i' handshakes can go at positions i,i+3,i+6,i+9... (because additional 3's can form a team resulting in 'i' handshakes).. (make edges correspondingly to form bipartite) so Now the question reduces to bipartite maching of n students with n positions.. :)
•  » » » » » 7 years ago, # ^ |   0 Building the graph seems to work in O(N^2) at least for me. Am I missing something?
•  » » » » » » 7 years ago, # ^ |   -15 Yeah, even bipartite matching takes O((n^2)*sqrt(n)) hence ,I think this one will get tle...
•  » » » » » » » 7 years ago, # ^ |   +3 I only used DFS for this :) but didn't managed to fix it during the contesthttp://codeforces.com/contest/534/submission/10685298
•  » » » » » » » » 7 years ago, # ^ |   +4 take into account we don't need some of the structures declared... because I changed my mind during the coding and forgot to delete them
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 My kind of brute-force algorithm couldn't pass pretest 9 but I think the idea is correct.Store the people in an array of vector, where vector v[i] stores people shaking hands with i people, initialise current index of all vector to 0.Now start from 0, if current index of v[0] is less than v[0].size(), it means there is a person that can enter now.add this person to solution vector, increment 0 to 1 and repeat.If, current index becomes >= v[i].size(), then check for current index that are possible, eg. for i=7, other states possible are 7-3=4, 4-3=1 and so on.If you cant find any valid state that has current index < v[i].size(), break out of loop.Edit: The idea is correct.It passed the system test after removing a stupid bug.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Umm i seem to getting a TLE on #72. Encountered such a problem? Have a look at my post
•  » » 7 years ago, # ^ |   +8 We only need to simulate the whole thing. But, we postpone groupings as late as possible.Let's say there is X ungrouped people and next one comes. First check if there is exists (remain) a person who shake hands with X people. If yes, allow him to shake hands with X people and add 1 to current no of ungrouped people.If not, form a group and try again, no of hand shakes becomes X = X - 3. Repeat if necessary. If ultimately not possible because there is not enough people to form groups anymore, output Impossible.
•  » » » 7 years ago, # ^ |   0 Ditto approach. I seem to be getting TLE on #72. Could you have a look at my post at the bottom?
•  » » 7 years ago, # ^ |   +7 D solution:Simple greedy: take the largest numbers first, e.g. 0 1 2 3 4 5 6 7, 5 6, 2 3 4, 0 1 2.
•  » » » 7 years ago, # ^ |   0 Ok, How is about 0 1 2 3, 0 1 2 ?
•  » » » » 7 years ago, # ^ |   0 Oh, I understand. You try to increase number of people at first.
•  » » 7 years ago, # ^ |   0 I solved with greedy :D200000 stack
 » 7 years ago, # |   +22 If in Problem 'A' n=4 testcase was not included in pretests, no. of hacks could be more!!
 » 7 years ago, # |   +1 I see several people, including me, failed on system test 50 for problem C. Any idea what it may have been?
•  » » 7 years ago, # ^ |   +2 Your A must be define as a long long... I have hacked 9 people like you :)
•  » » » 7 years ago, # ^ |   0 Ah, seriously. I changed it to int when I uploaded it, since I thought it wasn't necessary and might have slown down the solution.
•  » » » 7 years ago, # ^ |   0 but there written n,A <= 2·10^5, in test 50 A is 99964566758, am I misunderstand something?
•  » » » » 7 years ago, # ^ |   0 n ≤ A ≤ s , not 2 × 105
•  » » » » » 7 years ago, # ^ |   0 I have changed all variables to long long, except n, A((. thanks
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 I think A is not necessary to take as long long, rather sum in his case. Thanks. :)
•  » » 7 years ago, # ^ |   0 You have declared sum as int, but if I give you 200000 times 1000000 as d? Then the power goes to 11. Thanks. :)
 » 7 years ago, # |   -7 I have done 4 problems and in my view, the difficulty level was C,D,A,B. Problem B just ruined my contest. -_- However, I have enjoyed the problem D very much. Thanks to the Almighty, thanks to the problem setters, thanks to all. :)
 » 7 years ago, # |   0 Can somebody explain why http://codeforces.com/contest/534/submission/10677423 submission passed test case no 50. The coder in the above solution has used int type for all the values and is still successfully dealing with large inputs. HOW? Costed me a unsuccessful hacking attempt.
•  » » 7 years ago, # ^ |   +1 X + Y — Y would always result in X even if overflow occurs.As you can see in case 50 the answers are equal to the input.
 » 7 years ago, # |   +6 Nice problem set can't wait to see tutorial of D
 » 7 years ago, # |   0 Is something with std::set solution wrong or just mine is incorrect (why?)? I got TLE on test #46 ;-; http://codeforces.com/contest/534/submission/10685572
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 you used std::lower_bound, which has linear complexityuse set::lower_bound and you get AC: 10685831
•  » » 7 years ago, # ^ |   +3 use s.lower_bound(x) instead of lower_bound(s.begin(), s.end(), x)This have been discussed many many many times in Codeforces
•  » » » 7 years ago, # ^ |   +2 Thank you so much :)
•  » » » 7 years ago, # ^ |   0 Could you refer me a blog where this has been discussed?
•  » » » » 7 years ago, # ^ |   +1 I've seen this discussion couple of times on similar situation: some guys ask why his solution fail, another reply that lower_bound(s.begin(), s.end(), x) has linear complexity. But it's hard to find comments, so I can't give you links.
•  » » » » » 7 years ago, # ^ |   0 I couldn't find anything on google search as well.Maybe we can formalise it here. So what it means is that lower_bound(), upper_bound() have linear complexity(I highly doubt that) but s.lower_bound(x) has O(logn). But I have passed programs having O(n*logn) with n<=10^6 using lower_bound().If lower_bound() is linear then complexity would have been O(n^2) (impossible to pass).Is this valid for set only or is it true for vector, array also?Is its complexity based on array configuration or what?And one more thing, as far as I know c++ stl is highly optimised. So how come lower_bound() is linear, because I sure can implement this in O(logn)?
•  » » » » » » 7 years ago, # ^ |   +11 I'm pretty sure lower_bound() is O(log) for vector and array (but of course it is assumed that the vector/array is sorted).The thing with lower_bound() on set is that, you do not have random access in O(1), so probably it was implemented in a way that makes it O(N). I think it is stupid design of this C++ STL that allows people to use the library wrongly like that.
•  » » 7 years ago, # ^ | ← Rev. 4 →   0 I have a TLE on system tests, but I used 3 smaller multimaps(each element only in one multimap, depending on shakes[i]%3 and I cycled between them) and used insert, lower_bound ( s.lower_bound) , erase, empty operations. What could go wrong? Isnt is supposed to be N*log N solution? Or is it not good enough? http://codeforces.com/contest/534/submission/10675989
•  » » » 7 years ago, # ^ |   +3 You gave link to another solution.For your D, it looks like good, but it gets TL on N=113 which is weird. I ran your solution locally and it spits error in free(). I guess it's because you access myit while lower_bound can return a.end() (so myit does not point to an element) and then you erase myit -> undefined behaviour. Very strange it gets TL on CF...Add check myit != a.end() and I hope it will pass.
•  » » » » 7 years ago, # ^ |   0 Thank you. Changing one of "Impossible" conditions from (a.empty()) to (myit == a.end()) helped. It was my first time using map, I will watch out for it in future.
 » 7 years ago, # |   -14 فارسی زبونا همیات کنین
 » 7 years ago, # |   +8 Why this solution gives WA for problem-B? Plz, help me--> 10682655
•  » » 7 years ago, # ^ |   0 When calculating DP you are setting your initial ret value to be 0. However, your recursive call can return you negative infinity, because there is no solution. Since you update ret to be a max of a previous ret value i+get(...), you lose that information. So for a state that doesn't lead anywhere, you will return 0, which is wrong. As a result, when the correct solution is 1+2+3+4+5+6+5+3+2+1, your program can do 1+2+3+4+5+6+7+8+9+0 (10 can't reach 1, so we use 0). Change line 50 from ret=0LL; to ret=-inf; and you'll get an AC :)Good luck!
 » 7 years ago, # | ← Rev. 2 →   +3 D:Different teams could start writing contest at different times. the number of student -3 or -3*t(t=1.2...) it take me long time to understand the problem
 » 7 years ago, # |   0 Where can I find the rules for the scoring? Thanks in advance.
 » 7 years ago, # |   +1 Thanks for the problems. It was a great contest with very nice problems.
 » 7 years ago, # |   +3 Can someone explain why my code for C TLEd? http://codeforces.com/contest/534/submission/10682828 Shouldn't it be O(n)? Or do you need to somehow print more efficiently?
•  » » 7 years ago, # ^ |   0 As far as I can tell you just need to switch to faster i/o methods.
•  » » 7 years ago, # ^ |   +3 Scanner.nextInt and Scanner.nextLong() is REALLY slow. You should use Integer.parseInt(sc.next()) and Long.parseLong(sc.next()). If it is not sufficient, you must implement method to parse integer.
 » 7 years ago, # | ← Rev. 2 →   0 For problem A — Exam why is the following output wrong for input 6?6 Output 5 2 4 1 3 6 Answer 6 5 3 1 6 4 2 Checker Log wrong answer Jury has better result: 6>5
•  » » 7 years ago, # ^ |   0 Because 6>5, as it says.
•  » » » 7 years ago, # ^ |   0 Found the mistake. And it's silly!
 » 7 years ago, # |   +14 When will the editorial be published?
 » 7 years ago, # | ← Rev. 2 →   0 Is there a problem with submitting? Why can't I submit now?Edit: It is fix.
 » 7 years ago, # | ← Rev. 2 →   0 I seem to be getting TLE on case #72 of problem D: Handshakes. I am using a Hashmap which stores the keys as hand shakes and indexes of people in the arraylist. Code runs perfectly. Its based on the same idea as @_spartan has written. Any optimizations?Edit: As hellman1908 suggested, the complexity increases. So i changes the ArrayList to a Stack since the order does not matter and VOILA, AC :Dhttp://codeforces.com/contest/534/submission/10687311
•  » » 7 years ago, # ^ |   +1 You remove elements from the beginning of it. In ArrayList I guess it's O(n) so total complexity is O(n2). Remove last element and it will pass
•  » » » 7 years ago, # ^ |   0 Better Still, I'll try with a stack ;)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 AC with stack :D Thanks for the hint!! http://codeforces.com/contest/534/submission/10687565
 » 7 years ago, # |   +8 Is there any editorial links for the contest? sorry if I missed one thanks :)
 » 7 years ago, # |   0 How to solve Problem 'A'?What is Logic behind it?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Adjacent elements should differ by at least two, so if you enumerate first the odd numbers and then the even numbers you have a correct solution. For example, n = 5: 1 3 5 2 4This algorithm doesn't work when n < 5. In these cases, solve it on paper and hardcode into your source.
•  » » » 7 years ago, # ^ |   0 Thanks
•  » » » 7 years ago, # ^ |   0 it is actually works n < 5 except the fourth :)
•  » » » » 7 years ago, # ^ |   0 n = 2 (1, 2), n = 3 (1, 3, 2) does not work also.
 » 7 years ago, # |   0 My accepted solution for Problem — 'C' used binary search: http://codeforces.com/contest/534/submission/10684361. As far as I can see, no one else had used binary search to solve this problem. I am not able to digest this. What obvious thing am I missing?
•  » » 7 years ago, # ^ |   +1 Probably you would do better if you think the problem in two cases: + when all the other dices do their best + when all the other dices do their worst (summing 1 each)this give you a range of points you need on the a_i dice you are working on (once at a time), and of course tells you the amount of points (or faces on the dice) that you will never see to accomplish A points.Hope this helps http://codeforces.com/contest/534/submission/10679438
•  » » » 7 years ago, # ^ | ← Rev. 5 →   0 I applied exactly the same concept as you are mentioning, if you look into my code, it's doing the same thing — finding minVals for all dices and then maxVals for all dices. To get those minVals (and maxVals), I have used binary search (and you are saying that the minVals would simply be 1 for each die). Can there not be a case when the minVal for a die be more than 1? (I could not come up with a proof that there cannot be such a case. If someone has any, then please let me know.) To be certain of the correct answer, I used binary search to get the minimum values for each die and then the maximum values..
•  » » » » 7 years ago, # ^ |   0 think about this example1 8 9I hope I am getting your point, but if you are asking for a counter example where the lower value a dice MUST have this is the easiest case, obviously your lower value is 8, so your upper value, giving you 8-8+1 possible valid dice' faces (thus 9-valid = 8 not used faces).
•  » » 7 years ago, # ^ |   0 you did the same job as others! but your time complexity is O(log(n)) and other's is O(1):D
 » 7 years ago, # |   0 Great round, I like how many variants people wrote to solve problem D, really creative.
 » 7 years ago, # |   0 In case of Problem-B it is given "the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d."and this also " Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value "so for first case is it also possible that speed will be constant after 2 second I mean 5+6+6+6=23 2nd second value change by 1 and after that speed not change could be answarAm I wrong?
•  » » 7 years ago, # ^ |   +1 You are right, but the task wants you to output maximum possible value, and your 23 is certainly less than correct 26.
•  » » » 7 years ago, # ^ |   +1 Ok I got it "maximum possible value"I missed this phrase
 » 7 years ago, # |   0 How to solve the problem F? Who can help me ?
•  » » 7 years ago, # ^ | ← Rev. 3 →   +9 Notice that in a given row there can be maximum of 10 blocks (because we have at most 20 columns, and each block must be separated from next and previous block by at least one free cell). Also notice that we can encode any tiling by m integers as bitmasks (so that 0-th bit of every integer gives us the first row, 1-st bit gives second row, and so on) up to 25. Given that, let's do dynamic programming: dp[num_placed][r1][r2][r3][r4][r5][last] = true or false. It means, that we've already filled num_placed leftmost columns, and we must build r1 more blocks in first row, r2 more blocks in second row, ..., r5 more blocks in the fifth row; and last is the bitmask of last placed column. Let's estimate number of states: 21 * 115 * 32 = 108. Not all possible states are reachable. Instead of doing dp, I've made a backtracking, because it effectively visits all reachable states, with memoization it is done only once, and with some heuristics (for example, if we must place 5 blocks in some row and there are only 3 columns left, we can say 'goodbye' to this state immediately) it works even faster. But if you prefer dp approach, the main observation here is to encode [r1][r2][r3][r4][r5] as a single integer in numeral system base 11 (because each ri have possible values from 0 to 10), that makes coding more convenient.
•  » » » 7 years ago, # ^ |   0 oh!Thank you very much.Your analysis is so distinct.And the search with memoization is more convenient to write.
 » 7 years ago, # | ← Rev. 2 →   0 In case of Problem-Cfor the case 2 3 2 3will not answar be 1,1instead of 0,1 If second dice could not show 3 then this condition also apply for 1st dice too can't show 3 also?I think then s=d1+d2+d3...dn condition will not satisfy
•  » » 7 years ago, # ^ |   0 1st dice cannot show 3 by definition: d1 = 2, so it can only show 1 or 2 (but not 3, 4, 5 or any greater value).
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 by mean defination you mean this line?"s = d1 + d2 + ... + dn."
•  » » » » 7 years ago, # ^ |   0 No, I mean second sentence from the problem: "The i-th dice shows numbers from 1 to di".
•  » » » » » 7 years ago, # ^ |   0 Got it thanks
 » 7 years ago, # |   +1 Tutorial ?!
•  » » 7 years ago, # ^ |   0 What was this word "Tutorial"?Let's hope that the author haven't posted it yet because he wants to make it more understandable and detailed :)
 » 7 years ago, # |   +5 Please anyone tell me , why this solution for problem-D is WA on test-9 ? Isn't it a correct order ?.. Sol:-> 10692139
•  » » 7 years ago, # ^ |   0 No, it isn't a correct order because if 2 shakes hands with 0 guys, then 7 will shake hands with 1 guy instead of 4 guys :)
 » 7 years ago, # |   0 Think Problem A pretests without test 5 -> Hacksss :)))
 » 7 years ago, # | ← Rev. 2 →   0 My code in problem 534D - Handshakes got AC 10687529 but when I try the test case n=5 - [0 1 2 0 4] it's output is Impossible but it should be possible 1 2 3 4 5 How come?!!!!!!
•  » » 7 years ago, # ^ |   0 No, it is impossible. If 4 handshakes with nobody, then 5 could not handshakes with 4 people. "At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. " "so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team." You assume the 1 2 3 formed a team so 4 handshakes with nobody then 5 can only handshakes with 4. So it is impossible. Sorry for my bad English
•  » » » 7 years ago, # ^ |   0 I was misunderstand this part of the problem.. thanks :)
•  » » 7 years ago, # ^ |   0 If the 4th person shook hands with 0 people, how could the 5th person shake hands with 4 people?The answer is indeed Impossible.
 » 7 years ago, # |   +1 where are the editorials
 » 7 years ago, # |   0 Please publish the editorials for the round!!
 » 7 years ago, # |   0 How to solve Problem-DI mean from where I should start?
•  » » 7 years ago, # ^ | ← Rev. 5 →   +3 First,You should count a[i]. a[i] is the number of students who shook hands i times. We define cur .cur is the number of student who we can shake hands with now. In the beginning cur=0. if a[cur] > 0 , it tells us we can add a student who will shake hands cur times in the permutation.And than a[cur]--(because we use a person) else cur-=3 (3 student start writing a contest) until (cur<3 or a[cur]>0).. 　　　2.1 if (a[cur]>0) is same as 1.　　　2.2 cur < 3 it means the sought order of students doesn't exist.My english is very poor. You can see my code 10681578..I hope you can deal with it!
•  » » » 7 years ago, # ^ |   +8 Can you explain why this solution works?
•  » » » » 7 years ago, # ^ |   0 Sorry,I can't prove it.
 » 7 years ago, # | ← Rev. 2 →   0 Here is the editorial, but for some reason it is not attached to the contest
 » 7 years ago, # | ← Rev. 2 →   0 Sorry,wrong contest.
 » 7 years ago, # |   0 hello I am tired , trying D problemsomeone can help me !!!!! why does it give me runtime error on case 46 ??? 10733747that is my code thanks for advance everyone
•  » » 7 years ago, # ^ |   +5
•  » » » 7 years ago, # ^ |   0 thanks you!!! but could you explain me ?? what happen ??current = (*it).first; s[where].erase(it);why it doesn't equals to s[where].erase(it); current = (*it).first;
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 You erase it` and after you use invalidated memory
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 I get it. thanks you !!!