danilka.pro's blog

By danilka.pro, history, 6 years ago, translation,

Good time of day, Codeforces!

I am glad to announce that this Sunday, 8th November at 19:30 MSK, Codeforces Round #330 for both divisions will take place.

The problemset of the round has been prepared for you with pleasure by Alex fcspartakm Frolov and me, Dan Sagunov. We want to thank the coordinator of Codeforces Gleb GlebsHP Evstropov for his valuable help in problem preparation, Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon systems, Maria Delinur Belova for translating problem statements into English and Vladislav winger Isenbaev and Alex AlexFetisov Fetisov who have tested the round problemset.

Every participant will be given two hours to solve five problems. We have tried to make the round problemset variative and interesting and therefore we strongly recommend to read all the problem statements during the round. Scoring will be announced later as always.

We wish good luck and high rating to everyone!

UPD. We are sorry again for the mistake in Cdiv2/Adiv1 problem: jury's solution is working wrong in odd n case. We are hoping that other problems was (or will be such in upsolving) interesting and useful.

Anyway, let's congratulate the round winners:

First division winners:

second division winners:

Editorial could be found here.

UPD. Problem Cdiv2/Adiv1 was fixed and now it has the statement and solution which jury meant it to be. Problem has been returned to the contest, so feel free to upsolve it.

• +99

 » 6 years ago, # |   +7 you used to be red :D
•  » » 6 years ago, # ^ |   +16 You used to be purple :D It's not funny when it's told to you, isn't it?
•  » » » 6 years ago, # ^ |   +39 No man, I didn't meant that I was joking with him because he said that in his previous round see the first line of this post http://codeforces.com/blog/entry/20657
•  » » » » 6 years ago, # ^ |   +23 I didn't know that. Sorry.
 » 6 years ago, # |   0 I like your problems... not too easy not too hard. thank you.
•  » » 6 years ago, # ^ |   +38 NOT thank you because unrated...
 » 6 years ago, # |   +2 Finally we have Div 1 after A long time.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +48 It seems the queue has been empty lately, time to push() :-)
•  » » » 6 years ago, # ^ |   -8 queue.pop() :D
•  » » 6 years ago, # ^ |   +45 I think not. Doesn't the last contest seem like Div1?
•  » » » 6 years ago, # ^ |   0 We all agree with you :D
•  » » 6 years ago, # ^ |   +15 Dude !! last contest was almost a Div1 contest !! :P
•  » » 6 years ago, # ^ |   0 It will soon be a full month between DIV I rated contests. Has that ever happened before?
 » 6 years ago, # |   -36 Waiting For The Moment ..................
 » 6 years ago, # |   -126 The comment is hidden because of too negative feedback, click here to view it
•  » » 6 years ago, # ^ |   +42 You can't trick russians that way :P
•  » » » 6 years ago, # ^ |   -32 I actually tricked them :D. That's exactly what I wanted in the first place.
•  » » 6 years ago, # ^ |   +14 You could've made here as a link to your comment.
 » 6 years ago, # |   +11 The links in my email seemed to be incorrect.I clicked Codeforces Round 330,but it went to http://codeforces.com/contests/587,588
 » 6 years ago, # |   +8 "We wish good luck and high rating to everyone!". I may have believed that a week ago, but after explaining how the rating works it is clear high rating to everyone is impossible.
 » 6 years ago, # |   -62 That is my time to be purple.Ok gays! if you want to have a good luck and increase your rating please thumb up me, and you will be lucky!
•  » » 6 years ago, # ^ |   +70 gays? :|
 » 6 years ago, # |   -12 Last contest before regional Acm Icpc 2015.
 » 6 years ago, # |   -6 Good luck and have fun!
 » 6 years ago, # |   +1 how can i register for the todays contest round#330 (div.1)?
•  » » 6 years ago, # ^ |   +13 hack a div 1 account :P
•  » » 6 years ago, # ^ |   0 Only Div 1 contestants can register for Div 1 contests.
•  » » 6 years ago, # ^ |   +19 New contestants are only allowed to div. 2 contests. Once you have managed to gain a rating of >= 1900, you are allowed to to enter div. 1 contests. So simply join a few div. 2 contests. If your're an excellent programmer you'll be in div. 1 in no time.
 » 6 years ago, # |   +84
•  » » 6 years ago, # ^ |   +7 You're missing 12 more red figures
 » 6 years ago, # |   -6 I wish good luck and high rating to everyone!
 » 6 years ago, # |   -9 hope this would be my last div2 contest :D
•  » » 6 years ago, # ^ |   +16 ha-ha:D welcome again!
•  » » » 6 years ago, # ^ |   +3 thanks :D :P
 » 6 years ago, # |   +6 I can't take this contest because of school exam :( !life is not fair !
•  » » 6 years ago, # ^ |   +105 I can't take school exam because of codeforces contest :DLife is fair!
•  » » » 6 years ago, # ^ |   0 I dream your life! ;D
•  » » » 6 years ago, # ^ |   0 i cant do my homework for codeforces contestand ... fair unfair i dont now
•  » » 6 years ago, # ^ |   0 it's just about which is more important for you !!!
 » 6 years ago, # |   0 Hope I m able to solve more problems today and increase my level!
 » 6 years ago, # |   +29 Scoring will be announced later.....ammmm maybe after the contest :D
 » 6 years ago, # |   +14 Where is scoring distribution??
 » 6 years ago, # |   +9 today's contest also seem's like div1 contest..... how we solve ????
•  » » 6 years ago, # ^ |   0 Well , this time it's not so hard (at least as last round). :D. But i don't say it's easy too.
 » 6 years ago, # |   +5 "Div 2 problems" ...
 » 6 years ago, # |   -10 These kind of problemsets are a disaster! Such an easy A, then relatively much harder problems. Why did you wish us high rating? You knew that's a a lie.
•  » » 6 years ago, # ^ |   0 Nope B is ok.
•  » » » 6 years ago, # ^ |   +5 Try to solve C then!!! :|
•  » » » » 6 years ago, # ^ |   0 I am trying. :) I am weak in game theory and i have solved C only one time before.
•  » » » » » 6 years ago, # ^ |   +3 Crap :( Unrated round.
•  » » » 6 years ago, # ^ |   +8 So, round is unrated!! Let's discuss solutions before they cahnge their mind :D
 » 6 years ago, # |   +6 why this hard contests ??? is there a revolution in the divisions ??? :_( please a div2 usual contest !!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +12 I guess there should be Div. 3 contests, if Div. 2 continues being so hard.
 » 6 years ago, # |   +23 Div. 0 contest :)
 » 6 years ago, # |   +19 What terrible problems... perfect round to make unrated.
•  » » 6 years ago, # ^ |   +4 I think problem Div1A is really nice.
•  » » » 6 years ago, # ^ |   0 I was confused by the statement, but it seemed like a nice problem. Take a look at Div2/B though — absolute nightmare.
•  » » » » 6 years ago, # ^ |   0 If i did it then it's definitely easy! :P
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +1 You must wait for systests before claiming you did it. By the way, how did you do it? I thought 10^8 might not be correct complexity.
•  » » » » » 6 years ago, # ^ |   0 You didn't do it right, though. 14152835
•  » » » » » » 6 years ago, # ^ |   0 Yea :P. Now it's right after checking one more corner case a_i = 1 and b_i = 0.
 » 6 years ago, # |   +10 Unrated round >.<
 » 6 years ago, # |   -26 Why UNRATED contest because of one problem ??? This time I solved 2 problems and they did this.
•  » » 6 years ago, # ^ |   -15 this is wrong! just do not count the C part! but why it has to be unrated?
•  » » » 6 years ago, # ^ |   +25 Simply not counting the problem wouldn't be fair to the people who spent a lot of time on it.
•  » » » 6 years ago, # ^ |   +11 are u fucking serious? well imagine someone spent a lot of time for C, solved it and then BAM 'time well spent'. yea great idea
 » 6 years ago, # |   +6 After long time i was going to get under 1k rank and now it's unrated! :( Well now i am waiting next contest. :D
 » 6 years ago, # |   +25 "Unfortunately, we are too tell" — the english is stronK in this one :)
•  » » 6 years ago, # ^ |   +1 Think first, what would be your situation while getting such type of pressure! Can you think yourself in the place of authors?
•  » » » 6 years ago, # ^ |   -16 It's funny though isn't it? :). Btw these last 2 rounds reminded me why i stopped competing on codeforces long ago... Nothing has changed, hard to understand statements and problems not suitable for div2.
 » 6 years ago, # |   0 a unrated round after 1:30 hours. really?
•  » » 6 years ago, # ^ |   +58 Think about the chances of finding out that your model solution is wrong. There's only one: a contestant raises a valid question.Of course, realising that it's not your solution that's wrong (as a contestant), but a model solution, requires actually writing something that passes pretests — and not moving on to the next problem. How many people would do that? In addition, it requires realising that what you submitted is totally wrong. That makes the chances even lower.It requires a lot of coincidences. 1:30 can even be quite early, I'd rather expect the error to be found in comments after the round.
•  » » » 6 years ago, # ^ |   +63 Why didn't authors stress their model solution against n·2n solution?
•  » » » » 6 years ago, # ^ |   +13 Maybe they did, but the small test data weren't strong enough?
•  » » » » 6 years ago, # ^ |   +5 What makes you think the smallest counter example is small enough for that algorithm to be feasible?
•  » » » » » 6 years ago, # ^ |   +17 Looks very reasonable that the minimal counter example has the length <= 20.
•  » » » » » » 6 years ago, # ^ |   0 I agree, but my point is that you can't hypothesize that they did not stress-test their solution when you have no idea what the counter example looks like.
•  » » » » 6 years ago, # ^ |   0 This is the right question. I modeled that the task is unsolvable with any greedy algorithm that I came up with using my minimax bruteforce solution as a etalon and a couple of hard test cases, but still was trying to find some "quirk", because didn't even consider a possibility of a wrong problem.Why didn't authors did it...
•  » » » 6 years ago, # ^ |   -15 You the contestant.
 » 6 years ago, # |   +37 Well, perhaps that explains why I found Div1A to be so hard...
 » 6 years ago, # | ← Rev. 2 →   +31 An unproven greedy strategy can mess up your codeforces round :p
 » 6 years ago, # | ← Rev. 2 →   +33 That's why I recommend the authors to discuss the solution with me before the contest starts! ;)
»
6 years ago, # |
+207

ZLOBOBER COME BACK PLZ!!!

•  » » 6 years ago, # ^ | ← Rev. 2 →   -9 this is the second bad contest of new coordinator. (just two good rounds) :( UPD : sorry GlebsHP
•  » » 6 years ago, # ^ | ← Rev. 2 →   -17 Please Zlobober
•  » » 6 years ago, # ^ |   -14 Best of the best of the best : Zlobober
•  » » » 6 years ago, # ^ |   -35 In a few rounds, new coordinator gonna quit :(
•  » » » » 6 years ago, # ^ |   -9 replying your own comments ?
•  » » » » » 6 years ago, # ^ |   -24 I didn't know that a rule "Cannot reply your own comment", Thanks for the Tip :)
•  » » » » » » 6 years ago, # ^ |   0 there is no rule. It just seems like you are schizophrenics :( (nice image by the way)
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +22
•  » » 6 years ago, # ^ |   +582 Please be polite and patient. First contests are the hardest ones, mine first days were also very nervous, sometimes I've been really close to have an unrated round.What you do is the worst possible action. Haters' comments like yours only increase the pressure, and make harder for everybody to hold a normal round. Just imagine how stressed will be the next contest authors. So please show some respect to the platform and to GlebsHP and be patient.
•  » » » 6 years ago, # ^ |   +71 +1 to Zlobober. This failure is also our failure as well. We didn't notice that on the presolving stage of the contest, so whoever wants to speak bad about new coordinator feel free to equally share your rage between all of us. More of that, working with GlebsHP is very nice. We will try to be more thoughtful next time and do our best to avoid these mistakes. Shit happens :(
 » 6 years ago, # | ← Rev. 2 →   +36 In Hong Kong, I am doing this contest in MID-NIGHT and at the morning I need to go to school. And I still participate because I want my rating increase. Now this round is unrated... Really?
•  » » 6 years ago, # ^ |   0 do this contest in MID-NIGHT too
•  » » 6 years ago, # ^ |   +4 next time you ought to participate for contest, not for rating, and you will not upset :)
 » 6 years ago, # |   +3 What do you mean by this?
•  » » 6 years ago, # ^ |   -32 "We wish good luck and high rating to everyone!" ha? Could have become top10 if rated. Why not be rated for a part of the contestants?
•  » » » 6 years ago, # ^ |   +14 Dude, clam down. If you deserve it, you'll get it in the next contest. Be patient ;)
 » 6 years ago, # |   +46 Aw.. I solved (Div 1) D, was hoping for a lot of points. But I understand that making the round unrated is the right thing to do.
•  » » 6 years ago, # ^ |   -17 I'm so sorry!!!
•  » » 6 years ago, # ^ |   +5 Same here :/
 » 6 years ago, # |   0 And now this contest is unrated :(
 » 6 years ago, # |   0 Now that problem C is removed, did anyone find something wrong with the logic behind explanation of test case 2? It doesn't seem right to me somehow :(
•  » » 6 years ago, # ^ |   +5 test 2 was ok i guess
 » 6 years ago, # | ← Rev. 3 →   -29 I wish it was still rated. Those who solved Div 2 A and B quickly will lose out on good rating :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 rating is not everything, nor should it be the only motivation to code. just got swayed by emotion after the announcement so yes the decision should be fair to everyone :)plus the round writers have worked hard for this and they must have felt bad too. anyway, waiting for the editorials :)
 » 6 years ago, # | ← Rev. 2 →   -10 Seriously, round unrated!!!!, i can't believe it, after 1:30 hours in competition, this is a disaster[contest:330]!!!
•  » » 6 years ago, # ^ |   +2 wtf! cf had a lot of cool contests in these years!! how many of them gon wrong? NONE!! lets forget this brown day and v8 4 more cool contests.. and by the way, your a NewBie, just thank cf and fuc*OFF :D
 » 6 years ago, # |   -13 this is not fare! make it rated!
•  » » 6 years ago, # ^ |   +11 Fare??
 » 6 years ago, # | ← Rev. 2 →   +32 Does the model solution fail on this test by any chance? 5 1 2 3 4 5 Ah, so this is the countertest?I was a bit confused since things change a lot as the game progresses. During the contest, the first thing I came up with was apparently the same as the model solution, but I also had this countertest and got stumped and gave up. I proceeded to pass pretests on D and C (with some trouble). I guess I still haven't solved D in an official contest then... I still learned some stuff I guess :D. Lessons: deques and queues have a much larger memory overhead than vectors. return printf("1\n") works locally but not on CF. Sometimes things that seem too hard actually are XD
•  » » 6 years ago, # ^ |   0 What would the optimal solution for both players be? I'm not sure what they mean by "optimal" by both players.
•  » » » 6 years ago, # ^ |   0 The solution here should be 1.
•  » » » 6 years ago, # ^ |   0 Answer is presumably 1; the first player will remove 5 (or 1, whatever), then whatever the second player removes the first player will be able to get a result of 1 (e.g. if the second guy chooses 2, then the first guy would choose 1). Similar thing with the case I was trying to figure out how to deal with: 5 1 3 6 7 15 The point being that both players have a ton of on-the-fly adjustments they can make.
•  » » 6 years ago, # ^ |   0 Thst is the hack!Congratulation !
•  » » 6 years ago, # ^ |   0 What is special about this case? I couldn't come up with any solution (not even remotely close), so I'm not really sure.
•  » » 6 years ago, # ^ |   0 Are you using a set by any chance?
•  » » 6 years ago, # ^ |   0 So if this is actually the counterexample then I guess the offical solution was saying "ok, we can let the first guy do all his turns first" (i.e. you want max(arr[n-1-turns+i]-arr[i]) where turns=ceil((n-2)/2) is the number of turns the first guy gets) or something similar.
•  » » 6 years ago, # ^ |   +1 If it's in main(), you can use return printf("1\n"), 0;By convention, main() should return zero on success.
•  » » » 6 years ago, # ^ |   0 Yeah I know that. I always do it with the 0 but today I forgot and it still worked locally -> learned to check that.
 » 6 years ago, # |   +17 Were all the solutions of participants incorrect, too?
•  » » 6 years ago, # ^ |   +2 Maybe solutions which passed pretests are false, but solutions which fails pretest are true? :D:D
 » 6 years ago, # |   +1 a black day for codeforces ...... (mabye brown)
 » 6 years ago, # | ← Rev. 6 →   0 I assume we are free to discuss solutions if it is unrated.How to find the count of integers which start with b[i] and are divisable by a[i] in some range [a[i],pow(10,k + 1) -1] ? Anyone can help here please??? :)I assume we shouldn't brute force, there should be an elegant solution to this.My idea for B is : count possible numbers for each of the n/k positions. then answer is the product of the (1 + count of possible numbers) for 1 <= n/kA tip for the problem setter : It's better to say "If ... start 'WITH' instead of 'FROM'
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Find lower bound -> 'from' if divisible, from + (x — from % x) if not. Then find upper bound which is simply (to / x) * x. Now the number of divisors is (to — from) / x + 1
•  » » » 6 years ago, # ^ |   0 can you please define from and to, and x. Thanks.
•  » » » » 6 years ago, # ^ |   0 Oh my god. I got it!! :D I was sitting on the desk and got shocked for a moment how stupid it is :D
 » 6 years ago, # |   -9 Another terribly contest! The idea of tasks ( first four tasks are great ), but guys: The tasks are pretty hard for div 2 round. The fourth task again some physics ?! Bug in the third task, I am really interested what it is. I can not understand that two purple, one orange and two red coders didn't find mistake in the problem. Why I can not hack solutions with smaller matrix size than it is needed in the first task( many users put matrix [100][100] instead of [100][200])?
•  » » 6 years ago, # ^ |   0 4th task is not physics, point on circle can be described in terms of coordinates of circle-centre and angle (and angle depends only on time)
•  » » 6 years ago, # ^ |   0 the same at 4
•  » » 6 years ago, # ^ |   +32 >physicsI don't think this word means what you think it means. A cycloid is a mathemathical curve; while I see a lot of analogies with physics, they didn't help at all and I solved it as a purely programming problem.You're given an implicit relation between something proportional to the answer, t (the answer is tV / R) and some parameter p which you can freely change: φ(t, p) = R(t + sin(p) - sin(p + t)) - L = 0. Find the minimum t.Binary-search. Since t - sin(p + t) is non-decreasing in t for any p, if φ(t0, p) ≥ 0 for some p, then the min. t is at most t0; otherwise, it's more than t0. For fixed t0, sin(p) - sin(p + t0) attains all values in the range , which makes the binary search condition easy to check.Where's the physics? Though I agree that it's too hard for div1 B.
•  » » » 6 years ago, # ^ |   +10 Problems involving rotational motion like these arise a lot more in physics than in pure mathematics or computer science, and I believe that is where the confusion may have stemmed from.
•  » » » 6 years ago, # ^ |   0 Ok. I can agree with you. I didn't have full solution for the fourth task and you are right. The previous round had similar idea for the fourth task. I think physics task, which can be solved by math (geometry) and binary search. For me previous one was more interested.BTW:Did anyone has right solution for the C d2 (A d1) task ?
•  » » 6 years ago, # ^ |   0 allllekssssa Same happened with me.Someone had made an array of size[107][107]. So I gave n=100,m=100 and gave all the values as 1. Surprisingly, it gave Correct Answer which was 10000.I wrote that contestant's solution on my machine and gave the same input but a miracle happened. It gave 10000 here too. I failed to understand the sorcery:P. So as a last ditch, I put some 0's in between instead of all 1's. The correct answer was 9998 but his program showed 10000. Hacked it with this input and succeeded. But curious to know, what had happened the first time? Shouldn't the code Segfault?
•  » » » 6 years ago, # ^ |   0 I thought the same. I am not big expert for C++, but I think that program use some extra memory and change size of array.
 » 6 years ago, # | ← Rev. 3 →   +32 spent one hour on the C --> :C
 » 6 years ago, # |   +175 When you realize that your rating will decrease, but then contest become unrated
•  » » 6 years ago, # ^ |   0 The opposite happened to me :(
•  » » 6 years ago, # ^ | ← Rev. 3 →   +22 Vice versa, this is me.
 » 6 years ago, # |   -10
 » 6 years ago, # |   +1 I dont remember last time i was able to solve C (Since last 3 contest).
 » 6 years ago, # |   +33 Please don't make this round unrated , for the first time i solved div1 D during contest
•  » » 6 years ago, # ^ |   +117 please make this round unrated because div1D gave MLE on #59
 » 6 years ago, # |   -16 Shouldn't contestants decide whether or not they want this round rated? If there was a poll I think many would still prefer for it to be rated. And if more than 80% (or different fraction) of people want it to be rated then it would be. However, now it's too late since probably many have stopped writing and left after announcement.
•  » » 6 years ago, # ^ |   0 NOPE, CAUSE ITS SURE GOING TO BE 50-50
•  » » » 6 years ago, # ^ |   0 Well, at least then you would end up with a feeling that you made right decision by making it unrated contest.
 » 6 years ago, # |   +48 This must be upsetting for coordinators and problem setter too.I think we should support them and have a little faith in them. :)
•  » » 6 years ago, # ^ |   +23 Agreed, the number of posts saying "I hate you" is too much. Mistakes are bound to happen anywhere, and today's one incorrect model solution is small compared to the thousands of interesting problems that Codeforces has given us.
•  » » » 6 years ago, # ^ |   +26 I can only imagine how much effort it took him to write 8 problems and then only to see the contest to go in vain. Announcing it unrated must have hurt him more than anyone!! If not anything then he gave community 8 new problems to solve!! So less hate comments please
 » 6 years ago, # |   0 How to solve div2 B ?
•  » » 6 years ago, # ^ |   0 Wait.. :)
•  » » 6 years ago, # ^ |   0 for each a_i count how many numbers are divisible by a_i in the rang 0 to 10^k-1 . Then find how many of these numbers fall in the range of k-digit numbers starting with b_i . subtract it from previously counted numbers. The multiplications of these numbers for all i is the answer (mod 10^9+7) .
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Nice explanation. b_i = 0 was a exception.
•  » » » » 6 years ago, # ^ |   0 I didn't do any extra checking for b_i=0 . I passed the system test. What will be the exception, could you tell?
•  » » » » » 6 years ago, # ^ |   0 It depends on method of finding numbers that fall in the range of k-digit numbers starting with b_i. In my method it will give WA for b_i = 0.
•  » » 6 years ago, # ^ |   0 PRETEST 2 ALWAYS FAIL...:(
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 Compute the number of possibilities for the i-th group of digits, then the final result is the product of all those possibilities.To compute the number of possibilities for the i-th group of digits, you can count the number of integers j so that 0 <= j*a_i < b_i*10^(k-1) and add the number of integers j so that (1+b_i)*10^(k-1) <= j*a_i < 10^k.I hope this is clear :)
 » 6 years ago, # |   +13 so there I was... having solved B (hopefully) , thinking about how I may finally have a 1500+ rating or maybe even get a change of color and bla bla .... suddenly this notification -_- I am never gonna get a good rating :'(
 » 6 years ago, # |   +49
•  » » 6 years ago, # ^ |   +5 when do you people have time to make this stuff?
 » 6 years ago, # |   +44 I also wanted to point out that statement + input of Div1C is horrible. Seriously, WHY is the input given in rectangle? Combined with some vector explanation which I couldn't understand, I just stared at the problem statement for about 30 minutes.
•  » » 6 years ago, # ^ |   +7 Maybe in order to make a reasonable legend.
•  » » » 6 years ago, # ^ |   +16 it's still not
 » 6 years ago, # | ← Rev. 2 →   -9 How unlucky can a person be?if you want to find the answer,it's enough to know who is fsps60312.I didn't see anyone more unlucky than him/her.
 » 6 years ago, # |   0 what is the hack for div1 A?
 » 6 years ago, # |   +42 I'm still confused by problem C. Is it asking 'given n points, remove k of them and make the smallest rectangle which encloses them'? Why are the magnets described as rectangles, then?
•  » » 6 years ago, # ^ |   +18 just for lulz
•  » » 6 years ago, # ^ |   0 Yes. Probably because magnets are rectangle in real-life.
 » 6 years ago, # |   +21 Can you please explain in a detailed way what modeled solution was and why it's wrong? Because I was really sure about my solution for Div1A.
•  » » 6 years ago, # ^ |   +5 Can you describe your solution?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I guess everybody printed the minimum value of a[i + N / 2] — a[i] in sorted order :))I'm not sure at all about this solution but I hate the fact that in the latest contests div1A is much harder than some other problem or div1B is very strange and mathemtics problem. D was pretty ok, C also(even though that the task description was very ambiguous
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +25 Consider the follow case: 5 1 2 3 4 5 Printing out a[i + N / 2] - a[i] will get wrong as the answer should be 1 instead of 2.The first step is to ban 5, and if the second ban is 2 (or 3), just ban 1 (or 4). And it is easy to see that banning 1 or 4 in the second ban will get the result of 1 as well. (reverse the banning if the first ban is 1)
•  » » » » 6 years ago, # ^ |   0 I got with a greedy/bruteForce solution, after you sort the set, in the optimal game the first player will move just in corner sides. So he with (n — 1)/2 turns needs to maximize some distance from the preffix set and from its suffix, the remainder distance after to maximize will be the answer.code: linkYour text to link here... Does any one have a counter example of this??
•  » » » » » 6 years ago, # ^ |   +15 Same as the case mentioned above(?)Input this case to your solution gives 2 while the answer should be 1: 5 1 2 3 4 5 
•  » » » » » » 6 years ago, # ^ |   0 What about this one http://pastebin.com/fmV6DTvw ? I didn't manage to submit during the round because it disappeared after some time.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   +15 In the case: 5 1 7 100 130 131 your program gives 31 while the answer should be 6? I wrote this solution in time complexity of O(n!) and this should be correct.The possible first bans will give the following results: (so the first guy should ban 100)1: 31 (as the second guy should ban 130)7: 31 (as the second guy should ban 130)100: 6 (as the second guy should ban 130)130: 31 (as the second guy should ban 7)131: 30 (as the second guy should ban 7)
•  » » » » » » » » 6 years ago, # ^ |   0 the n should be even
•  » » » » » » » » » 6 years ago, # ^ |   0 Why?
•  » » » » » » » » » 6 years ago, # ^ |   0 sorry, my bad. I thought it should be even and now they removed the problem statement, so I'm not sure.
 » 6 years ago, # |   +5 How to solve problem D?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 If the wheel moves n meters then the pin moves n meters around the circle. Reduce this movement to an angle alfa between 0 and 180 degrees. this is how much the pin moves from start to finish. You want to maximize the distance in the x-axis made by this angle. This turns out to be 2*(alfa/2)*r. So the answer is tentatively n-2*(alfa/2)*r divided by speed. But notice that this implies we moved less than n meters, so alfa is actually smaller than before. Just plug in the new values and do the same process. If you do this enough times you will be really close the the real answer.
•  » » » 6 years ago, # ^ |   0 Nevermind, that won't work. It times out on test 3. I found a new method with binary six that gets me all the way to test 8, but then it becomes unable to reach sufficient precision.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Didn't have the time to pass send to the pretests but this works at least for test 1 : I used the equation of a cycloid. x(t)=r*(v*t/r — sin(v*t/r)) Then I use ternary search on d between 0 and r*pi with the start at x=d and the finish at s=d+(f-s).To compute the function to minimize (tfi-tsi), I have a solver that uses binary search.UPD : sorry, WA 4, not precise enough apprently, maybe its just a wrong implementation I don't know.
 » 6 years ago, # |   0 :/
 » 6 years ago, # |   +5 Give me back my up vote :/
•  » » 6 years ago, # ^ |   -6 Give me hints for B?
•  » » 6 years ago, # ^ |   0 come and get it! (بیا بگیرش)!
•  » » » 6 years ago, # ^ |   0 wait... I'll come for you tonight ;)
 » 6 years ago, # | ← Rev. 2 →   -8 just a bad contest...
•  » » 6 years ago, # ^ |   -25 why do you write comments in your stupid language when every one here are from different nationalities!!!
•  » » » 6 years ago, # ^ |   0 do not be rude.
•  » » » » 6 years ago, # ^ |   -20 aint it rude to write bullshit that no one knows in front off a hundred people!!!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -10 This comment has been deleted cause of technical reasons :/
•  » » » 6 years ago, # ^ |   +8 You are stupid more. You can be more polite.
•  » » » 6 years ago, # ^ |   +2 he is stupid for doing that but you cant say any thing you want to this language
•  » » 6 years ago, # ^ |   0 Unfortunately, we are too tell, that there was a mistake in a model solution for problem C. We will remove the problem from the round and the round will be UNRATED. We sincerely apologize for this happening.UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATEDdo you see UNRATED?
 » 6 years ago, # | ← Rev. 2 →   0 How to solve problem Div1 D (REQ)? There are 168 primes up to 1e3.There are 78498 primes up to 1e6.For 168 primes we can build Segmet Tree. But what do for others?
•  » » 6 years ago, # ^ |   +5 I have N * sqrt (N) * some constant around 7(maximum number of primes in the decomposition of a number smaller than 10 ^ 6)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 does it run in time limit?
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +8 According to his submission history, his solution ran in 2979 ms (barely below the 3s limit). I implemented the same thing (but with more overhead since I used prewritten code) and received TLE on pretest 9 (test 30, after some optimizations).There was an announcement in the beginning of the contest about the time limit being changed (presumably increased) to 3 seconds, but I'm still unsure about whether this solution was intended to pass. I think the time limit should either have been stricter (to avoid these solutions) or more tolerant (to make optimization of constant factors unnecessary).
•  » » » » » 6 years ago, # ^ |   +5 I just spent 30mins optimizing my solution and it finally passed. I had to change my factorization from O(sqrtU) to O(number - of - primes - below - sqrtU) which is just ridiculous. My guess is that constant optimizations like these weren't intended, and the time limit is just still too strict.UPD: Maybe we were supposed to factorize numbers in O(logU) using smallest prime table, like TimonKnigge suggested. That seems more reasonable.
•  » » » » » » 6 years ago, # ^ |   0 I actually precomputed the first prime factor and the next divisor of each number in times and O(U), respectively, but nonetheless received TLE on test 30.I won't try to optimize this solution since I now know that a better one exists, but I guess optimizing my implementation of Mo's algorithm would make it pass, too.
•  » » » » » » » 6 years ago, # ^ |   +5 My theory was that the segment tree solution (which I referred to as "my solution", I wasn't specific enough, my bad) in pair with first prime factor optimization is the intended solution and shouldn't ever TLE. Using prime factor optimization on Mo's (like you did) proves nothing since the dominant complexity is still . On the other hand, using it on the segment tree solution removes the square root factor completely.
•  » » » » » » » » 6 years ago, # ^ |   +5 Oh, I see that now, sorry.I only commented about precomputing the next divisor (as opposed to repeatedly computing it every time), though, because it would have slightly improved the complexity from to , where p(x) ≤ 7 is the number of prime factors in x — and this seemed to be important for geniucos's Mo-based solution to pass. Of course, the specific amount of time spent during precomputation doesn't really matter, since the bottleneck lies elsewhere.
•  » » » » 6 years ago, # ^ |   0 my solution didn't pass system test with such complexity
•  » » » » » 6 years ago, # ^ |   0 I had 2979 ms out of 3000=))))Try to optimize small stuff
•  » » » 6 years ago, # ^ |   0 Good =)What did you do?
•  » » 6 years ago, # ^ |   0 Mine is MO's algorithm + modular inverse + the fact that:phi(x) = x * P(1 — 1/div) -> where div is each unique divisor and P() is product.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 Note that phi(range)=prod(range)*{(p-1)/p for all p such that p divides at least one number in the range}. This is like DQUERY on spoj, since we want to know if a prime occurs 0, or >0 times. Use a BIT with multiplication. If sort the queries offline, and sweep over the left endpoint l, and for each prime multiply a[i]*(p-1)/p where i is the first occurrence of p>=l, we can solve the problem in
•  » » 6 years ago, # ^ | ← Rev. 8 →   +30 Note: where pi are the prime divisors of n. I stored the ai in a segment tree so I could query their product quickly.Next, notice that each number up to 1e6 has much less than primefactors, which is about 20. So, for each ai, store its prime divisors, and for each prime divisor, store the next number to the left that also has this prime divisor. Then, for each number ai that has a prime divisor p such that ai is the first number with prime factor p, multiply segmenttree[i] with (p - 1) * p - 1. Then sort all queries by left end points in increasing order, and simply query the segment tree for the answer, and whenever the left end point leaves some position i, for each prime factor p of ai, find the next occurrence of p, say position j > i, and multiply segmenttree[j] with (p - 1) * p - 1.Complexity: calculating the smallest prime divisor of all numbers upto 1e6 is for U the upperbound on the ai, then factoring each number and maintaining the next occurence of each prime is , sorting all queries is O(Q) (for each position you can just store all queries with a left end point on that position), and lastly, updating the segment tree for each left end point is , resulting in the beautiful complexity:Accepted submission: 14153688
•  » » 6 years ago, # ^ |   0 my persistent segtree gave MLE on #59 and MO's algo gave TLE on #30 , idk what should i do
 » 6 years ago, # | ← Rev. 3 →   +3 .
 » 6 years ago, # |   0 I am curious about the solution of Div2.C = = .I think lots of time , but still didn't come up with a good key.
 » 6 years ago, # |   0 "there was a mistake in a model solution for problem C."Was the problem solvable and only the judge's solution was wrong or was there a mistake in the problem statement making it unsolvable?
•  » » 6 years ago, # ^ |   0 no one knows..
•  » » » 6 years ago, # ^ |   -8 I saw some people had solved it before it was removed from the Standings, so they might know whether the problem statement was ok or not.
 » 6 years ago, # |   0 why this greedy wont work for problem c? simply sorting the points...remove the corner points,by finding the minimum value of a[i+rem]-a[i] for i=0..n-1-rem, where rem=n-n/2-n%2+1
•  » » 6 years ago, # ^ |   0 why would it work? games with optimality usually need to consider the recursive tree of game states.
•  » » 6 years ago, # ^ |   0 I love Itachi
 » 6 years ago, # |   +37 >mfw WA on pretest 4 on div1C
 » 6 years ago, # |   0 I couldn't submit anything last 20 minutes. It said page was blocked. You should have just let us keep writing the contest, if you want to make it unrated after the contest that's fine, but not being able to submit code makes me sad.
•  » » 6 years ago, # ^ |   0 I think they always hold this process here in CF, it wasn't this contest particularly And maybe not a big deal! There are a few tasks that are needed to be done behind the scenes and 20-40 mins delay is fine at all
 » 6 years ago, # | ← Rev. 2 →   0 That moment when you spend one hour on D, succeed the test after finding out a stupid mistake, and it is 30 seconds too late to submit.At least I did my first ternary search :)UPD : happy to see a failure ont test 4 anyways
 » 6 years ago, # |   0 Lesson learnt: NEVER EVER use inbuilt pow function in codeforces. It behaves weirdly.
•  » » 6 years ago, # ^ |   0 Can you show us why?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +4 Sure:Pretests Fail: http://codeforces.com/contest/595/submission/14150122
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Huh. I've never seen that before, my submission got through fine using pow. Then again, I do have four WAs on Div. 2 B.I'll be using a custom function from now on. C++ is weird. Thanks!
•  » » » » » 6 years ago, # ^ |   +5 obviously. Pow is for float numbers. If you use it for integral values they got casted to float type and you get precision errors.P.S. It has nothing weird with codeforces, go on and see the docs on C / C++.
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 It has to do with the compiler too, because on VC++ and on ideone.com C++14 I get no problems.That's what most troubled me, because on my PC the answer was correct. Still right about this being wrong usage of POW though.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I think its because of precision issues with floating point numbers. pow is a floating point function so such issues happen. Eg: pow(21, 14) gives me 3243919932521508680
•  » » » » » » 6 years ago, # ^ |   0 use pow(21.0,14) always that you want calculate in C++ a^b write pow(a.0,b)
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Emm, seems to not work correctly on my computer,  long long int a = pow(21.0, 14); cout << a; Still the same answer
•  » » » » » 6 years ago, # ^ |   0 Use powl() instead and see if the problem still persists ?
•  » » 6 years ago, # ^ |   +3 The same happened to me. But you were smarter and confident about your algorithm and figured out the problem.I thought "Maybe the second pretest is not the given example and my algorithm is wrong". Two lessons learned in my case.
 » 6 years ago, # |   +73 Like this if you gave up on the round because problem A seemed too hard.
•  » » 6 years ago, # ^ |   +95 Like this if you're too dumb to realize A is too hard and got pretests passed with ten-lines solution.
•  » » 6 years ago, # ^ |   +21 Just skipped it and solve other problems
 » 6 years ago, # |   0 I think it's little hard for me to solve Div2 B :(
 » 6 years ago, # |   0 Argh, I was fine until I decided to hack some solutions. Apparently solutions with out of bounds array are not hackable, so I just destroyed my own score (thanks for unrated :-D)I wonder why. Is the judge system using clean memory?
 » 6 years ago, # |   +5 Will this round announcement get fewer upvotes than the last round? (Last round has 120 upvotes currently)
 » 6 years ago, # |   +13 Actully 4th task is not about physics. A model of moving can be described like this: let start point be ( - b, 0), start be (0, 0). Start angle of point of circle is a (that's the angle between line centre-point, and line Ox). One can see, that if we want to get finish in time tres, than we should take such a, that  - b + v * tres + cos(a - v * t / r) ≥ f - s, where b = r * cos(a). It can be done through some mathematical analys: inequality is equivalent to v * tres + r * (cos(a) * (cos(tv / r) - 1) - sin(a) * sin(tv / r)) ≥ f - sUsing derivative, we can get, that after this we simply use binary search on $t$. By problem condition, a should be in range [0, 2π], but I haven't proved it. Anyway, this solution passed pretests, so it's not far from truth.
•  » » 6 years ago, # ^ |   -8 Yeah, I know that you can derive it yourself. But derive it yourself by pen and pencil you will need at least 10-15 minutes(of course if you know derivative,how to compute arc length and cosines). The person who will Google "trajectory of point on wheel of bicycle) it will lead him to cycloid(wiki) where all your formulas are written.\n Since it is 80% of problem I think it is unfair.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 We even don't need to use a derivative for finding max(a * cos(φ) + b * sin(φ)). One can see, that so there is an $\alpha$, for which so, $\sqrt{a^{2} + b^{2}}$ is maximum (and, obviously, it can be reached)and something wrong with tex on CF, I don't know why my message wasn't parsed normally
•  » » » » 6 years ago, # ^ |   0 You mistyped the last bracket: "b^{2}{" instead of "b^{2}}".
•  » » 6 years ago, # ^ |   0 Could someone please check why the above solution gives WA for Div-2D. I have done the same thing mentioned in this comment but I'm getting WA on test case 8. Link to my submission.Thank you
 » 6 years ago, # |   +1 Thank God.. It's unrated :)
 » 6 years ago, # |   0 No worry for rating and Failed System test.
 » 6 years ago, # |   +137 Hey guys , the wrong model solution caused a single round to be unrated, didn't cause the world war III to start!!!I believe GlebsHP did his best to prepare the round, but he is after all a human, and no human is free from mistakes.furthermore, this is not the first round which is made unrated because of wrong model solution in codeforces, it happened before with former coordinators, even in topcoder same situation happened before, please don't mix between what happened today and GlebsHP being a new coordinator.
•  » » 6 years ago, # ^ |   0 "even in topcoder." So you're saying that topcoder is recognized as a better platform than Codeforces.
•  » » 6 years ago, # ^ |   -13 I agree with you! GlebsHP has my support (if it is important to someone :D). I only worry about really bad estimation for level of tasks.
•  » » 6 years ago, # ^ |   0 when you are going to set a contest you have to check it 2 or 3 times at least to dont have this kind of mistakes if you cant or wont dont do this at all this isnt ww3 but its not that simple
 » 6 years ago, # |   0 Div2 B using c++ pow -> WA Changed pow to own power function -> ACDDDDD:
•  » » 6 years ago, # ^ |   0 The pow func in C++ sometimes cause trouble because it assumes numbers as floats and the return value gets wrong sometimes while working with ints in code Same thing happened to me previously and left me in confusion :]
•  » » » 6 years ago, # ^ |   0 It's so annoying -.-Worst of all, this isn't the first time this happens to me. I never learn :D
 » 6 years ago, # |   0 http://codeforces.com/contest/595/submission/14159310 Why does this give me compilation error?
•  » » 6 years ago, # ^ |   0 It compiles perfectly in my computer with g++
•  » » » 6 years ago, # ^ |   0 How is it possible? M_PI came from sky or what? :P
•  » » » » 6 years ago, # ^ |   0 I don't know, I only copied the code and compiled without errors or warnings. It seems that some compilers are including M_PI while other aren't. I've never used it...
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Visual Studio 2013 knows M_PI if u were included cmath
•  » » » » » 6 years ago, # ^ |   0 But he told about g++ and submitted in c++11
•  » » 6 years ago, # ^ |   0 I saw some cases where M_PI is not defined, it could be a reason
•  » » » 6 years ago, # ^ |   0 I manually defined pi and it still gives compilation error.
•  » » » 6 years ago, # ^ |   0 I've found this, as example of what you are saying:Your text to link here...
 » 6 years ago, # |   0 Yes, I too feel so he should be back!!Making Div2 ocassionally hard is a good practice indeed !! Adding maths problem reduces my fear from maths problems though I binary searched my answer :P ! But when I see this regularly I loose interest !That is why ZLOBOBER was good... But respecting the coordinator there might be some reasons as to why rounds these days are becoming hard!But I think my rank only depends on how fast I code Problem B . If I cannot I get a bad rank! Only a few people solve C making the ranks totally based on speed and in my opinion it should be balanced on Speed and Problem Solving!
•  » » 6 years ago, # ^ |   0 and more problem solving. in this contest specifically every one solved b and no one solved c(actually d) and for me(my net was going crazy) it was bad lost.
 » 6 years ago, # | ← Rev. 2 →   +10 Is Div.1 A solvable for the given constraints?Edit:I was only able to think of greedy solution for even values of n:A will always remove a position situated on the boundary of the remaining array.Now, whenever B moves, he can select the middle element from the remaining array, to ensure that he can select consecutive elements.So, answer is min{x[i+n/2]-x[i]}.will this give correct answer for n=even?
•  » » 6 years ago, # ^ | ← Rev. 5 →   +14 Yes. Let P(x,n)=min{x[i+n/2]-x[i]}. It is easy to show that P is not greater than answer — if the warrior doesn't care what archer does and delete all a[j] for j < i or j > i+n/2, the result will not greater than x[i+n/2]-x[i].Let's prove P is not smaller than answer. After the warrior take turn, the archer can make P not smaller than it was before warrior's turn, by deleting the median of x.For example: if x is 1 2 3 4 5 6, initial P will be min(4-1,5-2,6-3). If warrior delete 1, archer will delete 4, and x will be 2 3 5 6, P will be min(5-2,6-3), which is not smaller than initial P. If warrior delete 4, archer will delete 3, and x will be 1 2 5 6, P will be min(5-1,6-2).Archer can prevent P from being smaller, and P for n=2 is answer, so initial P is (not smaller than) answer.
•  » » » 6 years ago, # ^ |   0 thanks for your explanation :)
•  » » » 6 years ago, # ^ |   0 Any ideas about why the statement "It is easy to show that P is not greater than answer" doesn't hold for n=odd?I don't see how you implied this statement from n=even.
 » 6 years ago, # |   0 I make mistakes(in fact, I just did, for all the two hours), why shouldn't you? :)If there's a probability for wrong model solutions of 0.01% for every round, the probability for it to ever happen in all the 330 rounds is 1-(1-0.0001)^330 ~= 3.25%
•  » » 6 years ago, # ^ |   +10 I have an experience in preparing a contest, and 0.01% seems to be too small const) It's closer to 1 - 5%, as for me.
 » 6 years ago, # |   +3 The problems are quite interesting and the difficulty is fine. What a pity it is unrated. BTW, can anyone show me how to solve Div2 C/Div1 A? Even the algorithm for the wrong model is fine. I never know how to solve game theory problem
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 For warrior, I was removing first or last element (from remaining set), for archer second or second last element — depending on gap sizes at front & back. But I couldn't solve ties when front & back gaps were equal (it would require to iterate through all existing elements, to resolve ties), was getting WA on 6th pretest.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +20 If n is even, min(a[i+n/2]-a[i] for i to 0~n/2-1) is the answer.If n is odd, min(max(min(a[i+(n+1)/2]-a[j],a[j]-a[i]) for j to i+1~i+(n+1)/2) for i to 0~(n-3)/2) is the answer.It can be proven by mathematical induction.EDIT: Sorry, my odd solution was wrong too. Code
•  » » » 6 years ago, # ^ |   0 How did you arrive at the result for n=odd? Did you try out for small cases like n=5,7,9 etc. and notice a pattern?
•  » » » » 6 years ago, # ^ |   +10 I tried to apply same mathematical induction to odd-case, but it was wrong :(
•  » » » » » 6 years ago, # ^ |   0 What is the counter test?
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +10 51 2 12 22 23if warrior deletes 12, answer will be 1.
 » 6 years ago, # |   -6 why did these past contests was ********
•  » » 6 years ago, # ^ |   -16 first learn english, then type bullshit!!!
•  » » 6 years ago, # ^ |   -16 these past contests WAS?? WAS!!!!!!!!!!!!!
•  » » » 6 years ago, # ^ |   0 i typed half of this comment 10 minutes after the other half :)
•  » » 6 years ago, # ^ |   +19
•  » » » 6 years ago, # ^ |   0 hah LIKE
 » 6 years ago, # |   -13 BTW this one looks very similar to today's A: 377C - Captains Mode
 » 6 years ago, # |   +8 positive point of unrated contests!you don't have to wait for rating changes! :D
 » 6 years ago, # | ← Rev. 2 →   +6 though Div 2 C got removed, could greedy be one of the approaches to it? like first sort the positions and then player 1 would try to delete positions from the end while player 2 would start from the middle?
 » 6 years ago, # |   +3 What was the greedy approach for DIV2 C even if it was incorrect? I was not even able to get an answer for the second pretest? Please help !!
 » 6 years ago, # |   +7
 » 6 years ago, # |   +1 When will the editorial be published?
 » 6 years ago, # |   0 PLEASE HELP!!!This is my code for DIV2 B https://ideone.com/eZXkMxI am simply getting WA in test 2 where as it gives the right answer!!! And CF shows it gives WA! Why???
•  » » 6 years ago, # ^ |   0 Casting double value of power to integer and expecting correct conversion? What about values as 999.999999, wouldn't it evaluate to int value 999?
•  » » » 6 years ago, # ^ |   +3 But why it gives correct result in Codeblocks and ideone?
•  » » » » 6 years ago, # ^ |   0 Because it's a different compiler, different cpu or different OS? Never cast floating values to integers, if you must — add 0.5 before casting. But in this case — you can just multiply by 10 until you get that power.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   -10 or write your own power
•  » » » » » » 6 years ago, # ^ |   -7 SHUT UP!!!!!!
•  » » » » 6 years ago, # ^ |   0 i had the same problem but in codeblocks gives wrong answer for me o_O
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Yup, I had the same problem. Write your own function: int exp (int b, int p) { if (p == 0) { return 1; } else if (p % 2 == 1) { return b * exp(b * b, p >> 1); } else { // if (p % 2 == 0) return exp(b * b, p >> 1); } } 
 » 6 years ago, # |   +1 danilka.pro please elaborate on what the issue with Div2C have been.
 » 6 years ago, # |   0 I think it is no need to set too many queries in one test case in div2 Problem D. :P Because of this, I got TLE with my code using cin/cout. Anyway, it is lucky that this round unrated... haha
 » 6 years ago, # |   +3 Div1 D looks too easy for that slot, Div1 B was too hard for that slot.And Div1 A was impossible for the slot, apparently :P What was the statement about?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -11 Binary search is too hard for Div1 B?
•  » » » 6 years ago, # ^ |   +57 Judging by your 18 submissions to 549H — Degenerate Matrix, I'd say binary search is quite complicated :D
 » 6 years ago, # |   0