Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### jzzhu's blog

By jzzhu, 6 years ago, ,

Hello everyone! Codeforces Round #257 is coming soon.

In this round, you are going to meet our friend Jzzhu. Though my id is jzzhu, the real Jzzhu isn't me, and he is a very cute boy. Now he is facing some challenges. Can you help him to solve the problems?

The problem setters are yc5-yc and me, and thank ydc, jzc, fanhqme for testing.

Many thanks to Gerald for helping to prepare the round. Also I'd like to thank MikeMirzayanov for creating such a good platform.

Have a good time with Jzzhu!

UPD

In Div. 1, scores for each problem will be 500-1000-1500-2000-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2000-2500.

UPD

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

1.semiexp

3.rowdark

4.WJMZBMR

5.mruxim

Division 2:

1.swenyoo

2.chm517

4.TBH

You can find editorial here.

• +225

 » 6 years ago, # |   +9 Wow! Another Chinese round!
•  » » 6 years ago, # ^ |   +40 But Codeforces Round #256 (Div. 2) was a combobreaker :D
•  » » » 6 years ago, # ^ |   0 Another combobreaker is just coming =D
•  » » » 6 years ago, # ^ |   +37 a Div-2 only round cannot actually be called a combobreaker :DStill, Div 1 rounds are all Chinese :D
•  » » » » 6 years ago, # ^ |   0 That combobreaker will also come soon :)
•  » » 6 years ago, # ^ |   +6 I think the reason of the continous Chinese Rounds is Stand Alone Complex ( a name of a interesting phenomenon in Ghost In The Shell TV version ).
 » 6 years ago, # |   +32 chinese round month.. and maybe xiaodao's round will be come out this month
•  » » 6 years ago, # ^ |   -22 I hope not :(
•  » » » 6 years ago, # ^ |   +9 Gold Bear!!!! Amazing!! I feel surprise to see such amazing id in codeforces
•  » » 6 years ago, # ^ |   +5 I have thought the #257 is xiaodao's round..... Wish his round come soon~ And the multi-university training come soon~
 » 6 years ago, # | ← Rev. 2 →   -28 jzzhu != jzzhu ("the real Jzzhu isn't me")
 » 6 years ago, # | ← Rev. 3 →   +21 I like Chinese rounds because it starts early, but Div1 E is always too hard :v
•  » » 6 years ago, # ^ |   +74 Seriously, Are YOU talking about Div1 E?
•  » » » 6 years ago, # ^ |   -14 Yes, although I'm at Div2 :v
•  » » » » 6 years ago, # ^ |   +10 i cannot see a E Accepted by you either div2 or div1 :D
•  » » » » » 6 years ago, # ^ |   +20 Yeah, I'm still a noob D: I will try my best to improve D:
•  » » » » » » 6 years ago, # ^ |   +12 That's the spirit :D
•  » » » 6 years ago, # ^ |   +10 seriously , why a Div2er like me can't talk about div1E ?
 » 6 years ago, # |   -83 Chinese round, Interesting.
•  » » 6 years ago, # ^ |   -166 Why do you idiots give me negative points? Fucking shit.
•  » » » 6 years ago, # ^ |   -146 You are a Fucking shit.
•  » » » » 6 years ago, # ^ |   -160 Look at ur poor rating, WOW such a idiot! Do you think you "Expert" have the right to scold me?
•  » » » » » 6 years ago, # ^ |   -61 Look at your poor minus contribution, WOW such an idiot! Do you think you "Jackass" have the right to leave a comment?
•  » » » » » » 6 years ago, # ^ |   -98 You life quality depends on your skills (your rating replies parts of it), but not on the fucking voting system. Just idiots with blue or green or even less like voting all the time, because they do not have the ability to solve problems HAHA!
•  » » » » » » » 6 years ago, # ^ |   0 Well, I downvoted all of your comments here except the first one (not because I like it, just because I don't care). Also, if I was a mod, I'd ban your sorry ass into the worst corners of Internet! What do you say to that?
•  » » » » » » » » 6 years ago, # ^ |   -63 I would say you are just a fucking shit.
•  » » » » » » » » » 6 years ago, # ^ |   +74 Suddenly quiet about rating, are you?
•  » » » » » » » » » 6 years ago, # ^ |   +47 Why are you guys quarrelling about nothing?
•  » » » » » » » » » 6 years ago, # ^ |   -20 Nah, I'm just teasing him :D
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -19 Let's solve problems.
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +18 This is codeforces but not /b/
•  » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   -9 Hey, Of course having strong communication is a skill and if you can call it "fucking voting system", It's much easier that call ratings "the fucking ratings system". But something makes me think, Your rating is just 1766 and just with 2 contests that is shows there is not stability in your rating necessarily but you are this kind of proud of your self and self-conceited. I hadn't seen even tourist speaks like that.
•  » » 6 years ago, # ^ |   +5 Seems that Chinese rounds are interesting, but you guys are more interesting! 233333333333
•  » » 6 years ago, # ^ | ← Rev. 2 →   -17 _
 » 6 years ago, # |   +2 It is the third contest which I can not participate because of IOI's schedule. When this contest started, we was on the bus.I can't participate last 2 contests too, because I must sleep enough to participate IOI contests.
•  » » 6 years ago, # ^ |   +6 Best wishes~! Gl&&Hf in IOI~!
•  » » » 6 years ago, # ^ |   +1 Thanks. I won a Bronze medal.
•  » » » » 6 years ago, # ^ |   +1 Is it the last IOI that you can participate? If you were born in 1997 according to you id, you may participate in ACM-ICPC next year~
•  » » » » » 6 years ago, # ^ |   0 Yes, I have another chance.
 » 6 years ago, # |   +7 Another chinese round. I like chinese rounds because it can involve math and sometimes good problems.
 » 6 years ago, # | ← Rev. 3 →   +34 A Fermat prime number round! For more info about Fermat theory, click here. It's a theory about prime numbers that are a power of 2 added by one.
•  » » 6 years ago, # ^ |   +13 Hah, came here to say that we should celebrate that round, because that is surely last Fermat's prime number round in our lifes :P. Rounds FF, then 100000000, then 2^2^3 + 1, which is Fermat's prime. Nice combo. Does anyone know interesting properties of 258 :P?
•  » » » 6 years ago, # ^ |   +13 Depending on what's interesting:Wolfram Alpha says that it divides 85^2+1. And its prime factorization is quite simple.OEIS gives just 1 interesting result: the number of Delannoy paths from (0,0) to (4,4) that don't start with a (1,1) step.The worse thing is that we'll probably never get rounds 109 + 9 and 109 + 7. In any base.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +74 Since Codeforces round 255 everyone is finding an interesting thing about the contest number and it remembered me something! Few months ago, our teacher proved us that every number has a interesting properties! For example 1 is the first number, 2 the first even number, 3 the first prime odd number and so on. And the prove: Assume that it's not true! So, spot the first number that has no interesting properties, This is an interesting properties itself!
•  » » » » 6 years ago, # ^ |   0 cool)
•  » » » » 6 years ago, # ^ |   -9 This seems familiar to me, may you name the teacher?
•  » » » » » 6 years ago, # ^ |   0 Mr.Mirjalali
•  » » » » » » 6 years ago, # ^ |   0 Thanks!
•  » » » » 6 years ago, # ^ |   0 Is your teacher name َ"Ali Ghasaab" :)? He knows me very well :) give my regards to my best ever teacher...
•  » » » » » 6 years ago, # ^ |   0 No, But he was my teacher 3 years ago.
•  » » » » 6 years ago, # ^ |   0 It reminds me of a theory like this: every number can be named not more than 50 chars. The proof is similar: if there exists a number that cannot be named less than chars, it can be named as "The first number cannot be named in 50 chars". It is 44-chars name.
 » 6 years ago, # | ← Rev. 2 →   +150
•  » » 6 years ago, # ^ |   -25 hard contest or easy!!!
•  » » » 6 years ago, # ^ |   +19 Yes. Or medium.
• »
»
»
»
6 years ago, # ^ |
-61

# 256؟؟

•  » » » » » 6 years ago, # ^ |   -40 ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็What, are we having a contest in posting random stuff?
•  » » » » » » 6 years ago, # ^ |   -37 what???are you seying!!! ???
•  » » » » » » » 6 years ago, # ^ |   0 No, that should be my question. When your post only contains a number and 2 weird characters, I can only reply in kind. Except my weird characters break through comments :D
•  » » » » » » » » 6 years ago, # ^ |   -15 ok thank you very much
 » 6 years ago, # |   +19 Chinese here, Chinese there, Chinese everywhere :P after these 3 contests my mom will see me just like JACKIE JOHN
 » 6 years ago, # |   -9 soga=-=have fun!!
 » 6 years ago, # |   +6 hope an easy contest! :)
 » 6 years ago, # |   +2 Chinese round again.I'm glad to see it.RP++
 » 6 years ago, # |   -11 just Ten minutes remain but a problem rush in my mind: But i will be glad if any of you answer my question : http://codeforces.com/blog/entry/13102
 » 6 years ago, # |   +5 I like Chinese round! Good luck and have fun for everyone!
•  » » 6 years ago, # ^ |   0 Especially with standard score
 » 6 years ago, # |   0 what's the problem with hack???
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 div2 B with 1000000000 -10000000003
•  » » 6 years ago, # ^ |   +3 For Div2, Problem B. A lot of participants didn't noticed that (x-y) can be less than -(10^9+7).
 » 6 years ago, # |   0 Great round! I submitted three. Hope they pass systests!
 » 6 years ago, # |   +5 Any hint on C except for Blossom Algorithm? Nice round anyway.
•  » » 6 years ago, # ^ |   0 I think we can do a bipartite matching using dinics etc. Too bad I couldn't implement it during contest though :(
•  » » » 6 years ago, # ^ |   +1 I thought of that too, but how would you be sure that if A-B was chosen (like A in the first set, B in the second), B-A won't be?
•  » » » » 6 years ago, # ^ |   0 Yes, you are right. Maybe this is not the intended way. Now I too am confused.
•  » » » » 6 years ago, # ^ |   0 you can consider only the edges that connect a smaller number to a bigger one (not vice-versa)
•  » » » » » 6 years ago, # ^ |   0 I think that it still won't work this way. Think about connecting A-B and B-C (both of them forward edges).
•  » » 6 years ago, # ^ |   +4 I used sieve of Eratosthenes.
•  » » 6 years ago, # ^ |   0 Since you want a hint: Greedy. And prime sieving, yes.
•  » » » 6 years ago, # ^ |   +15 I solved it in a greedy way — by "solved" I mean it got accepted. But I have no idea why it is correct. If you know why, can you write why it works? Thanks
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +60 Here's a quick proof:Clearly we cannot do anything with primes greater than . (Let be a prime, then it can only be matched with an apple with number at least 2p. But 2p > n. So we cannot match p.) We can't do anything about 1 either, and if there are an odd number of apples remaining, we must remove one (since all groups have two apples and thus the total number of apples used is even). My solution makes sure that all the remaining apples are matched, which due to the above proof, is maximum.My solution works as follows: Generate all primes below n and reverse the order, so we process from the largest prime. For each prime p > 2, observe the apples p, 2p, 3p, ..., kp where kp ≤ n < (k + 1)p. We ignore all apples that have been used before. Now, greedily take the two apples with largest numbers together. In the case we are left with a single apple p, then observe that 2p must be used in the previous group. Replace it with p, so we keep 2p to be used later in the final pass. Finally, for prime p = 2, we greedily match every even apples remaining. It shouldn't be hard to see that all apples not in the form 2p or 2 k are used in step 2, and all remaining apples (except probably one) that are not used in step 2 are used in step 4.
•  » » » 6 years ago, # ^ |   +8 Sorry for double post but... Chaotic_iak, you made over +500 in less than two months! Amazing progress, my huge congratulations :)
•  » » » » 6 years ago, # ^ |   +9 Thanks! I think that's because the problems I did fit with my ability, and the remaining problems I didn't do are hard enough that not many other people did those. :P
 » 6 years ago, # |   +35 very WEAK pretests....I'm really afraid of systests...
 » 6 years ago, # |   +5 all problems was tricky thanks
 » 6 years ago, # |   0 what was to be done in div-2 C ....
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 The solution doesn't exist if k > n + m - 2. In the ideal case, after making k cuts, the remaining pieces have equal area. Sometimes, this is not possible.First, try to make only vertical cuts in the best way (i.e the minimum area is largest). If k < n - 1, we will have ⌊ m / p⌋ columns in the minimum area. So area is that number multiplied by n. Same way try to make only horizontal cuts.In some cases we cannot make only horizontal or only vertical cuts, so we have to do both. Which one to do first? Try both possibilities, i.e. first vertical then horizontal and then first horizontal and then vertical, and then print the maximum resulting area (of the smallest piece) as answer.My solution: 7171855
 » 6 years ago, # |   0 What is the approach for DIV2 D ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I used Dijkstra algorithm to find the shortest paths from the capital to every city. Then I destroyed the trains which aren't used in the various shortest paths. I'm not sure, however, if this works.
•  » » 6 years ago, # ^ |   0 Nevermind I got WA
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Dijkstra... When we finish it, we must calculate unused train roads.. And if we have a choice what type of road to use we must use not-train road..
•  » » 6 years ago, # ^ |   0 You can use Dijkstra to determine the number of trains are used in the shortest paths from the capital to the other cities. Plus a little modification that if you can reach a specific city as fast as the train, you pick the road not the train.
•  » » 6 years ago, # ^ |   +1 If you need it, here there is my fixed code: http://codeforces.com/contest/450/submission/7179339
 » 6 years ago, # |   +32 Problem D is very well known. Have no idea where the tester was looking at. Also naive solution works 3.3 seconds on Java, while TL is 2 seconds. I guess, one may got AC with the same written in C++...
•  » » 6 years ago, # ^ |   +8 What kind of naive solution do you mean? dp[n][mask] ?
•  » » » 6 years ago, # ^ |   0 I mean 3^(log2(n)) solution.
•  » » » » 6 years ago, # ^ |   0 I got TLE for this on pretest 5.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 My 3^(log2(n)) in C++ passed pretests, at least ( /contest/449/submission/7172391 ).It's fairly possible to get it AC, I think.
•  » » » » » » 6 years ago, # ^ |   0 Can you please explain your solution? Thanks!
•  » » 6 years ago, # ^ |   +6 Really? Sorry haven't seen it before. Can you give me a link?
•  » » » 6 years ago, # ^ |   +12 This will do.
•  » » » » 6 years ago, # ^ |   0 Oh, it seems that someone told the approach before. Sorry again, didn't remember that.
•  » » 6 years ago, # ^ |   +8 I also didn't know this, but approach I used was very similar to one in problem http://codeforces.com/problemset/problem/383/E (approach to do that part which can be easier done in 3^(log_2(max number)).
 » 6 years ago, # |   -8 Pretest can be weak because I don't trust my code but I accecpted
 » 6 years ago, # |   +3 I think there will be a lot of problem C div2 fails.
•  » » 6 years ago, # ^ |   0 me too, because I think I will fail div2C
•  » » » 6 years ago, # ^ |   0 Me too =))).
•  » » » » 6 years ago, # ^ |   0 I feel like this too :D Almost sure...
•  » » 6 years ago, # ^ |   +1 By the way, what was the intended approach for A div1? The limits suggest some kind of greedy formula.
•  » » » 6 years ago, # ^ |   +9 Either put as many horizontal cuts as possible (obviously with extra vertical cuts if there are too many cuts to do), or put as many vertical cuts as possible (with extra horizontal cuts if necessary).
•  » » » » 6 years ago, # ^ |   +37 "Proof": With a horizontal cuts and b vertical cuts, you divide the chocolate into (a + 1)(b + 1) pieces, so the minimum area cannot be larger than . If you want to maximize this, intuitively you need to take (a + 1)(b + 1) as small as possible. Since a + b = k is fixed, the best you can do is to minimize one term as much as possible, because .
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +13 Note: My solution failed, so this might not be correct.EDIT: Note to self: n rows mean n - 1 horizontal cuts, not n. 7174814
•  » » » » » 6 years ago, # ^ |   0 I used the same idea and also failed, but it is not a proof because nm/(a+1)(b+1) is just an upper bound and you cant conclude that much.
•  » » » » » » 6 years ago, # ^ |   0 That's why it's only a "proof", with quotes, and that I say about "intuitively". It's not rigorous yet, although I felt I was confident enough with the intuition that I went with it.Accepted with a fix (was a faulty reasoning that n rows means n cuts): 7174814
•  » » » » » » » 6 years ago, # ^ |   0 I fixed mine too, didn't notice int could overflow! :'(
•  » » » » » 6 years ago, # ^ |   +2 My accepted solution has a similar idea. Assume that our solution is obtained by t horizontal cuts and k-t vertical cuts. Then, the maximal smallest area is f(t) = n/(t+1) * m/(k-t+1). Note that, 0 <= t <= n-1, and 0 <= k-t <= m-1, then lo = max(0, k-m+1) <= t <= min(k, n-1) = hi. Finally, the solution is max(f(lo), f(hi)).
•  » » » 6 years ago, # ^ |   0 Mine is to try 4 cases: Use all cuts across vertical side. Use as much as possible cuts across horizontal side and the rest across other side. 3-4. Same as 1-2 but in other directions, i.e. "horizontal <-> vertical" This seems to give the same answer as naive approach for all 1 <= n, m <= 100, 1 <= k <= 200. So I didn't look for anything else.
•  » » 6 years ago, # ^ |   0 I use greedy for this problem and don't know it is false or true
 » 6 years ago, # |   +17 http://codeforces.com/contest/449/submission/7169365 — that code will surely get accepted :DD
•  » » 6 years ago, # ^ |   0 How did you know? :-O
•  » » 6 years ago, # ^ | ← Rev. 2 →   +27 IT GOT ACCEPTED :O00OO00OOOO!!!???????"3+m*(27-6*n)+n*(-17+4*n))%mod))%mod*powmod(180,mod-2)"Unbelievable :P.
•  » » » 6 years ago, # ^ |   +8 Nice chinese problem with short and beauty solution, isn't it?)
•  » » » » 6 years ago, # ^ |   +16 This Solution from China also :)
•  » » » 6 years ago, # ^ |   +3 I think Mathematica is your good friend in dealing with this kind of problems. :P
 » 6 years ago, # |   0 Is the observation in Div1 D that it is enough to sum the groups of k from 1 to 20 instead of n, correct ? If it is correct how will it help in solving the problem ? I tried to use the dp state (index,k) but I had no idea how to keep track of the mask till this index.
 » 6 years ago, # |   -8 The system testing is start
 » 6 years ago, # |   +1 was there an easier solution for div2 B instead of doing matrix multiplication w/ the linear recurrence? I thought this was a hard topic for a div2 B problem D:
•  » » 6 years ago, # ^ |   +1 Yes, the sequence is periodic. You could calculate only first six terms.
•  » » 6 years ago, # ^ |   0 Actually there was a trick:Every sequence is the repetition of 6 numbers:x,y,y-x,-x,-y,x-y,...;so you could just find which he was trying to search (using division and mod). Hope this helps
 » 6 years ago, # | ← Rev. 2 →   +19 problem B has 4 pretests.....WTF! WHY????????
•  » » 6 years ago, # ^ |   +3 such weak pretests... that make a lot of coders FST 5.....
•  » » 6 years ago, # ^ |   +6 I'm only sad I had no idea pretests were this weak, otherwise I would have hacked Div1-Bs like crazy :P
•  » » 6 years ago, # ^ |   0 I forgot int64 but got AC :)
•  » » 6 years ago, # ^ |   0 I've seen a guy whose 4 solutions falled on finals.
 » 6 years ago, # |   0 I didn't do well. Only one submission :(
 » 6 years ago, # |   +12 Back to home (div 2) :D
 » 6 years ago, # |   0 How to solve div2-C problem?? please with proof 233333
 » 6 years ago, # |   +8 Back to Newbie.la la la..
•  » » 6 years ago, # ^ |   +2 Back to Specialist.la la la..
•  » » » 6 years ago, # ^ |   +10 Back to red.la la la..:P
•  » » » » 6 years ago, # ^ |   0 Back to blue lalalala :D With 1500 points ahahah. A point less and i was still green lol
•  » » » » » 6 years ago, # ^ |   +1 Back to Blue lalalala :D 1699
•  » » » 6 years ago, # ^ |   +2 Hope I can become specialist after rating update. :P
•  » » » » 6 years ago, # ^ |   +1 Wow,I became the expert. XD
•  » » » » 6 years ago, # ^ |   0 You became expert))
•  » » » 6 years ago, # ^ |   0 Hey you got three accepts you will either go to Candidate master or your rating will increase !
•  » » » » 6 years ago, # ^ |   0 I say about you. (1 problem)la la la...
•  » » » » » 6 years ago, # ^ |   0 Ya :P
•  » » 6 years ago, # ^ |   0 I become green ! la la la -_- :'(
 » 6 years ago, # |   0 in Div 2 what is the solution for problem C i got WA what i thought of is there is a 3 cases 1) not applicable if k > m+n -2 2) 1 if k > max(m,n) -1 3) n*m/(k+1) else ?!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 3 3 1: Correct answer is 3. Your case 3 gives 4.4 4 4: Correct answer is 2. Your case 2 gives 1.
 » 6 years ago, # |   0 problem C in Div 2 was crazy ;(
 » 6 years ago, # |   0 Why is the system testing so slow..?
 » 6 years ago, # |   +12 Congratulations semiexp !
 » 6 years ago, # | ← Rev. 2 →   -70 In my opinion this round should be unrated because it wasn't an unusual round...there were very few pretest. What do you say?
•  » » 6 years ago, # ^ |   +1 IMO no. weak pretests allow hacks!
•  » » 6 years ago, # ^ |   +20 "it wasn't an unusual round" = "it was an usual round" ?
•  » » » 6 years ago, # ^ |   0 Yes. Also, "usual" rounds have weak and few pretests.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 Thanks to your hack, I've fixed my Div2 B :D
•  » » » » » 6 years ago, # ^ |   0 no problem, i also got 100 pts. :) so you should always write weak code and correct it at last moment. may be not as i might not be able to help again.
•  » » 6 years ago, # ^ |   0 Very funny.
•  » » 6 years ago, # ^ |   0 Anyone saw you before you come ?
•  » » 6 years ago, # ^ |   0 Thanks to week pretests, I was able to enjoy hacks.
 » 6 years ago, # |   0 Can someone help me find a flaw in my solution to Div.2 D / Div. 1 B? Link to code: http://ideone.com/opD81jMy approach was to calculate the shortest paths to every node from the capital with and without train tracks. Then I delete off as many tracks as possible.
•  » » 6 years ago, # ^ |   +14 try this testcase out 3 1 2 2 3 1 2 1 3 2 
•  » » » 6 years ago, # ^ |   +1 Can you explain more?
•  » » » » 6 years ago, # ^ |   0 as he use the calculated shortest paths to every node from the capital without train routes, it'll be wrong in case the graph is not connected without some train routes :)
 » 6 years ago, # |   0 Please, help me the problem C div 2? :( I'm try it in 1h30 but it was wrong :(
•  » » 6 years ago, # ^ |   +1 pretty solution http://pastebin.com/WCQTTuLX
•  » » » 6 years ago, # ^ |   0 can you give any proof?
•  » » » 6 years ago, # ^ |   0 thanks for your code :D Can you give me proof? :(
•  » » » » 6 years ago, # ^ |   0 proof — best way to divide is divide by one side
•  » » » » » 6 years ago, # ^ |   0 Great proof!
 » 6 years ago, # | ← Rev. 3 →   0 EDIT: Resolved now.I got WA in http://codeforces.com/contest/450/submission/7160858, but seems other solutions are accepted with same answer ?! What am I missing ?!!
•  » » 6 years ago, # ^ |   0 Fix your link... for any person X it leads to X's submissions :)
•  » » » 6 years ago, # ^ |   0 sure. hope its better now
•  » » » » 6 years ago, # ^ |   +4 Hint: consider case when n%6 == 0 :) you should've write "case 0:", not "case 6:"
•  » » » » » 6 years ago, # ^ |   0 Oh ok. thanks :)
•  » » 6 years ago, # ^ |   0 You wrote case 6 instead of case 0.Here is your code corrected. http://codeforces.com/contest/450/submission/7176195
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 edit : ignore , already answered. In your case if n == 6 then n%6 is 0. change your case 6 to case case 0.
 » 6 years ago, # |   0 Will there be any editorial for these contests?
•  » » 6 years ago, # ^ |   0 I think it will be post in a minutes.
•  » » » 6 years ago, # ^ |   0 not yet :/
 » 6 years ago, # |   +11 Nearly back to grey...... Anyway just keep on fighting!
 » 6 years ago, # |   +31 I was a green coder before this contest,but now I'm purple!
•  » » 6 years ago, # ^ |   +3 Congratulations!
•  » » » 6 years ago, # ^ |   0 Thank you!
•  » » 6 years ago, # ^ |   +3 Great Step :)) Congrat :))
•  » » » 6 years ago, # ^ |   +1 Thank you!
 » 6 years ago, # |   0 Can anyone explain div2D/div1B?
 » 6 years ago, # |   0 Although problem C div2 was hard, but I enjoyed the problems. Especially problem B div2. Thanks for your nice problems.Won't there be any editorial?
 » 6 years ago, # |   0 Hard round i ever seen... very tricky ..but interesting problems..thanks for setting this contest...
 » 6 years ago, # |   0 I wish the pretests for B and D weren't pointless... I got first submit AC on all pretests, and systest fail on the first non-pretest. THE VERY FIRST ONE. TWICE.And it's not like there were too many pretests, D had 7 and B just 4. Would it have hurt too much to add several more? Not to mention, there was no real maxtest (just one with unit lengths) included in the pretests of B, which is IMO not a good idea regardless of the problem.
•  » » 6 years ago, # ^ |   +5 BTW, many wrong solutions failed pretests on B)I think it was made this way to increase number of challenges. But most of us just did not found out during the round that pretests are so weak.
•  » » » 6 years ago, # ^ |   -8 Yes, it's a given that many solutions would fail if there are just 4 pretests, out of which 2 are samples. Which is why I'm complaining that the pretests were few and bad. Usually though, it should be "it seems this problem has many tricky situations -> let's try hacking", which doesn't seem like the case with B.
 » 6 years ago, # |   0 For those who got why Div1 A failed so many times: why did Div1 A fail so many times? What's the general flaw pattern?
 » 6 years ago, # |   +14 Nice round, but how about editorial?)
 » 6 years ago, # |   0 please any one explain me how to solve div2 C briefly . waiting for editorial but of no use.
•  » » 6 years ago, # ^ |   +1 I just a few words, you simply have to observe that you divide up one side of the chocolate as much as you can and use the remaining cuts on the other side of the chocolate. You do this for both sides.The intuition behind this is quite simple. I think someone above this has already explained but I will explain it here as well. The number of pieces after you make a cuts on one side and b cuts on the other side is (a + 1) (b + 1), leaving the min area to be (nm) / ((a + 1) (b + 1)). You want to thus minimize (a + 1) (b + 1) which is equal to ab + a + b + 1. Since a + b = k, you just need to minimize ab.
•  » » » 6 years ago, # ^ |   0 thank u very much !! I was very disappointed for not solving such an easy problem !!
•  » » » 6 years ago, # ^ | ← Rev. 6 →   0 acho163 We need to minimize the value expr=ab i.e expr=a*k-(a*a).How can we say that value of expr is least when you divide up one side of the chocolate as much as you can?( I'm talking about the case when k>m-1.In this case,how can we say that by keeping a=( k-(m-1) ),we get the least expr value? ).
•  » » » » 6 years ago, # ^ |   0 This is through intuitive math thinking. Let's say k = 6. Let's list out the possible values of ab, such that a + b = k.a = 1, b = 5, 5 a = 2, b = 4, 8 a = 3, b = 3, 9.So as you can see, the smaller a is, the better, thus we maximize the cuts on one side to minimize the cuts on the other side. The proof is basic math, see if you can prove it yourself.
 » 6 years ago, # |   +17 yc5-yc, jzzhu any updates regarding the editorial?
 » 6 years ago, # |   +58
 » 6 years ago, # |   +7 I think the pretests are becoming too much weak. Sometimes it makes me wonder if they are even necessary at all. I think they should be made a little more stronger. Recently I've seen many codes of strong coders who are way beyond my level to pass on pretests on one shot but fail within a few cases of the main test cases. And after checking them, the cases were actually simple rather than medium or strong corner cases. Sometimes this becomes a little upsetting. I don't know if others feel this way but this is just my opinion.
•  » » 6 years ago, # ^ |   0 It depends on what they are trying to achieve. In the competitions I've participated in the past the solutions were only checked on the samples from the problem statement, at best, so you had to be think carefully before submitting. However, you also got partial score if the solution failed some tests, and no penalty for late submissions/resubmissions.It certainly makes more sense to have stronger test cases here, since even a small mistake means you get 0 for the problem, and you get penalized for resubmitting the problem anyway. Still, it doesn't mean that they should include all corner cases (which seems to be the Topcoder approach).
•  » » » 6 years ago, # ^ |   0 In haven't participated in almost any competitions where the solutions would only be tested on samples. IOI, ACM ICPC, CF rules aren't like that, and many competitions use one of them. TC doesn't really count, because they often have many samples, including large tests. Yandex Algorithm, not. GCJ, not. CodeChef: ACM rules. Various ACM trainings: ACM rules. Most secondary school competitions: IOI rules. Uh... Hackerrank: even more detailed than ACM rules. To be honest, I haven't participated in a competition without feedback for months, and I do almost all there is.There are just a few secondary school competitions (like COCI or USACO) that have no feedback.The reason for it is clear: you don't have to think carefully before submitting, because a small unnoticeable bug can make you fail easily. If you understand the problem incorrectly and it still fits with the samples, nothing can help you. If you have a small bug that only shows with large/specific cases (yes, there are such situations, converting subtrees to intervals by inorder traversal is an excellent example), you don't have to find it even if you generate dozens of tests and check your code against a bruteforce. Your code can fail on large corner cases. Etc. Even if the problem has partial scoring, you can still fail horribly because of missing a special case (I got 0/100 on IOI 2012 Rings, with exactly one WA in each of 5 subtasks, even with full feedback, and you can easily guess why).I don't know if TC really includes all corner cases in samples. It's usually "several small samples demonstrating the problem, sometimes some corner cases, 1 or 2 large samples". I've even had solutions that were so horribly wrong I fail to understand how I could ever write such bullshit, and yet passed all the samples. Besides, their samples are supposed to be the same thing as pretests here.
 » 6 years ago, # |   0 How to solve D1-D using inclusion-exclusion? What's the idea?
•  » » 6 years ago, # ^ |   +30 Let X denote the input set. . allzero(y, S) returns true if and only if the i-th bit of y is 0 for (similar definition for allone). Then the answer would be . requires m = 20, but I will use m = 2 for better illustration. It's trivial to generalise to the case where m = 20. By inclusion-exclusion principle, we know:. . . . .If all T mask are known, we can simply loop over all possible mask values (220) to get the answer.Now let's turn to T mask. T mask is the number of element x, such that x&T mask = T mask. Informally speaking, if some bit of T mask is 1, the corresponding bit of x must be 1, otherwise there's no constraint on x.  for (int i = 0; i < n; ++i) { int x; scanf("%d", &x); cnt[x]++; } for (int j = 0; j < 20; ++j) for (int i = two(20) - 1; i >= 0; --i) { if (getbit(i, j) == 0) cnt[i] += cnt[i | two(j)]; } Prior to the j-th iteration, cnt[mask] would be the cardinality of the set of x, such that bit 0 to j - 1 meets the condition I mentioned above, bit j to 19 must match precisely between x and mask. Executing the j-th iteration would loosen the constraint in 0 values at the j-th bit of mask. The overall time complexity is 20 × 220.
 » 6 years ago, # |   +14 My rank changes from 192 to 191 and silly_girl is not from top 5 as writer mentioned is this a cheating case ?
•  » » 6 years ago, # ^ |   0 Seriously, what happened ?