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 gagaga5-gagaga 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
5.mruxim
Division 2:
1.swenyoo
2.chm517
3.Shinka
4.TBH
You can find editorial here.
Wow! Another Chinese round!
But Codeforces Round 256 (Div. 2) was a combobreaker :D
Another combobreaker is just coming =D
a Div-2 only round cannot actually be called a combobreaker :D
Still, Div 1 rounds are all Chinese :D
That combobreaker will also come soon :)
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 ).
chinese round month..
and maybe MinakoKojima's round will be come out this month
I hope not :(
Gold Bear!!!! Amazing!! I feel surprise to see such amazing id in codeforces
I have thought the #257 is MinakoKojima's round..... Wish his round come soon~ And the multi-university training come soon~
jzzhu != jzzhu ("the real Jzzhu isn't me")
I like Chinese rounds because it starts early, but Div1 E is always too hard :v
Seriously, Are YOU talking about Div1 E?
Yes, although I'm at Div2 :v
i cannot see a E Accepted by you either div2 or div1 :D
Yeah, I'm still a noob D: I will try my best to improve D:
That's the spirit :D
seriously , why a Div2er like me can't talk about div1E ?
Chinese round, Interesting.
Why do you idiots give me negative points? Fucking shit.
You are a Fucking shit.
Look at ur poor rating, WOW such a idiot! Do you think you "Expert" have the right to scold me?
Look at your poor minus contribution, WOW such an idiot! Do you think you "Jackass" have the right to leave a comment?
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!
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?
I would say you are just a fucking shit.
Suddenly quiet about rating, are you?
Why are you guys quarrelling about nothing?
Nah, I'm just teasing him :D
Let's solve problems.
This is codeforces but not /b/
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.
Seems that Chinese rounds are interesting, but you guys are more interesting! 233333333333
_
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.
Best wishes~! Gl&&Hf in IOI~!
Thanks. I won a Bronze medal.
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~
Yes, I have another chance.
Another chinese round. I like chinese rounds because it can involve math and sometimes good problems.
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.
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?
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.
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!
cool)
This seems familiar to me, may you name the teacher?
Mr.Mirjalali
Thanks!
Is your teacher name َ"Ali Ghasaab" :)? He knows me very well :) give my regards to my best ever teacher...
No, But he was my teacher 3 years ago.
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.
hard contest or easy!!!
Yes. Or medium.
256؟؟
ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็
What, are we having a contest in posting random stuff?
what???are you seying!!! ???
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
ok thank you very much
Chinese here, Chinese there, Chinese everywhere :P after these 3 contests my mom will see me just like JACKIE JOHN
hope an easy contest! :)
Chinese round again.I'm glad to see it.RP++
just Ten minutes remain but a problem rush in my mind: But i will be glad if any of you answer my question : http://mirror.codeforces.com/blog/entry/13102
I like Chinese round! Good luck and have fun for everyone!
Especially with standard score
what's the problem with hack???
div2 B with
1000000000 -1000000000
3
For Div2, Problem B.
A lot of participants didn't noticed that (x-y) can be less than -(10^9+7).
Great round! I submitted three. Hope they pass systests!
Any hint on C except for Blossom Algorithm? Nice round anyway.
I think we can do a bipartite matching using dinics etc. Too bad I couldn't implement it during contest though :(
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?
Yes, you are right. Maybe this is not the intended way. Now I too am confused.
you can consider only the edges that connect a smaller number to a bigger one (not vice-versa)
I think that it still won't work this way. Think about connecting A-B and B-C (both of them forward edges).
I used sieve of Eratosthenes.
Since you want a hint: Greedy. And prime sieving, yes.
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
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:
It shouldn't be hard to see that all apples not in the form 2p or 2k are used in step 2, and all remaining apples (except probably one) that are not used in step 2 are used in step 4.
Sorry for double post but... Chaotic_iak, you made over +500 in less than two months! Amazing progress, my huge congratulations :)
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
very WEAK pretests....I'm really afraid of systests...
all problems was tricky thanks
what was to be done in div-2 C ....
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
What is the approach for DIV2 D ?
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.
Nevermind I got WA
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..
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.
If you need it, here there is my fixed code: http://mirror.codeforces.com/contest/450/submission/7179339
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++...
What kind of naive solution do you mean? dp[n][mask] ?
I mean 3^(log2(n)) solution.
I got TLE for this on pretest 5.
My 3^(log2(n)) in C++ passed pretests, at least ( /contest/449/submission/7172391 ).
It's fairly possible to get it AC, I think.
Can you please explain your solution? Thanks!
Really? Sorry haven't seen it before. Can you give me a link?
This will do.
Oh, it seems that someone told the approach before. Sorry again, didn't remember that.
I also didn't know this, but approach I used was very similar to one in problem http://mirror.codeforces.com/problemset/problem/383/E (approach to do that part which can be easier done in 3^(log_2(max number)).
Pretest can be weak because I don't trust my code but I accecpted
I think there will be a lot of problem C div2 fails.
me too, because I think I will fail div2C
Me too =))).
I feel like this too :D Almost sure...
By the way, what was the intended approach for A div1? The limits suggest some kind of greedy formula.
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).
"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 
.
Note: My solution failed, so this might not be correct.
EDIT: Note to self: n rows mean n - 1 horizontal cuts, not n. 7174814
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.
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
I fixed mine too, didn't notice int could overflow! :'(
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)).
Mine is to try 4 cases:
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.
I use greedy for this problem and don't know it is false or true
http://mirror.codeforces.com/contest/449/submission/7169365 — that code will surely get accepted :DD
How did you know? :-O
IT GOT ACCEPTED :O00OO00OOOO!!!???????
"3+m*(27-6*n)+n*(-17+4*n))%mod))%mod*powmod(180,mod-2)"
Unbelievable :P.
Nice chinese problem with short and beauty solution, isn't it?)
This Solution from China also :)
I think Mathematica is your good friend in dealing with this kind of problems. :P
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.
The system testing is start
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:
Yes, the sequence is periodic. You could calculate only first six terms.
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
problem B has 4 pretests.....WTF!
WHY????????
such weak pretests... that make a lot of coders FST 5.....
I'm only sad I had no idea pretests were this weak, otherwise I would have hacked Div1-Bs like crazy :P
I forgot int64 but got AC :)
I've seen a guy whose 4 solutions falled on finals.
Back to home (div 2) :D
How to solve div2-C problem?? please with proof 233333
Back to Newbie.
la la la..
Back to Specialist.
la la la..
Back to red.
la la la..
:P
Back to blue lalalala :D With 1500 points ahahah. A point less and i was still green lol
Back to Blue lalalala :D 1699
Hope I can become specialist after rating update. :P
Wow,I became the expert. XD
You became expert))
Hey you got three accepts you will either go to Candidate master or your rating will increase !
I say about you. (1 problem)
la la la...
Ya :P
I become green !
la la la -_- :'(
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
?!!
3 3 1: Correct answer is3. Your case 3 gives4.4 4 4: Correct answer is2. Your case 2 gives1.problem C in Div 2 was crazy ;(
Why is the system testing so slow..?
Congratulations semiexp !
In my opinion this round should be unrated because it wasn't an unusual round...there were very few pretest. What do you say?
IMO no. weak pretests allow hacks!
"it wasn't an unusual round" = "it was an usual round" ?
Yes. Also, "usual" rounds have weak and few pretests.
Thanks to your hack, I've fixed my Div2 B :D
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.
Very funny.
Anyone saw you before you come ?
Thanks to week pretests, I was able to enjoy hacks.
Can someone help me find a flaw in my solution to Div.2 D / Div. 1 B? Link to code: http://ideone.com/opD81j
My 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.
try this testcase out
Can you explain more?
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 :)
Please, help me the problem C div 2? :( I'm try it in 1h30 but it was wrong :(
pretty solution http://pastebin.com/WCQTTuLX
can you give any proof?
thanks for your code :D Can you give me proof? :(
proof — best way to divide is divide by one side
Great proof!
EDIT: Resolved now.
I got WA in http://mirror.codeforces.com/contest/450/submission/7160858, but seems other solutions are accepted with same answer ?! What am I missing ?!!
Fix your link... for any person X it leads to X's submissions :)
sure. hope its better now
Hint: consider case when n%6 == 0 :) you should've write "case 0:", not "case 6:"
Oh ok. thanks :)
You wrote case 6 instead of case 0.
Here is your code corrected. http://mirror.codeforces.com/contest/450/submission/7176195
edit : ignore , already answered. In your case if n == 6 then n%6 is 0. change your case 6 to case case 0.
Will there be any editorial for these contests?
I think it will be post in a minutes.
not yet :/
Nearly back to grey...... Anyway just keep on fighting!
I was a green coder before this contest,but now I'm purple!
Congratulations!
Thank you!
Great Step :)) Congrat :))
Thank you!
Can anyone explain div2D/div1B?
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?
Hard round i ever seen... very tricky ..but interesting problems..thanks for setting this contest...
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.
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.
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.
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?
Nice round, but how about editorial?)
please any one explain me how to solve div2 C briefly . waiting for editorial but of no use.
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.
bboy_drain 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? ).
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.
gagaga5-gagaga, jzzhu any updates regarding the editorial?
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.
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).
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.
How to solve D1-D using inclusion-exclusion? What's the idea?
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 Tmask are known, we can simply loop over all possible mask values (220) to get the answer.
Now let's turn to Tmask. Tmask is the number of element x, such that x&Tmask = Tmask. Informally speaking, if some bit of Tmask is 1, the corresponding bit of x must be 1, otherwise there's no constraint on x.
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.
My rank changes from 192 to 191 and silly_girl is not from top 5 as writer mentioned is this a cheating case ?
Seriously, what happened ?