### zscoder's blog

By zscoder, history, 3 years ago, ,

Important Update: Our friends have noticed that the upcoming round collides with their contest and also weekend is full of many another contests, so the round is now moved to Monday, 29 August 2016 15:05 MSK. We are sorry for the inconvenience caused and hope that you'll understand us.

Hi everyone!

Codeforces Round #369 (Div. 2) will take place on 27 August 2016 at 16:05 MSK. As usual, Div.1 participants can join out of competition.

I would like to thank dans for helping me with the preparation of the round, MikeMirzayanov for the amazing Codeforces and Polygon platforms and also Phyto for testing the problems.

I am the author of all the problems, and dans also helped making one of the problems harder. This is my first round on Codeforces! Hope everyone will enjoy the problems and find them interesting. It is advisable to read all the problems ;)

In this round, you will help ZS the Coder and Chris the Baboon while they are on an adventure in Udayland. Can you help them solve their problems? :)

Good luck, have fun, and wish everyone many Accepted Solutions. :)

UPD : Also thanks to IlyaLos and HellKitsune for testing the problems too.

UPD 2 : There will be 5 problems and the scoring is standard : 500-1000-1500-2000-2500.

UPD 3 : Editorial

UPD 4 :

Congratulations to the winners :

Div. 1 winners :

Div. 2 Winners :

• +286

 » 3 years ago, # |   +21 Timing although nice collides with Codechef lunchtime (•_•)
•  » » 3 years ago, # ^ |   +16 The time has been changed to not collide with the lunchtime round.
•  » » » 3 years ago, # ^ |   0 Now it's 3pm in timezone of most participants. Is it possible to launch round as usual?
•  » » » » 3 years ago, # ^ |   +21 You can't say "most participant". The usual staring time isn't good for some countries too. There just cannot be a starting time which is good for everyone.
•  » » » » » 3 years ago, # ^ |   -14 That's because the Earth is a sphere. However, I think the time before Russia changed the time zone will be better than now.
•  » » » » 3 years ago, # ^ |   +10 And still >7k participants. It seems there are people who like this time.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Registrants, for now. With 44 min remaining, < 4k participants.
•  » » » » » 3 years ago, # ^ |   0 Or love contest :/
 » 3 years ago, # |   +53 Since it's impossible for everyone to have a positive rating change, I wish high rating for everyone who deserves it and has been working hard.
•  » » 3 years ago, # ^ |   +30 so you are wishing low rating for the lazy ones.. :(
•  » » » 3 years ago, # ^ |   0 yes, they deserve that :)
•  » » » » 3 years ago, # ^ |   0 We are all lazy. It's why we became programmers.
•  » » 3 years ago, # ^ |   0 Not sure how you did it, but your wish has been granted in the past
 » 3 years ago, # |   +32 Good to see zscoder start writing regular rounds now. I wonder what interesting problems he has in stock.
 » 3 years ago, # |   +48 I wish not to see "unrated user" in top_10
 » 3 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 3 years ago, # |   +2 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +4 Time not collide with contest lunchtime... Please don't play with my feelings.UPD : Nevermind, Thanks for update...
 » 3 years ago, # |   +3 Could you please postpone the contest a little bit? Something like 19:00 MSK would be great for everyone, because some of us are still working at 15:05 MSK.
•  » » 3 years ago, # ^ |   +9 And another part of us are not able to participate in evening. It is like rating updates — even if everyone have solved all problems, it is impossible to increase everyone's rating. For someone it will be bad, for another it will be good
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 No, it's not like that.
•  » » 3 years ago, # ^ |   +13 19:35 MSK in my local time is 00:35,it's difficult to please everyone ：）
•  » » 3 years ago, # ^ |   +9 It is a great time for East Asia time zone though, it's roughly 21:05 over here. You can't imagine how thankful I am to see and participate a round ending before the clock hits 12.
•  » » » 3 years ago, # ^ |   0 Things are not always same.. ... I will be thankful if the contest starts after 22:00.... We all have some job to do :)
•  » » » » 3 years ago, # ^ |   0 More or less I think we can agree that starting before 00:35(the usual time) is a great idea. =D
 » 3 years ago, # | ← Rev. 2 →   -15 Is the contest delayed for 3 days or is this a bug/mistake ?
•  » » 3 years ago, # ^ |   +67 I think it's a feature.
•  » » 3 years ago, # ^ |   +13 Reading the announcement before posting a comment would be a great idea.
•  » » 3 years ago, # ^ |   +9 There is a bold Important Update which means you should read it and it's important
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 This post was made right after the time was switched. It probably done while/right after the author made the post. I believe at the time of posting it there was no update.
 » 3 years ago, # |   -19 Will problems be in russian language?
•  » » 3 years ago, # ^ | ← Rev. 6 →   -28 I think if a contest is in russian, they will say it in announcement ... and why should it be ?! author of contest is not from russia.. and a lot of people don't know russian !UPD : I am so sorry about what I said... I didn't mean something bad ... It's just because I don't know English well...
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 The problems are always translated in russian or english by the coordonator,you can read them in both languages.
 » 3 years ago, # |   +2 contest time change .....:(
•  » » 3 years ago, # ^ |   -17 Yes
 » 3 years ago, # |   +1 The first thing that I saw here was arithmetic-progression tag :/
•  » » 3 years ago, # ^ |   +19 3, 6, 9, ...
 » 3 years ago, # |   -6 Where is contest tomorrow?!
 » 3 years ago, # |   0 Thanks a lot zscoder i was just wondering how i would be able to give 3 contests with time colloiding with each other in a single day + i have an annual day also tomorrow of cse society and as last contest cost me too much -ve rating and i want to become expert again so can't afford to miss a regular round....U solved my problem and also of many i think...so thank u so much zscoder:)
 » 3 years ago, # |   -8 Thanks, Monday is better!!
 » 3 years ago, # |   0 Hopefully not a stupid question. What contests are there overlapping?
•  » » 3 years ago, # ^ | ← Rev. 3 →   -12
•  » » » 3 years ago, # ^ |   +1 Also Atcoder!
•  » » » » 3 years ago, # ^ |   +3 mentioned :)
•  » » » » 3 years ago, # ^ |   +1 Isn't it a day later?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +2 List of Contest, if someone need (^_^)
 » 3 years ago, # |   -29 Registration is opened for 3 days before contest, I think it is a special round. :)
 » 3 years ago, # |   0 Oh now I won't be able to participate anymore :( sadlife
 » 3 years ago, # |   0 "wish everyone many Accepted Solutions", that's a joke right !?
 » 3 years ago, # |   0 why change the contest to 8.29？？？？？？excuse?
•  » » 3 years ago, # ^ |   0 This is because of the many contests that are being held in this weekend (one of which clashes with the original time) so this is to allow everyone to have a chance to participate in all of them instead of being forced to choose between the clashing contests.
 » 3 years ago, # | ← Rev. 4 →   +9 your problems in educational round are always among the most interesting problems I've ever met. Hope your round will be interesting too! 710E - Генерация строки 691E - Xor-последовательности 665E - Красивые подмассивы 678D - Итерированная линейная функция
•  » » 3 years ago, # ^ |   +2 I'm glad that you like my problems :) Just pointing out that 678E - Очередной турнир ситхов is not by me but is actually by dalex. My proposal for that round is 678D - Итерированная линейная функция. Anyway, hope you enjoy this round too!
 » 3 years ago, # |   +5 Please try to give a constant time for next rounds...
 » 3 years ago, # | ← Rev. 2 →   0 hope high rating for those who deserve it and working hard. also hope less queue waiting time.
 » 3 years ago, # |   +54 this guy has 2 Bronze medal in IMO his results so...
•  » » 3 years ago, # ^ |   0 So, we should wait for lots of math problems :P
 » 3 years ago, # |   -26 Why this round delay?
 » 3 years ago, # | ← Rev. 2 →   0 1.29 August 2016 15:05 MSK.2.27 August 2016 at 16:05 MSK.3. Aug/29/2016 18:05UTC+6.Which is perfect time??????
 » 3 years ago, # |   0 Thanks for changing time :)
 » 3 years ago, # |   0 Is it possible to change it to tomorrow? On Monday at 6pm a lot of us are busy at that time.
 » 3 years ago, # |   0 Perfect timing of a contest...:-) thanks for shifting the contest.
 » 3 years ago, # |   +7 List of Contest, if someone need (^_^)
 » 3 years ago, # |   +5 Awful time. It's a middle of working day in Europe!
 » 3 years ago, # |   0 Where is our Gleb? :P
 » 3 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 3 years ago, # |   0 Great , I'm so happy , Monday I can participate !!
 » 3 years ago, # |   -20 كل تاخيره و فيها خيره :D
 » 3 years ago, # |   +12 Chinese people will be glad to participate this round. It's on 20:05! The earrrrly time means we can almost see the rating changes!
 » 3 years ago, # |   0 in the name of allah, most mercifulltime changing isn't good thing at all.
 » 3 years ago, # |   +1 I love arithmetic-progression :D
 » 3 years ago, # |   +25 can U please put the contest 2 hour later? i and 37 of my friends are in class in this time and we really want to participate in this contest! thanks!
•  » » 3 years ago, # ^ |   0 well, he can't satisfy all the pepole :p
•  » » » 3 years ago, # ^ |   -6 Why people use this argument? Is it possible to check the distribution of participants among countries and answer that question once and for all?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Fine, go ask 40,000 users about their preferred time :3
•  » » » » » 3 years ago, # ^ |   -17 Is it the only way that comes to your mind?People specify the region in their's profile. For example, you are from Lattakia in Syria. Lattakia has the time UTC+02:00 which is the same as in Moscow (I didn't know that before :) ).
•  » » » » » » 3 years ago, # ^ |   0 But Moscow is UTC+3
•  » » » » » » » 3 years ago, # ^ |   0 Yes, but current time is still the same — that is what I found interesting.
 » 3 years ago, # |   0 1*3 2*3 3*3 !!!
 » 3 years ago, # | ← Rev. 2 →   0 XD
 » 3 years ago, # |   0 Why the contest time becoming earlier day by day?? ?
 » 3 years ago, # |   +8 Keeping the previous problems in mind which are provided by the problemesetter zscoder in various educational round , i hope that today's round is going to be fantastic, wish you all positive rating change :)
 » 3 years ago, # |   0 It would be much better if you do these after 18:00 :)
 » 3 years ago, # |   0 I Wish i could be Specialist in this contest .!
 » 3 years ago, # |   +7 Again 7k+ contestants :) i hope there won't be long queue!
•  » » 3 years ago, # ^ |   +6 Probably many registered for the previous date and won't be able to attend the contest.
 » 3 years ago, # | ← Rev. 2 →   0 Contest time is so bad, I hope change it to the usual Codeforces rounds time :( (there is electricity outages in Syria in this time :p)
 » 3 years ago, # |   0 pray for being specialist .!
•  » » 3 years ago, # ^ |   0 doesn't help always . saying from experience :/
•  » » » 3 years ago, # ^ |   0 it helps i you worked hard and pray in the same time ..not just a pray
•  » » » » 3 years ago, # ^ |   +1 Doesn't help if you're an expert :p
•  » » » » » 3 years ago, # ^ |   0 I meant my "praying for becoming a candidate master" didnt work . :P
•  » » » » » 3 years ago, # ^ |   0 In fact I got a -128 instead of +11 that i needed xD
•  » » » » » » 3 years ago, # ^ |   0 Wow! *__*
•  » » » » » 3 years ago, # ^ |   +1 yes it help if you are an expert..but if you are not it won't help
 » 3 years ago, # |   +3 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 3 years ago, # |   0 we going by accepted solutions :D
 » 3 years ago, # |   +1 7.5k regitered users, hope there won't be a large queue..
•  » » 3 years ago, # ^ | ← Rev. 3 →   +1 > 8k XD
•  » » » 3 years ago, # ^ |   +6 8.3k till now, the queue will be sooooo large, I hope the servers won't break :\
 » 3 years ago, # |   +10 could you delay the contest till i finish my ice cream
 » 3 years ago, # |   +22 First round exceeds 8k
•  » » 3 years ago, # ^ |   0 Check the following ratio after the contest: .This number is more important :)
•  » » » 3 years ago, # ^ |   0 They are important both :)
 » 3 years ago, # |   0 How many people feeling lazy for contest?
 » 3 years ago, # |   +8 More than 1000 unrated users :/
 » 3 years ago, # |   +17 WOW!! 8000+ contestant already registered.
 » 3 years ago, # |   0 8385 registration !!! Is it the highest ever ? WOW... way to go CF.. Love this platform.
•  » » 3 years ago, # ^ |   0 Now is 8670 registration.
 » 3 years ago, # |   0 Very cool problems. (I liked problem C and D more)
•  » » 3 years ago, # ^ |   0 I cant solve these !! ((
•  » » 3 years ago, # ^ |   +1 I can't solve D, but my mind is same!
•  » » 3 years ago, # ^ |   0 can u please explain how to solve C and D
•  » » » 3 years ago, # ^ |   0 c dp[n][m][k], where n-the number? we want to paint, m-color,k-how pretty ! dp[i][j][x]=min(dp[i-1][j][x],dp[i-1][1..m!=j][x-1) if color[j]!=0; else dp[i][j][x]=min(dp[i-1][1..m!=j][x-1);
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +7 D:Let ans = 1 Count number of cycles and store in what cycle is a vertex. If a vertex doesn't belong to any cycle then reversing the edge won't matter so that contributes ans = ans*2 to the answerNow if there is a cycle that contains k different vertex, then you have to reverse any of its edge so possibilities are 2**k — 2 (1 for no reversal and 1 for all reversal) So ans = ans * (2**k — 2)Do this for every vertex that is not part of any cycle and for every cycle
•  » » » » 3 years ago, # ^ |   +1 Isn't it possible that when you flip edges not in a cycle you end up with another cycle?
•  » » » » » 3 years ago, # ^ |   0 No it isn't. It is a functional graph (just one edge from each vertex) So if you suppose have a edge u->v and if you reverse it to v->u then any path going through v will just stop at u and won't move any further.
•  » » » » » 3 years ago, # ^ |   0 No it isn't. It is a functional graph (just one edge from each vertex) So if you suppose have a edge u->v and if you reverse it to v->u then any path going through v will just stop at u and won't move any further.
•  » » » 3 years ago, # ^ |   0 Here is my dp solution: 20251359.I think, it's hard to explain :)
•  » » 3 years ago, # ^ |   0 Could you explain it to me?
•  » » » 3 years ago, # ^ |   0 If my solution is correct answer is Product((2^cycle_len — 2)) * 2^unused. unused = vericles outside cycle. cycle_len = length of cycle.
•  » » » » 3 years ago, # ^ |   0 i tried that and got wrong on 9
•  » » » » » 3 years ago, # ^ |   +5 Strange, mine passed pretests. Maybe you have bugs?
•  » » » » » » 3 years ago, # ^ |   +1 cycles = strongly connected components?
•  » » » » » » » 3 years ago, # ^ |   0 No, just simple cycles like 1->2->3->4->1.
•  » » » » » » » » 3 years ago, # ^ |   0 thats what i did wrong
•  » » » » 3 years ago, # ^ |   0 What is Product? And if we have many cycles?
•  » » » » » 3 years ago, # ^ |   0 There is at most 1 cycle in the graph. I just realized it post contest -_-
•  » » » » » » 3 years ago, # ^ |   +8 No, e.g. 4 2 1 4 3 There may be many but they are disjoint.
•  » » 3 years ago, # ^ |   0 Please explain how to solve those two problems
•  » » 3 years ago, # ^ |   0 Problem C : DP[i][j][k] = minimum cost to color first 'i' trees such that the color of the ith tree is 'j' and beauty is k . transitions are easy to think .
•  » » 3 years ago, # ^ |   0 how did you solved D, i tried finding all strongly connected components and then and then using formula (2^k1-2)*(2^k2-2)*....*(2^kx-2) where x is the number of strongly connected components, ki — size of the k-th component and if a component has size 1 i multiply it with 2
•  » » » 3 years ago, # ^ |   0 I came up with the same idea but got that you have to consider the opposite edges and it makes that all the vertices are in the same scc :(
•  » » » 3 years ago, # ^ |   0 Can someone confirm your solution or prove its correctness? my solution was something similar.
 » 3 years ago, # |   0 let's wait and see how many div2 B solutions will fail at test n = 1
•  » » 3 years ago, # ^ |   +10 test 4 was n=1 . so no solution would fail i guess
•  » » » 3 years ago, # ^ |   0 I think in the case 4 n! = 1
•  » » » » 3 years ago, # ^ |   0 Weird, I took care of that specific case and I got passed it immediate.
•  » » » » 3 years ago, # ^ |   0 if n==1 return 1 XD
•  » » 3 years ago, # ^ |   0 I think none, I saw like 10 solutions in my room and everyone checked for n = 1. (Maybe it was in pretests?)
•  » » » 3 years ago, # ^ |   +6 I got hacked for it
•  » » » » 3 years ago, # ^ |   0 not possible
 » 3 years ago, # |   0 How to solve E ? Wilsons theorem ?
•  » » 3 years ago, # ^ |   0 Div1E: (B - A) / B = (2N - 1)(2N - 2)...(2N - K + 1) / 2N(K - 1)The denominator (B) is a power of 2, so for it you just need to count how many 2s you need to remove both from A and B (using modular inverse!). For (B-A), you can compute it straightforwardly in a loop but early break if you get 0.
•  » » » 3 years ago, # ^ |   0 how did you come up with that ?
•  » » » » 3 years ago, # ^ |   0 It is quite straightforward. First one goes to any place, the second one can go to 2N - 1 places to avoid collision, third one has 2N - 2 free places, etc.
•  » » » » » 3 years ago, # ^ |   0 I meant how did you derive the formula ?
•  » » » » » » 3 years ago, # ^ |   0 Consider the amount of days and the chances of any two of the people in the set doesn't have the same birthday. Do some maths and you will end up with this formula.
•  » » » 3 years ago, # ^ |   0 I had the same idea but i didn't know how to find the numerator ?! how ?
•  » » » 3 years ago, # ^ |   0 Wait... but (2^N-1 % MOD)(2^N-2 % MOD)...(2^N-K+1 % MOD) doesn't have the same amount of 2s as the values that are not under %MOD right....?
•  » » » 3 years ago, # ^ |   0 why the formula is , but not , or why do we say that order here matters?
•  » » 3 years ago, # ^ |   0 I get hit by pretest 4 so I probably missed out some exceptions in my last few minutes, but I strongly believe that my approach is correct.For B, the value is (2^n)^k (before modulo 1e6+3, of course), it is not hard to prove, since there are (2^n) days and k people in the set, so this is the total case.Denote A' as B-A, this value is (2^n)! / (2^n-k)! as we consider that the days are not clashing with each other.To calculate A', you can just use a for loop from (2^n-k+1) to (2^n) to get the value, note that since MOD = 1e6+3, when you hit something that is divisible by MOD, just return 0.The only part I failed is to make A' co-prime with B by counting the 2's in the for loop, but note that I am using values that are under modulo MOD so the amount of 2's are not exactly correct.
•  » » 3 years ago, # ^ |   +9 The combinatoric(probabilistic) problem wasn't too hard.Answer is The real problem i think is compute this value modulo mod.Notice than when k >  = mod the term that involves factorials is equal to 0, so answer isn't that hard in that case, but remains the problem of reduce the fraction. The only prime factor of the denominator is 2, so you need to find the biggest p such that 2p divides the numerator. Then multiply both num and den for the multiplicative inverse of this number and voila...
 » 3 years ago, # | ← Rev. 2 →   +14 Hats off to zscoder for such an awesome problemset, especially problem D :)
•  » » 3 years ago, # ^ |   0 can you explain your solution?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 For each component of the graph, because it has x vertices and x edges, there exists exactly one cycle. In this cycle, by switching edges, the only way you can end up with another cycle is if you don't switch any edges, or you switch all of them. So if the cycle has y vertices, you have (2^y — 2) valid sets of edge switches. And it's not hard to find the cycle length with a simple dfs.You can also notice that for every other edge it doesn't matter if you switch it or not, so for a component of size x with a cycle length of y, the answer is (2^y — 2) * 2^(x — y). All that's left is to multiply the answers for every component of the graph.Hope I helped. Edit:Complexity is O(n)
•  » » » » 3 years ago, # ^ |   0 Wow! It was one of those problems where the difficult part is that you have to make important observations and the rest is easy.
•  » » 3 years ago, # ^ |   0 How to solve D? My solution used strongly connected component. Got WA in testcase 4 -__-
•  » » 3 years ago, # ^ |   0 Could you explain yours? I tried to find the cycles with some special properties of the problem within the designated time but can't find the solution :(
 » 3 years ago, # | ← Rev. 5 →   0 I solved A , B in 16 minutes and didn't solve C. It seems like it is very easy as a lot of people solved it. But how did you handle something like that ? (3 3 3)(0 0 0)(1 200 200)(1 1 1)(1 200 200)With my approach it was so hard to be handled because after the putting the colors that will give me the minimum cost I start to change the current beauty to be beauty + 1 or beauty -1 in every step until I reach set == k.But this case will require from me to change the beauty by 2.
•  » » 3 years ago, # ^ |   0 dont really know what you mean by "set" , but it can be solved by dynamic programming .
•  » » » 3 years ago, # ^ |   0 I thought about solving it with DP , but the problem was that I need to save which colors I have used so Far which cannot be saved as it will be 2 ^ (colors)
•  » » » » 3 years ago, # ^ |   0 You can use each color multiple times.
•  » » » » 3 years ago, # ^ |   0 For an index i, you only need to know what color was on i-1 index. So you could do dp with (n, no of segments, lastcolor) as states. You can choose any of noofcolors for index i if it is not colored.So complexity: O(n*segments*color*color)I just hope it don't give tle if there are no prunings done :|
•  » » » » 3 years ago, # ^ |   0 Thank you very much , I understood something wrongly :)
•  » » » » 3 years ago, # ^ |   0 You only need to store the color of the last element to know if you increase the number of groups or not.
 » 3 years ago, # |   +8 Couldn't submit D because the servers were slow during the last 60 seconds ;_;
 » 3 years ago, # |   -14 *Reads Problem E*Notices a way to calculate large factorial is needed*Ready to rant for requiring knowledge about an algorithm that I probably won't need it again.*Notices that since MOD is only 1e6+3 so things could be simplified at the last minutes*QWERTYUIOPLKJHGFDSAZXCVBNM obviously didn't coded quick enough and failKeep on observing till the last moment guys... This is a pretty decent problem set anyways, I'm lovin it. =]
 » 3 years ago, # |   +5 What was pretest 7 at D?
 » 3 years ago, # |   +1 I tried to hack this 20246021 twice, as it uses int but he gives the correct output and no overflow happened!!could anyone explain why that happened?!
•  » » 3 years ago, # ^ |   0 Your hack is wrong, I guess. Operations on 32 bit integers normally wrap around. Can you share your hack with us?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 the 1st hack the 2nd hackwhat do you mean by "Operations on 32 bit integers normally wrap around", could you explain that?
•  » » » » 3 years ago, # ^ |   +3 Take a look at this. Normally the result of addition, subtraction and multiplication on ints will still be correct modulo 232. And if the final solution is less than 231, the calculated value will be correct.The problem with the second code is that the compiler is able to deduce that the loop will result in undefined behavior, so the compiler can basically do whatever it wants. In the first code, the compiler cannot deduce anything (because of user input) and no weird "optimizations" will occur. The machine code generated will simply use the ADD x86 instruction (or perhaps the MUL instruction), which on x86 produce the correct result modulo 232.I warned everyone not to expect such crazy undefined behavior (for example when hacking solutions) but I got booed off
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +6 100 536870913 536870913 536870913 536870913 536870913 536870913 536870913 536870913 1536870913 1 536870913 536870913 536870913 536870913 536870913 536870913 1 536870913536870913 536870913 1 536870913 536870913 536870913 536870913 1 536870913 536870913536870913 536870913 536870913 1 536870913 536870913 1 536870913 536870913 536870913536870913 536870913 536870913 536870913 1 1 536870913 536870913 536870913 536870913536870913 536870913 536870913 536870913 1 1 536870913 536870913 536870913 536870913536870913 536870913 536870913 1 536870913 536870913 1 536870913 536870913 536870913536870913 536870913 1 536870913 536870913 536870913 536870913 1 536870913 536870913536870913 1 536870913 536870913 536870913 536870913 536870913 536870913 1 5368709131 536870913 536870913 536870913 536870913 536870913 536870913 536870913 536870913 1This is the case I found.
•  » » » » 3 years ago, # ^ |   0 Would it be possible to get test case #117 for this problem? My solution for some reason did not pass it :(submission/20233549
 » 3 years ago, # |   0 I figured out the solution for problem D. Unluckily couldn't complete the code on time.It is easy using DFS to find the number of edges that form the circle, let's name it cEdge.Notice that if we choose the sets that contain the circle edges, after flipping, the circle remains.So the answer = Number_of_all_subset — Number_of_subset_doesn't_contain_all_circle_edge = Pow(2,n) — 2*Pow(2, n — cEdge).It this solution were right, I would be a little bit sad. Cause this is the first time I was this close to problem D.
•  » » 3 years ago, # ^ |   +4 You're correct, but note that you can have multiple weakly connected components and thus multiple circles: 4 2 1 4 3 
•  » » » 3 years ago, # ^ |   0 Thanks. Found my bug.
•  » » » 3 years ago, # ^ |   0 Ah, couldn't have thought of it. My formula now becomes more complicated. Thanks for pointing it out
•  » » 3 years ago, # ^ |   0 It's right, but you need to do this not once, but for every connected component of the graph, and multiply these answers.
 » 3 years ago, # |   0 Please help me with the second question (Div. 2) and tell me what I did wrong? http://ideone.com/6HDQwQ
•  » » 3 years ago, # ^ |   0 your solution gives -1 in : 1 0
•  » » 3 years ago, # ^ |   0 Check:33 3 33 0 33 3 3answer is 3, you are printing -1
 » 3 years ago, # |   0 Wasted a lot of time on B and C, I think I could have solved D if I was a little faster :(
 » 3 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 3 years ago, # |   0 i spent all the contest to figure the wrong answer on pretest 4 in B .after 1:55 i figured that i didn't do that if(n==1) print(1) ; return;
 » 3 years ago, # | ← Rev. 2 →   0 Almost everyone has implemented a O(n^4) dp for problem C,I just hope it doesn't pass else it would be very unfair..how could 10^8 iterations pass...there are many problems on codeforces where a similar complexity has given TLE.
•  » » 3 years ago, # ^ |   -12 It's a Div2C for a reason man.
•  » » » 3 years ago, # ^ |   0 I can show a variety of Div-2C problems where such a complexity has given a TLE, MAN!!!
•  » » » » 3 years ago, # ^ |   0 Calm down. I mean it is not meant to be extremely challenging.Sorry if you feel that you are offended by my previous comment.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Send me problems where there is no high constant factor, and 10^8 fails on CF servers.(No sarcasm intended). 10^8 just always pass.
•  » » 3 years ago, # ^ |   +5 TLE: 2 seconds. Also codeforces servers are pretty fast + almost no constant factor.The only thing i worry is all operations are on long long int though
•  » » 3 years ago, # ^ |   0 usually you can pass 10^8 iterations! you can even 10^8 * 5 of them! but I think there is a O(n^3) dp!
•  » » » 3 years ago, # ^ |   0 There is indeed an O(nmk) solution.
•  » » » 3 years ago, # ^ |   0 Yes, the inner loop iterates on colors. When you want to break the previous group and start the new one, you need to compute the two minimum costs over all possible colors of the previous group. And then iterate again on possible colors of new group and use one of the two minimum costs.That is, you make two consequent loops instead of two nested.
•  » » » » 3 years ago, # ^ |   0 ...and I didn't have the balls to do the extra work, and I still failed regardless of the optimization.
•  » » 3 years ago, # ^ |   0 Didn't actually try O(n^4). I thought it might blow up. So I tried for MORE THAN AN HOUR to bring the complexity down to O(n^3). (Using subtle techniques. Thus difficult to debug.) Consequently, I didn't have time for Problem D and E.
 » 3 years ago, # | ← Rev. 2 →   0 Don't know if in 2 seconds, the Codeforces's system can run in O(1e8). But if it could, here is my solution for problem C.Using DP Let's call dp[i][j][k] = the minimum cost after we color the i-th with k-th, so that we can get j beauty of coloring.Formular: At each i-th tree, we can color it and i-th tree with the same or different color. if (c[i] != 0) dp[i][j][k] = min(dp[i-1][j][c[i]], dp[i-1][j-1][t]) where t = 1..m, t # c[i] if (c[i] == 0) dp[i][j][k] = min(dp[i-1][j][k] + p[i][k], dp[i-1][j-1][t] + p[i][t]) where t = 1..m, t # k
 » 3 years ago, # |   0 Can anyone explain C ?
•  » » 3 years ago, # ^ |   0 Use a dp arraydp[tree][color][set_count]Just handle the transfer between states carefully and you are set. (Note that the constraints are VERY small)
•  » » » 3 years ago, # ^ |   0 Can it run in O(1e8) ? I used 4 for loop. Hope it'll pass
•  » » » » 3 years ago, # ^ |   0 Yes, it's fast for cf
•  » » » » » 3 years ago, # ^ |   0 normally what's the limit?
•  » » » » » » 3 years ago, # ^ |   -10 It's about 1e9/s. Usually TL won't be that tight since there are constant factors so consider 1e8/s.
•  » » » » 3 years ago, # ^ |   0 I remember, when i can't hack solution with 1e9 operations!
•  » » » » » 3 years ago, # ^ |   +1 That is true — "1e9" takes here around 1s (anyway it depends on complexity of operations)Some simple iteration + summing would do that, anyway I doubt 1e9 load/store operation would be that successful.Anyway 1e8 shall be OK with much complex operation (especially considering it might be considerably reduced by a constant)Have nice day ^_^
•  » » » » » » 3 years ago, # ^ |   +5 Thanks, you too!
•  » » » » » » 3 years ago, # ^ |   0 How can we know in general the number of iterations we can do ? For instance 1GHz means how many iterations ? Thanks :)
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Do you know asymptotic(o())? So the number of iterations is the max possible asimptotic! As example, if n=1000 and o(n^2) then number of iterations near 1000000
•  » » » » » » » » 3 years ago, # ^ |   0 If you mean time complexity yes I know. I was just asking how can we know in general how many iterations we could do. Because here I had the solution for C in O(nkm^2) but I thought that I could do only 10^6 operations so I didn't even try to submit it
•  » » » » » » » » » 3 years ago, # ^ |   0 Here you can make above 2e9 primitive operations!
•  » » » » » » » » » 3 years ago, # ^ |   0 Thanks.So what is a primitive operation ?For instance addition, comparison,.. are worth how many primitive operations ?
•  » » » » » » » » » 3 years ago, # ^ |   0 =,+=,-=,*=,&,|,^,-,+,*,<<,>>,all comparison! I think it's all
•  » » » » » » » » » 3 years ago, # ^ |   +1 Thanks !
•  » » » » » » » » » 3 years ago, # ^ |   0 You're welcome!
 » 3 years ago, # |   0 http://codeforces.com/contest/711/submission/20254708 Some one please tell me why this timed out ?
•  » » 3 years ago, # ^ |   +13 Good day to you,it became "stuck" in your "do-while" cycleTry following input 5 2 3 1 1 4 Good Luck ~ Have nice day
•  » » » 3 years ago, # ^ |   0 Thanks , and good day to you to sir .
 » 3 years ago, # |   +1 Rant: Hate it when forgot to uncomment a line that i commented out during debuggingBut atleast it shows up in pretests xD and i could fix it :D
 » 3 years ago, # |   +15 C was the first DP problem that I've solved during the contest thank you zscoderself-confident level is rising.
•  » » 3 years ago, # ^ |   +4 Same here :D
 » 3 years ago, # |   +8 Finally, I am going to be blue! :D
 » 3 years ago, # |   +1 Problem B was so tricky
 » 3 years ago, # |   0 Pain is solving 4 problems and then getting "WA on 105" _/_
 » 3 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 3 years ago, # |   0 Can someone tell why did I get WA on 105.http://codeforces.com/contest/711/submission/20244876Its not clear from the test case what's wrong.
•  » » 3 years ago, # ^ |   0 Not sure if that's the reason.But here you call answer by reference, but you don't save it in the memo table in the first if condition. I think this should cause TLE and not WA though.
•  » » » 3 years ago, # ^ |   0 Yups I saw that. But WA isn't the outcome of it.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +7 It looks like your submission is being re-judged ? It's re-running test 1 again. Edit : It is accepted. I guess that makes you x100 happier now. Congrats!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +17 Rejudged. Congrats! Ratings will be adjusted tonight.
•  » » » 3 years ago, # ^ |   +30 Thanks. I almost cried seeing your comment.
•  » » » 3 years ago, # ^ |   +3 What was the reason behind it Mike?
 » 3 years ago, # |   +1 Can someone tell me what's wrong with my code? 20239552
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 You are doing a[x][y]=(r[(x+1)%n]-r[x]); what if 0 is in last row. r[x + 1] = 0 in that case.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 If 0 is in the last row, I simply take the sum of the first row to be the (standard) sum to which all other sums are to be compared with. Am I missing something? UPD: Also, in the input which is giving WA, the 0 is in the first row and first column.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 vector< long int> r(n),c(n);should be vector< long long int> r(n),c(n);long int d1=0,d2=0,s=0;should belong long int d1=0,d2=0,s=0;Those sums can reach 500*10^9=5*10^11 which overflows 32-bit integer. UPD:a[x][y]=(r[(x+1)%n]-r[x]);t=a[x][y]also causes overflow.Change it to t=(r[(x+1)%n]-r[x]);`
•  » » » 3 years ago, # ^ |   0 Thanks. I had always thought that long and long long were same. Stupid me.
 » 3 years ago, # |   +1 Yes!!!! Specialist finally...next target :- Expert
 » 3 years ago, # |   +3 O(n*k*m^2) in C! Really? 10^8? I didn't believe that it will pass all the tests and wrote something strange... Now I don't understand how my code passed pretests. Anyway, problems were very nice. Thank you
•  » » 3 years ago, # ^ |   +3 10^8 with simple operations can pass with only 1s they gave you 2 seconds anyway, if they want you to solve it in o(n^3) complexity then they would give 500 for n and just 1 second
•  » » » 3 years ago, # ^ |   0 I didn't know this before. It is usual for me, that test system can't pass more than 10^7 operations, so it was a good lesson :-)
 » 3 years ago, # |   0 I like the problem c,my dp is weak.i didn't solve it in contest,the problem c help me improve my mind,and the time is really really nice, thanks a lot
 » 3 years ago, # | ← Rev. 2 →   0 Hi.This is about Problem B. I'm stuck at the test 93, and the test data is:31 15 511 7 39 0 13The correct answer is 1. However I think the answer should be -1.Could anybody explain this for me? Thx.
•  » » 3 years ago, # ^ |   0 Nope.Sum across second diagonal = 21Sum in last row = 23 Maybe wrongans = abs(stdSumI — tSumI);
•  » » » 3 years ago, # ^ |   +1 Wow...Sorry...I submit the wrong file after the contest...
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 The correct answer is -1. As can be seen in 20259409
•  » » » 3 years ago, # ^ |   +1 Wow...Sorry...I submit the wrong file after the contest...
 » 3 years ago, # |   0 Problem C I though n*k*m^2 couldn't pass so I didn't do the solution. New lesson of analyzing bigO notation
 » 3 years ago, # |   0 Problem B :Were there test cases such that the square is already a magic square and hence you have to print a -1 straight away ?
 » 3 years ago, # |   0 I have a tendency of writing recursive solutions for DP problems. Will that be cause any problem in near future? Here is my accepted solution for DIV 2C (Complexity O(NKM2)). Can anyone help how to modify the same recursive solution so that complexity is reduced to O(NKM).
•  » » 3 years ago, # ^ |   0 I have been told that it is always better to have an iterative code because it is easier to make sure you don't compute the same thing twice and you can have stack overflow with a recursive function. But I am no expert if someone knows it better ...
•  » » » 3 years ago, # ^ |   +13 Good day to you!I think it is (in MOST cases) up to you [what fits you better].The advantages of "iterative" method are, that is is faster (by a constant — not that much but it is SOMETHING).The "stack problem" is usually on, only if it is "1D" Dynamic Programming with N greater than 10^5 — anyway it can be prevented by executing DP a few times (you can execute the recursion with 10^5,2*10^5,3*10^5...etc in a loop, so there won't be more than 10^5 depth {or you can do this with custom depth — it doesn't cost any asymptotic complexity :) })The same thing will never be computed twice (in any of the methods), anyway a "thing" might be asked more than once in recursive form (anyway as it is computed it ends in O(1) )I (personally) prefer recursive method over iterative [it is easier for me to see the solution] — but as I said, it is personal matter.An advantage of recursive DP is, that it is more easy to do a DP, in which the whole "state-space" doesn't fit into array, but you will use only "part" of it [with assist of "map"]. Also it is more easier, whenever the parents are somehow "variable" — not fixed :)So the asymptotic complexity of both methods is same, and most of the things can be (somehow) converted to other method to make it working — so unless you are (for a reason) hunting every "ms", then it is only matter of personal preferences!Good Luck & Have Nice Day :)
 » 3 years ago, # | ← Rev. 2 →   0 nice
 » 3 years ago, # | ← Rev. 2 →   +5 Is there a bug in the contest ?!Rating changes are removed !! zscoder MikeMirzayanovUPD : The bug is fixed now.
•  » » 3 years ago, # ^ |   0 My rating changes are returned. :) You can try to refresh the pages.
 » 3 years ago, # |   +4 did the round become unrated ?! or is it just a bug ?
•  » » 3 years ago, # ^ |   0 No Man Sorry
 » 3 years ago, # |   +5 11 days till the next contest !:/
•  » » 3 years ago, # ^ |   0 Great, now at least my exams will be over :D
•  » » 3 years ago, # ^ |   0 and it collides with icpc first phase in south america :(
 » 3 years ago, # |   +1 it's really frustrating that next contest is 10 days away.