### Tigutor's blog

By Tigutor, history, 5 years ago, translation,

Hi all!

In two days, at 19:35 MSK Codeforces Round #339 (Div. 1 & Div. 2) will take place. This is an unusual round since we — the problemsetters — are highschool students who participate in the programming training group at high school #179. This round is our first effort and we did our best to make it interesting and bug-free. I invite you all to compete in this round since the problems will be solvable, but even tourist will have to think over some of them. :)

With supervision and control from Mikhail Tikhomirov (endagorion), the problems were developed by: Egor Chunaev (ch_egor), Vasily Alferov (platypus179), Dmitry Sayutin (cdkrot), Timofey Gutor (Tigutor), Maria Fedorkina (MF2000). Mikhail Sorokin (themikemikovi4) and Sergey Aleikin (Derrior) contributed their problem ideas.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements in English, AlexFetisov and winger for testing, and, of course, MikeMirzayanov for unique CodeForces and Polygon systems.

Round will have standard Codeforces rules, with pretests at first, and final tests afterwards. Take care to account for all possible cases.

Best of luck to everyone!

UPD Points for problems are

Div 2. 500-1000-1750-2250-2250, Div 1. 750-1250-1250-2000-2500

UPD Congratulations winners! standings

Div1:

Div2:

UPD Editorial

• +501

 » 5 years ago, # |   +152 Poor english, let's hope the english statements will be better..
•  » » 5 years ago, # ^ | ← Rev. 2 →   +73 Yes, i dont speak english very vell, but lately we'll correct this post. English statements will be created by Delinur, and she know English very well.
•  » » » 5 years ago, # ^ |   0 But you translated Wikipedia...
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 From English to Russian Example This to This
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -33 So this post can be better if you want Delinur to translate it to English, too.
•  » » » » 5 years ago, # ^ |   +7 Deliner->Delinur
•  » » 5 years ago, # ^ |   +14 Statements were pretty clear, thanks for that! problems were also nice and interesting, I really liked C div1 and D div1 :)my only complaint is A div1. there was no idea behind it, just a stupid geometry formula.
 » 5 years ago, # |   +80 i has very very good expect contest, so many prepared people and i like endagorion contest because they very very good. best hope much good statements
•  » » 5 years ago, # ^ |   -40 RIP English (2016 — 2016) Even worse than the blogs english ...
•  » » 5 years ago, # ^ |   +68 isn't it rude to make fun of someone who just prepared a contest for you?
•  » » » 5 years ago, # ^ |   -8 he's just joking about the bad english xDbut he's saying good things about the contestso he's not actually making fun of the author
 » 5 years ago, # |   -40 Yeee, another codeforces round rated. Wishing ratings high to all, hope math problems to see.
•  » » 5 years ago, # ^ |   -33 hope your english to learn
•  » » » 5 years ago, # ^ |   0 This comment is actually funny! I like it!
 » 5 years ago, # |   +83 Google Translate would have done better. :D
•  » » 5 years ago, # ^ |   +23
•  » » » 5 years ago, # ^ |   +42 "we, its drafters — ordinary students, united by the fact that together are engaged in the circle in 179 schools" Somebody help, my sides are leaving the orbit
•  » » » 5 years ago, # ^ |   0 Is this the original post? Hillarious!!! because the problem will be solved, but even the tourist-y have to think about some I bet touristy will scratch his head for the entire duration of contest, as to why the drafters have given solved problems in a contest :D
 » 5 years ago, # | ← Rev. 5 →   +32 The statement of problem B in the last round was horrible, i was not able to understand it till the contest ends.and from the English used in this blog, I think this one will be worse :(please make sure the problem statement be clear and concise to be fair enough for all contestants.
 » 5 years ago, # |   +2 I want to say the Tigutor-у that his knowledge of english is very good.I'm not only fan of Ilya_MSU but fan of Tigutor too. What tasks have you created except Div1E?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +12 You will see the problems authors in the editorial when it is published :)I will keep silence before.
•  » » 5 years ago, # ^ |   +10 Div 1, F, certainly.
 » 5 years ago, # |   +42 How do you know tourist will have to think it over..?
•  » » 5 years ago, # ^ |   +62 Maybe they have asked him?
•  » » 5 years ago, # ^ |   +10 Strong feeling about this : Some new algorithm/trick/concept from some recently published paper will be involved.
 » 5 years ago, # |   +614
•  » » 5 years ago, # ^ |   0 :D :D :D :D :D :D :D :D :D
•  » » 5 years ago, # ^ |   +5 He scared to participate in contest :D
•  » » » 5 years ago, # ^ |   +54 but..
•  » » 5 years ago, # ^ | ← Rev. 2 →   +11 More upvotes on a comment than the post itself :) Tourist is gonna make the contest setter remember who he is.
•  » » » 5 years ago, # ^ |   +3
 » 5 years ago, # |   -20 It's really inspiring to me that someone with less rating than me could hold an CF contest. Thanks!
•  » » 5 years ago, # ^ |   -51 I'm so sure in Tigutor that I'm going to cut my balls off if he won't be red in a month. Just like Ilya_MSU
•  » » » 5 years ago, # ^ |   +22 I'll remind You to do so. ;)I'm waiting for next month.
•  » » » » 5 years ago, # ^ |   -15 S/He seems careless! Maybe s/he is the girlfriend of IlyaMSU?
•  » » » » » 5 years ago, # ^ |   0 I'd like to but I'm not. :(
•  » » » 5 years ago, # ^ |   -22 Username relevant.
•  » » » 5 years ago, # ^ |   0 I don't want to underestimate from anyone but he has Registered 18 months ago and the maximum rate he can get 1514 and now you say that he will be red in a month do you actually think so
•  » » » » 5 years ago, # ^ |   +8 Thanks a lot for your research
•  » » » » » 5 years ago, # ^ |   0 research!! it just a click on his handle
•  » » 5 years ago, # ^ |   0 how rude are you!!!! he created a contest for you.
 » 5 years ago, # |   +25 I enjoy contests by lower rating writers. They usually contain interesting problems that involves creative thinking.
•  » » 5 years ago, # ^ |   -28 Has endagorion too low rating for you?
 » 5 years ago, # |   -23 I think there are at least 3 problem eassy in CF round 339.
•  » » 5 years ago, # ^ |   +5 No buddy. All problems are solvable by you if you are coder like Tourist :)
•  » » » 5 years ago, # ^ |   0 why you must compare with tourist... you must do better and you must solve problems even tourist cant... you must make it solvable.
•  » » » » 5 years ago, # ^ |   0 It is quite impossible for him . I know him very closly
 » 5 years ago, # | ← Rev. 2 →   -52 Your code here... 
•  » » 5 years ago, # ^ |   +2 Spam detected :P
•  » » » 5 years ago, # ^ |   -14 thanks!
 » 5 years ago, # |   +5 A contest prepared by so many people is my worst nightmare. Hope for the best though.
 » 5 years ago, # |   +12 I'm new here, could you tell me if there's a difference between Div. 1 and Div. 2? Thanks
•  » » 5 years ago, # ^ |   0 Hello, Div 1 is more difficult and is generally for contestants with a rating >=1900. On the other hand, Div 2 is easier and for less experienced competitors.
•  » » 5 years ago, # ^ |   +5 When the contesters take part in Codeforces contest, they raise or lower their rating that reflects their ability to solve the tasks. The rating is a modification of Elo rating, several details can be read in a fuller form. According to the rating, the contestants are split into two divisions: the second one (the weaker one, amateurs) and the first one (the stronger one, pros). The contestants who don't take part in contests and those whose rating is below 1900 belong to the second division. The 1900+ rating means that you're part of the first division. Usually two types of contests are held on Codeforces: for the second division contestants (the first division contestants can take part there out of competition) and for both divisions. The first contest type contains simpler and learning-oriented tasks.
•  » » 5 years ago, # ^ |   +12 What is your div1 account?
•  » » 5 years ago, # ^ |   0 Difference between Div. 1 and Div. 2
 » 5 years ago, # | ← Rev. 2 →   0 To be honest I don't think the English is poor...quite clear for me...
•  » » 5 years ago, # ^ |   +14 they edited it, the last version was a bit funny but if you tried your best you could understand what it meant
•  » » » 5 years ago, # ^ |   -16 yes!Initial revision is really funny!Look, like this one : << I invite all of you write this round >>.!!
 » 5 years ago, # | ← Rev. 2 →   0 BTW,you're good-looking:D[user:Tigutor]
•  » » 5 years ago, # ^ |   +10 Aren't you male?
•  » » » 5 years ago, # ^ |   +11 Yes...But it doesn't matter to praise him...
•  » » » 5 years ago, # ^ |   -8 He is a she. No guy praises another guy for looks bro, unless gay.Otherwise, chinese names gender neutral. I know a girl who has same name as her.
•  » » » » 5 years ago, # ^ |   +8 it's quite normal for us to praise other's looking no matter what the gender you are,if you like.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Alright, I accept that. But YOU are a girl, unless, your name is gender neutral and you are gay(which is cool, btw) :)
•  » » » » » » 5 years ago, # ^ |   0 but you're wrong.maybe there's something different between our culture.anyway,stop talking about this.
•  » » » » » » » 5 years ago, # ^ |   0 Eeek!!! No offence to you sir, our cultures are probably different.
•  » » » » » » » » 5 years ago, # ^ |   +4 Okay.good luck for the coming contest
•  » » 5 years ago, # ^ |   +110
 » 5 years ago, # |   -49 哇塞高中生出题好厉害也！
 » 5 years ago, # |   +37 I hope tourist takes part in this round and talk about the difficulty
 » 5 years ago, # |   0 "even tourist will have to think over some of them" certainly tricky questions are expected looking forward to it
 » 5 years ago, # |   0 Does the scoring mean that the difficulty of div2 D & div2 E is the same?!
•  » » 5 years ago, # ^ |   +9 It's difficult to say. For decent div1 coders it may be same. For good div2 coders it may not.
 » 5 years ago, # |   -69 The comment is hidden because of too negative feedback, click here to view it
•  » » 5 years ago, # ^ |   +49 Look, a self-predicting comment!
•  » » 5 years ago, # ^ |   +12 Make here as a link to your comment, then it'll be perfect :)
•  » » 5 years ago, # ^ |   0 I was just testing my time machine and it works well
 » 5 years ago, # |   +2 Can someone plz explain the second testcase in DIV-2 1000 points....
•  » » 5 years ago, # ^ |   +9 What is 'product'? I don't get it....
•  » » » 5 years ago, # ^ |   +8 Now I got it.. Product means multiply... My english is terrible....
 » 5 years ago, # |   0 If i get WA in pretest then also 50 points will be deducted?
•  » » 5 years ago, # ^ |   +4 yes, but if you don't AC that problem , there will be no decrease on your total score.
•  » » » 5 years ago, # ^ |   0 this is what Codeforces says : "there is 50 points penalty for submission which fails the pretests or resubmission (except failure on the first test, denial of judgement or similar verdicts). "
 » 5 years ago, # |   +17 I'm becoming newbie today n:). So happy to achieve this feat. Feeling gratefull. after being hacked 3 times. :)
•  » » 5 years ago, # ^ |   0 :)
 » 5 years ago, # | ← Rev. 2 →   +15 Well. That could've gone better.But dat number of pretests... I really hope not to fail systests now :D
 » 5 years ago, # |   +41 Let the hate begin!
•  » » 5 years ago, # ^ |   +23 He did hint at problems being hard, but people laughed him off because of his weak english.
•  » » » 5 years ago, # ^ |   +8 I cried at your comment XD
 » 5 years ago, # |   +3 Will the tests which lead to successful hacks be used for system testing?
•  » » 5 years ago, # ^ |   +4 Yes.
 » 5 years ago, # |   +5 Do we need convex hull in div2C or we can find the smallest radius without it?
•  » » 5 years ago, # ^ |   0 Min from distances to all edges.
•  » » 5 years ago, # ^ |   0 No, because points are given clockwise or anticlockwise direction.
•  » » 5 years ago, # ^ |   0 Look at the second test
•  » » 5 years ago, # ^ |   +5 You just need to find the point on the polygon closest to P and the one farthest away, the one closest to it is going to be on one of the edges ( so check each edge), the one farthest away is going to be one of the vertices ( so check each vertex ) Let MAX be the largest distance to P and MIN be the shortest distance to p. Then the aswer is (MAX*MAX-MIN*MIN)*PI.No convex hull required.
•  » » » 5 years ago, # ^ |   -7 the one closest to it is going to be on one of the edges wrong.Consider the segment with end points -1,2 and 1,2. The minimumis at point 0,1.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 read more careful, 0,1 is on the edge
•  » » » 5 years ago, # ^ |   0 I tried something similar , but I was checking for min distance on vertex too. Can you clarify a bit more why the one closest is going to be on one of the edges?
•  » » » » 5 years ago, # ^ |   0 It could be that the point which is closest to p is an endpoint of some line segment. In general, for a given line segment if the projection of p lies on that line segment then that's the closest point to p on that segment. If not, then the point which is closest to p is going to end up being one of the endpoints of that segment.
•  » » 5 years ago, # ^ |   0 I think we just need to find the point of intersection of each side with normal from origin to that side. If it lies within that segment, then that point is to be used to find minimum radius, otherwise, the smaller distance to origin from the 2 end points of the segment are to be taken as candidates for minimum.Waiting for editorial.
•  » » » 5 years ago, # ^ |   0 edge is not the same thing as vertex. The one farthest away is a vertex, the one closest is ON an edge.
•  » » » » 5 years ago, # ^ |   0 Oh, read it wrong. My bad :)
•  » » 5 years ago, # ^ |   +1 we can do it without convex hull also. to find shortest distance of each line segment from center first find distance of both points from center and then check if the line having slope equal to the perpendicular of this lines egment and passing through center intersects the line segment or not. if yes, calculate intersection point as well as its distance from centre. take minimum of all calculated distances.this is the smallest radius.
 » 5 years ago, # |   0 I don't think Div1 B and C worth the same score. T^T
 » 5 years ago, # |   +19 What's the idea behind Div2 Problem C pretest 3?
•  » » 5 years ago, # ^ |   0 I tried a naive solution by finding nearest and farthest radial points of the polygon. Guess there is more to it. This approach works for the illustrations
•  » » 5 years ago, # ^ |   0 I suppose something like: 3 0 0 -1 1 1 1 0 2 
•  » » 5 years ago, # ^ |   +60 I think this
•  » » » 5 years ago, # ^ |   +9 How did you make that colorful and cool drawing?
•  » » » » 5 years ago, # ^ |   0 Umm, microsoft paint? Then post a picture comment here.
•  » » » 5 years ago, # ^ |   +3 You are right. Something like this :)
 » 5 years ago, # |   -6 Div2 B time limit was a bit too strict I thought
•  » » 5 years ago, # ^ |   0 Dont use python or biginteger.
•  » » 5 years ago, # ^ |   +5 No! You must check if the given number is beautiful (reading it as a string). If it isn't beautiful, save it for the final step. For each beautiful number, you have (lenght-1) zeros. So, if the number is only composed by one "1", and this one must be at the first position (because the restrictions), you don't need to do estrictly a "product", because most of them are one "1" and a bunch of "0". You need to save the sum of total zeros of beautiful numbers called "zSum". So, if the non-beautiful number is zero, the answer is zero. Else, the answer is a string composed by the non-beautiful number (remember to read it as a string, because the lenght can be 100000 as maximum) and then "zSum" zeros. I took me a few submissions before figure it out.
•  » » » 5 years ago, # ^ |   0 Yes, my java submission counts number of zeros and appends a 1 or the non-beautiful number at the front. In java, it TL-ed on test 8, but in c++ it did not. Minor optimizations could drastically change the verdict for this problem. That is why I think this TL was too strict(I wonder how hard it was to pass for python users...)
•  » » » » 5 years ago, # ^ |   0
•  » » » » » 5 years ago, # ^ |   0 Not a Java expert, but I guess you shouldn't use Scanner for reading inputs.. use BufferedReader instead because of time complexity... Also it's not wise to print "0" (I mean characters) in a loop, instead store in a string and then print the string...
•  » » » » 5 years ago, # ^ |   0 Oh, sorry then. Yes, I submitted it in C++.
 » 5 years ago, # |   +16 The test case 1 900000000000000000 12345678, helped me earn 1800 points in the contest by hacking the first problem of almost every user in my room. My best ranking ever, thanks to hacks.Actually python rocks for this question.
•  » » 5 years ago, # ^ |   0 Whats the correct answer?
•  » » » 5 years ago, # ^ |   +3 1 12345678 152415765279684, is the correct answer
•  » » » » 5 years ago, # ^ |   -6 I think 1 12345678 152415765279684 108064748184340920 is the correct answer
•  » » » » » 5 years ago, # ^ |   0 I think with C++, something like taking logs should have been used. Damn so much overflow :\
•  » » » » » » 5 years ago, # ^ |   +3 The only you need is to check whether if LONG_LONG_MAX/n
•  » » » » 5 years ago, # ^ |   0 My solution with unsigned long long int fails :\ Another -1 so
•  » » » » 5 years ago, # ^ |   0 FFFFFFFFFUUUUUUUUUUUUUUUUU----------------Arithmetic overflow is such a bitch....It gets me every time...
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 deleted
 » 5 years ago, # |   0 Div2B pretest 9? how?
•  » » 5 years ago, # ^ |   0 This one checked if your program could answer correctly the case where all numbers were beautiful
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 What?? There's always 1 non beautiful number..
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 at least n - 1 beautiful numbers
•  » » » » 5 years ago, # ^ |   0 some number of tanks of one country was removed from the game, hence the number of tanks of this country may not remain beautiful.may may may mayit just guarantees for atleast n-1 beautiful numbers. never for atleast 1 non beautiful no
•  » » » » 5 years ago, # ^ |   0 There is always one number subtracted from, but it might remain a beautiful number. Confusing, I know :P
•  » » » 5 years ago, # ^ |   0 And here i was thinking i can hack some submissions because of this. -_-
•  » » 5 years ago, # ^ |   0 Statement isn't clear, especially for those, who is a new in compatetive programming like me. Turns out, it can be solven in a few minutes(< 10), but because of its statement I couldn't at all:(
 » 5 years ago, # | ← Rev. 2 →   +12 There could be a lot of hacks on problem A if not third pretest(
•  » » 5 years ago, # ^ |   +23 There could be a lot of hacks on every problem if not these good pretests :)I think it was a bit cruel — to give samples which can be solved with "point-point" distance, without "point-segment". And at the same time there was no crazy hack fun...
•  » » » 5 years ago, # ^ |   0 I figured out the point-segment thing with concave polygons after failing the 3rd pretest, but didn't have time to code it all...Effing geometry.
 » 5 years ago, # |   +5 I remember some people were joking about the difficulty of the problems before the contest... Anything to say? :P
 » 5 years ago, # |   0 Can anyone explain Div 2 C? My idea was to find the minimum distance from P to the polygon and the maximum distance and then pi*(max*max-min*min)
•  » » 5 years ago, # ^ |   +1 I don't know correct solution, but yours fails at this test:4 0 0-1 -10 21 -10 1
•  » » » 5 years ago, # ^ |   0 My idea was exactly similar to this comment Now I'm confused
•  » » » 5 years ago, # ^ |   0 You're wrong. The minimum distance doesn't have to be the distance from P to one of the point in the polygon.For example, for the test: 3 0 0 0 2 -1 1 1 1 The minimum distance is 1 while not sqrt(2).
•  » » 5 years ago, # ^ |   +6 Minimum distance doesn't always lie on vertices.eg 3 2 -11 0 2 13 0ans = pi*(4-1) = 3*pi.
•  » » » 5 years ago, # ^ |   0 I handled that issue
•  » » » » 5 years ago, # ^ |   0 Then maybe you didn't handle the finite line issue.The min point must lie on the finite line segment.If you just considered perpendicular distance from point p to line then you might fail some cases.
•  » » » » 5 years ago, # ^ |   +1 I also handled the issue and failed test 3 : maybe you forgot the edge between the first and last vertex.
•  » » » » » 5 years ago, # ^ |   0 Maybe your solution to find the minimum distance from a point to a segment has some bugs.
•  » » » » » » 5 years ago, # ^ |   0 No I just added the last edge and it passed all tests :)
 » 5 years ago, # |   +7 I think this round is too difficult ....
 » 5 years ago, # | ← Rev. 2 →   +6 What is the intended approach for div 1 D?The same question for a single query can be solved using dp on trees in linear time which led to me to come up with an approach which involved using HLD to compute dp at the bare minimum required nodes (klogk for each query I think) but the implementation was turning out to be too long so I went off to sleep instead.
•  » » 5 years ago, # ^ |   0 You can first build the auxillary tree, which is a compressed tree of the marked nodes in O(klogN) time consisting of O(k) nodes and then apply the same dp on this tree in O(k). For implementation details on how to build the auxillary tree, refer my soln here
 » 5 years ago, # |   +17 Div2 A should've been named Hack those overflows.
 » 5 years ago, # |   0 My WA solution for div2 C was to compute minimum and maximum radius, find difference between circles and output. I specially handled the case in which all radii were the same(answer =0)I claim that any radius between [minradius,maxradius] can be attained by some point in the polygon. Is this false?
•  » » 5 years ago, # ^ |   0 3 0 0 -2 1 2 1 0 2submit it
 » 5 years ago, # |   +3 Thanks for great div2A! 22 successful hacks are non penis canina. My hacks: 1 1000000000000000000 1000000000 1 1000000000000000000 536870912 1 1000000000000000000 536870913 536870912 = 2 ^ 29
•  » » 5 years ago, # ^ |   0 Very good!
•  » » 5 years ago, # ^ |   0 second test case can be used to hack unsigned right , awesome
•  » » » 5 years ago, # ^ |   0 Yep, and the third one is the test, which generates overflowed long long less than 10^18 and greater than previous one.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 In first redaction 1 ≤ k ≤ 109 but we thought that it is big trap for Div2A.
•  » » 5 years ago, # ^ |   0 Can you describe how do you find second and third tests?
 » 5 years ago, # |   +13 Thank you for strong pretest for B!
 » 5 years ago, # | ← Rev. 2 →   -32 I hate Div. 1 A. No interesting idea, just applying mathematical formulas and crying when wrong answer on pretest #3 shows up and then finding a typo in one of these formulas :'(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +23 I agree div1A doesn't find its place in any contest it's a stupid problem.
•  » » » 5 years ago, # ^ |   +9 But we struggled with it. It was for us.
•  » » » 5 years ago, # ^ |   +6 I think this problem fits well in some ICPC-style contest. However, CF round is not ICPC :)
•  » » » » 5 years ago, # ^ |   +14 I don't understand what you all are talking about. I see the only problem with it: some guys could use prewritten geometry and get accepted a little faster (several minutes). I haven't used it.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 It is the great problem to have a lot of hacks/challenges :)
•  » » » » 5 years ago, # ^ |   +13 I don't think it is a good idea to have an ugly problem for the sole purpose of allowing people to hack more
•  » » » 5 years ago, # ^ |   +30 I just used the ternary search for each side of polygon
•  » » » » 5 years ago, # ^ |   +3 same here but got TLE on test 37 :(
•  » » » » 5 years ago, # ^ |   +3 Same here, but could not get AC during contest. Missed the line segment between 1st and last point :(. Code Link
•  » » » 5 years ago, # ^ |   +8 I don't get it. Why your comment gets +28 while mine gets -32? Is there something wrong with my comment which doesn't meet Codeforces standards?
•  » » 5 years ago, # ^ |   +7 By mathematical formulas you mean distance between points and distance between point and line? They are well known and quite easy. Actually, geometry problems are quite rare on codeforces, so it's good to have them sometimes.
•  » » » 5 years ago, # ^ |   +5 'Well known' — yes. Quite easy? Well... (between points ok, that's easy, but I didn't remember the formula for the distance between a point and a line and I had to deduce it by myself)Also there surely are many much better geometry problems than that.
•  » » » » 5 years ago, # ^ |   0 We have this formula on the lesson in 8 form: abs(a*x0+b*y0+c)/sqrt(a^2+b^2) x0, y0 — point's coordinates
•  » » 5 years ago, # ^ |   +6 There is an interesting, simple idea. However, there's also annoying geometry. If P was inside the polygon, though, it could've made an easy div1A without the annoying stuff.
 » 5 years ago, # |   0 Any One Please tell me that is What is "Hacked".After my submission I received a message that solution is hacked...
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 This means another contestant has found a case when your program produce wrong output. In short, your solution is wrong.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 thanks .... trungpham90
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 It means someone found bug in your solution and found test in which your code fails. So, your solution incorrect and you should find bug and resend solution.
•  » » » 5 years ago, # ^ |   0 thanks.. balalaika
 » 5 years ago, # | ← Rev. 2 →   0 Thank you for preparing such a contest like this!Although I don't pass Div.2 C,this contest is well! Thanks everyone!
 » 5 years ago, # |   +9 At this time tourist
 » 5 years ago, # |   0 What is test case 9 in div2B?
•  » » 5 years ago, # ^ |   0 Do this 210 10
•  » » » 5 years ago, # ^ |   0 My code gives correct answer for these test cases. still wa on test case 9. http://pastebin.com/rz7D6CKm
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Your code doesn't give true answer. It gives 010. Answer 100
•  » » » » » 5 years ago, # ^ |   0 It gives 100 for me on my system.
•  » » » » » » 5 years ago, # ^ |   0 Maybe you used 'cout' and 'printf' together,aren't you? When you use this ,please don't use 'ios::sync_with_stdio(false)'.
•  » » » » » » » 5 years ago, # ^ |   0 Yup, that was my mistake :(
•  » » 5 years ago, # ^ |   0 something like410 10 10 10
•  » » 5 years ago, # ^ |   0 the number of the removed country is also beautiful .try this : 10 10 10
 » 5 years ago, # | ← Rev. 2 →   +24 The only problem I liked from this set was Div1 D :(
•  » » 5 years ago, # ^ |   0 Seriously? My code started working after the contest (on pretests) and it's 300 lines. I don't like it. Idea is simple: there is a stupid algorithm with time O(n+k). How to fit the queries? Just compress the graph to make it O(k) vertices. Or do you have another solution?
•  » » » 5 years ago, # ^ |   +33 I liked the problem D too.My solution is slightly above 100 lines; the idea is to compute the answer in offline and to use maps with small-to-big optimization.
•  » » » » 5 years ago, # ^ |   +71 And I just processed 64 queries at once using bitmasks :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +18 My solution is heavily based on LCA. We sort vertices from the query in the Euler order (it's computed in one of LCA implementations anyway). Then it's optimal to take consecutive vertices whose LCA has the largest depth and disconnect them by deleting their LCA. If LCA is also a selected vertex, we need to delete some of its children, also -1 case is handled here. The only difficulty is how to implement this idea in the best way, but anyhow it should be O((N + K)logN).
•  » » 5 years ago, # ^ |   +25 What about div. 1 C? I know you enjoy palindromes :)
 » 5 years ago, # |   +19 Any idea in DIV2E/DIV1C? There are no DP, right? Just only some tricky but easy-to-implement construction? :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +15 If we have two letters with odd ai then the answer is 0. Otherwise the answer is g = gcd(ai).Let's build such string:1) If all ai is even then we can build a block of length with occurrences of the i-th letter (in any order). And then copy that block g - 1 times, each time reversing it. Easy to see that we will have exactly g palindromes (because g is even).2) If we have some odd ai then g is odd. So for each even ai the value is also even. So we can build g identical palindrome blocks of the length , where the letter with odd ai will be in the middle and all the letters will occur times.It's not hard to prove that the answer can't be greater than g.
 » 5 years ago, # |   +10 I don't like Div2B statement — take too much time to figure out that numbers could be very long etc etc. One of these tasks where statement reading takes the same (or more) time as solution finding and coding.
 » 5 years ago, # |   +23 Authors at this moment...system testing
•  » » 5 years ago, # ^ |   +9 We're sorry, because The Great Admin now in taxi and hurry to start system testing)
 » 5 years ago, # | ← Rev. 3 →   0 When I read the problem statement of Div2.B at first, I could not understand. By repeating to read the statement many times, I noticed that "find the product" stands for calculating , and then I could solve immediately. By and large, the accounts for sample case are too short for me.
 » 5 years ago, # |   +27 Div1A is really great for Educational Round. Authors would do better by PM'ing Edvard with this task. I know that it's wrong, but I was badly confused about this right from the start of the contest.
•  » » 5 years ago, # ^ |   +5 Did you participate in Education Rounds with geometry problems? In the first one, half of solutions were hacked due to precision problems. In the second one, even the author solution had precision problems and they had to increase the error tolerance 1000 times. I think it is not a coincidence that there are no geometry problems in the last 3 Education Rounds. Too much work to get them right when your adversaries have 24 hours to find challenging cases. Unless you want to restrict coordinates to be less than 100 and set required precision to 1e-2.
 » 5 years ago, # |   +22 Its very funny that participants who have 26 successful hacks on A failed A on system testing :)
•  » » 5 years ago, # ^ |   +10 Anyway, they earned a lot of hacking score (besides they didn't solve the A)
 » 5 years ago, # |   +164
•  » » 5 years ago, # ^ |   +3 Is that Endagorion in the background?Tourist fanboys everywhere -__-
 » 5 years ago, # |   0 Super Contest, I got a lot of fun!!!!!!
•  » » 5 years ago, # ^ |   +3 And KPACUBO got a lot of fun!!!
 » 5 years ago, # |   +1 Look there, running code: here
 » 5 years ago, # |   +5 Why system testing stuck at 100% ?
 » 5 years ago, # | ← Rev. 2 →   -25 Thanks to authors! : )
 » 5 years ago, # |   +1 Endagorion tomorrow published editorial, please wait...
•  » » 5 years ago, # ^ |   +4 and you will publish the announce 3 days ago
•  » » 5 years ago, # ^ | ← Rev. 2 →   +7 Well it's tomorrow , still no editorial published
 » 5 years ago, # |   0 div2 D. Skills what's the answer of 3 5 1 0 4 0 4 1
 » 5 years ago, # | ← Rev. 4 →   0 Another test case for Div. 2 A: 9007199515875289 9007199515875289 94906267 
•  » » 5 years ago, # ^ |   0 K <= 10^9 but in your test is more
•  » » » 5 years ago, # ^ |   0 Sorry, I have replaced the big K with 94906267 (<= 10^9).
 » 5 years ago, # | ← Rev. 2 →   0 My code working fine on my machine but failed system test for the same code. Working fine on custom invocation also.
•  » » 5 years ago, # ^ |   +1 I'm sorry to say there's no way that code's "working fine". You're getting an overflow error, checking that it doesn't become smaller isn't enough, as it can overflow into a bigger number.For instance, consider numbers modulo 40, k = 4. The powers are 4, 16, 24. 24 is clearly wrong, but it's still higher than 16. Your code won't detect this kind of error.What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right.
•  » » » 5 years ago, # ^ |   0 Sorry I misread the Jury's output as mine and vice-versa, Thanks btw :)
 » 5 years ago, # |   0 Don't know why it failed system test ? code
•  » » 5 years ago, # ^ |   +2 Looks almost perfect to me, maybe a bit overcomplicated. The problem seems to be you're forgetting the last return value on you function bool check(string s);which should be returning true at the end, if it doesn't catch one of the false conditions. It seems you got lucky and the undefined return value is usually true, but it's bound to be false sometime.Here's a hint: this kind of mistake is something that can be detected by your compiler. Make sure you compile with warnings enabled! With g++ this is done with the flags:g++ -Wall -Wextra -Werror(Of course there's more warning flags, but these should do for most things)
•  » » » 5 years ago, # ^ |   0 Thanks got it :) Why I did this mistake
•  » » » 5 years ago, # ^ |   0 Do you know how to set these conditions in Sublime Text?
•  » » » » 5 years ago, # ^ |   +3
 » 5 years ago, # |   0 Ratings Updated!
•  » » 5 years ago, # ^ |   +1 We have exactly similar ratings, fine)
 » 5 years ago, # |   -22 the worst contest I see in codeforces problem B was unclear
•  » » 5 years ago, # ^ |   +4 Can't agree with "worst", was quite well overall.But Div2B is bad, I agree with that. Statement is over-complicated a lot.
•  » » » 5 years ago, # ^ |   +1 As for me it was one of the best problems during last several rounds because it is the one i have just solved and only thanks to it i have become a "specialist") And it is the one you haven't solved (from what you have tried to solve), i know(
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +1 Congrats :)Yea I've failed on that one — algo was correct, but I didn't checked all branches correctness. My failing case was where non-beautiful number comes before 0 in sequence, so I printed "nonbeautifulnumber0" instead of "0". After self-analysis I blame my bad emotions about problem statement — because of them I wasn't very concentrated when checking.Besides that, its very easy problem. ProblemStatementComplexity > ProblemComplexity. I really hate these ones (and my hate is what caused these bad emotions) :)
 » 5 years ago, # |   +5 That moment when you realize you failed test 3 on Div2 C because you forgot the edge between the first vertex and the last one...
 » 5 years ago, # |   +22 Div. 2 D is interesting except for asking the final value of the numbers, that adds nothing but boring and time consuming implementation.
•  » » 5 years ago, # ^ |   +8 I was thinking about and decided that it doesn't add a lot of code, and has some advantages. Firstly, you can check participant's answer more precisely.Secondly, you could detect [potential] situation when participant's solution is better than jury's one and report.
•  » » » 5 years ago, # ^ |   +6 It's true a lot of lines of code aren't added but the logic behind them takes a lot of time to think and debug properly. It costed me 15 minutes to code it on top of the 30 minutes used to find the best value.1º Indeed, but I still think the problem is already good without them, maybe just asking the minimun value and the number of maximum values used is enough.2º That's not a job for contestants.
•  » » » » 5 years ago, # ^ |   +8 2) Yes, but first reason still applies =)What about your idea to output a number of full skills and the minimum level I think it is too spoilerish, because allows to guess that the maximums can be taken greedily.
 » 5 years ago, # |   0 Can anybody please help me where my div2 A problem is getting wrong. ?Code link — http://ideone.com/EzXlNfInput case : 1 999999999999999999 1000000000My output : 1 1000000000 1000000000000000000 Correct output : 1 1000000000
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 You are using doubles for l and r, doubles have precision problems. It's probably representing 1000000000000000000 and 999999999999999999 as the same number.You should store l and r in long long and use doubles to check possible overflow.
•  » » » 5 years ago, # ^ |   0 Ok thanks :)
 » 5 years ago, # |   0 Was long intended to fail the tests (Test 24) in Div 2 A in JAVA ? I changed my code to BigInteger and it passed. I'm sure a lot of people used the method I did. All I did was preprocess the powers, store them in a TreeSet and print subSet(l, r+1) (which is an inbuilt method in JAVA TreeSet (similar to C++ std::set)) which prints all the elements in the range [l,r]. You can do this by adding it to a vector, then sorting etc, same thing.I don't think these solutions should have failed. This is just my opinion. Here is the WA code and AC code. Only changed Long to BigInteger, nothing else
•  » » 5 years ago, # ^ |   +1 You need to be clever if you use 64 bit ints (java long) in order to avoid overflow errors. Echoing a similar answer I already gave:Checking that the numbers are in the correct range isn't enough, as they can overflow and land in the range again. For instance, consider numbers modulo 40, k = 4, and [l,r] = [3,25]. The powers are 4, 16, 24, etc. Since the third number should be 64, 24 is clearly wrong, but it's still in the [l,r] range so your program will print it out.What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right and you don't have overflow errors.
•  » » 5 years ago, # ^ |   +7 This problem basically asks you to properly handle the overflow. If there exists an input which make your code fail, then your code should fail (no excuse).You can deal with overflow problem without having to rely on BigInteger.From your code, you only need to add one line before start *= k; if ( start * k > LIMIT ) break; // check overflow (LIMIT can be 10^18, or you can use 'r') start *= k; But wait, start * k can be overflow, can't it? Yes, so change it to this: if ( start > LIMIT / k ) break; start *= k; You don't need BigInteger at all.
 » 5 years ago, # | ← Rev. 2 →   0 (http://imgur.com/JckabmD) Why is my output wrong?
•  » » 5 years ago, # ^ |   0 That number is clearly not a power of k, and it's appearing due to overflow errors. See http://codeforces.com/blog/entry/22726?#comment-272811 or http://codeforces.com/blog/entry/22726?#comment-272774 for a better explanation.
 » 5 years ago, # |   +3 Got WA in problem a, initially I was using long double, and I lost a lot of time because apparently codeforces wont work correctly with %Lf. So I switched to double, then I got WA because I needed long double precision. What was the point of div2 a? To get me not to use c++?
•  » » 5 years ago, # ^ |   0 Yes I agree. The entire objective of a Div 2 A problem is defeated. It is just to check if you can implement basic ideas. itu, thanks for your explanation!
 » 5 years ago, # |   +3 Oh, I didn't know that Decimal in Python is so slow. TL56 on Div2 C :( And the same solution with the usual Float is correct.
•  » » 5 years ago, # ^ |   0 Its not "decimal in python", its "python" itself who is slow :)
•  » » » 5 years ago, # ^ |   0 It is ok for the problems like Div2 A-C. I just mustn't be too greedy for precision in 2C=1A.
•  » » » » 5 years ago, # ^ |   0 Well yea, I was using it before. But then I've failed to implement some solutions because it was 40 times slower than C#. So I've decided to switch.And I believe two active languages is a bad idea for competitive — it is better to master one (there is a lot of cases to study, like overflows, reading 1e9 test inputs, etc etc).
•  » » 5 years ago, # ^ |   0 On the bright side you got to hack my botched handling of vertical lines.
 » 5 years ago, # |   +4 Div2 problem A, good example how useful Biginteger can be.
•  » » 5 years ago, # ^ |   0 BigInteger Will get TL, Muhaha.
•  » » » 5 years ago, # ^ |   +1 it won't BigInteger submission
•  » » » 5 years ago, # ^ |   0 logk r BigInteger multiplications. That definitely wouldn't time out.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Not sure about C++, but in C# we have "decimal" type which can store up to 28-29 digits (basically it is int128 with "floating point position").I also have another somewhere interesting solution for C#:Do all the math on regular long type (int64) inside the "checked { }" block which force compiler to check all math operations for overflow. If got an exception -> break cycle.
•  » » » 5 years ago, # ^ |   0 Cool solution!Also, there's BigInteger in C# (in System.Numerics), which is also fast (in such small case).To Java Users : ...... and easier to write. 15385528
•  » » » 5 years ago, # ^ |   +5 I think It's fair to say that decimal can be used more like int97 or unsigned int96 rather than int128. Because mantissa is only 96 bits plus 1 sign bit.
•  » » 5 years ago, # ^ |   0 No need ;)
 » 5 years ago, # |   +39 Typical GNU C++: pair s = pair (13.3, 14.4); cerr << s.first << ' ' << s.second << endl; No warnings. if (rand() % 10 < a.size()) puts("0"); naive.cpp: In function ‘int main()’: naive.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (rand() % 10 < a.size()) puts("0");
•  » » 5 years ago, # ^ |   0 Sad but logical.With floating point types being silently and implicitly converted to integers all the way in the history of C/C++, it is only logical to extend this property to simple aggregate types as well. So, no warning, as in int x = 4.59;.Regarding rand() % 10, there is no way to tell that the result of int rand() is actually non-negative, except if we go and analyze the source of function rand(). In the general case, it would be impossible for a compiler to do (with halting problem as a subproblem). Why rand() returns int and not unsigned is however a good question — why, indeed?And the problem the compiler warns about gets quite real with if (rand() % 10 - 10 < a.size()) when the part rand() % 10 - 10 is converted to unsigned (~4 billion) before comparison takes place.
•  » » » 5 years ago, # ^ |   0 I don't understand why this get warning: int ans2 = (long double) (10 + rand()); cerr << ans << endl; naive.cpp: In function ‘int main()’: naive.cpp:85:38: warning: conversion to ‘int’ from ‘long double’ may alter its value [-Wconversion] int ans = (long double) (10 + rand());but conversion for pair don't. My solution for A fails today because of that.And about comparing of signed and unsigned values. Why it can't compare them in the following way: if signed value is negative then we know answer, otherwise compare them in unsigned type?
•  » » » » 5 years ago, # ^ |   +8 Oh, there's -Wconversion which is not covered by -Wall or -Wextra. Didn't remember that, sorry!Now that's actually strange. In my hand-rolled implementation of pair  (version 1, version 2), such usage does trigger a warning with -Wconversion right where it should. Perhaps the library authors do something more clever, or, theoretically, not detecting the warning in the library code might be a compiler bug.
•  » » » » 5 years ago, # ^ |   +8 Regarding comparison of signed to unsigned, that would be a really clever move if there was a processor instruction to do exactly that. Looks like that's not the case, and the alternative is to issue a branch instruction, which may be an expensive operation on a modern PC. And C/C++ compilers usually produce efficient (while not necessarily intended) code by default.Also, legacy software may depend on the current documented behavior.
 » 5 years ago, # |   +1 Not knowing how to know when overflow will occur in power costed me getting to expert. Oh well, atleast I learnt something today. :)
 » 5 years ago, # |   0 Can someone tell me which edge case did I miss for DIV2B ? http://codeforces.com/contest/614/submission/15367847
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 310 10 10There are cases without any non-beautiful numbers. In this situation you nb variable will remain uninitialized when you write it out and... oups.
•  » » » 5 years ago, # ^ |   0 I have handled that case. http://ideone.com/Rxsi4u
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 It seems your code fails for such a non-beautiful number:100005Its start from '1' AND have zeroes. So you count these zeroes towards the final answer, but also printing the number as it is. So 4 more zeroes than necessary.
•  » » » 5 years ago, # ^ |   0 Thanks Beresta
 » 5 years ago, # | ← Rev. 2 →   -18 Picture removed.
•  » » 5 years ago, # ^ |   -12 For DIV-2 C / DIV-1 A
•  » » 5 years ago, # ^ |   0 Please don't take it personally but honestly speaking I don't like this picture. A national flag is the symbol of independence and sovereignty of a country. Inappropriate uses of a national flag is not appreciable. May be you didn't do it purposely. But you should know that we can't disrespect our country by using our national flag inappropriately. As a Bangladeshi, my request is please remove this picture. It hurts my feelings. I don't want to see a big hole and some stripes on our flag.
•  » » 5 years ago, # ^ |   +1 I'm not sure with the question, but I guess, the answer is yes.I also fell for the notorious test case #3. My solution was: find the furthest and closest point among the N given points to P. Apparently the "among the N given points" part is wrong. The closest point is not necessarily one of the N points.consider this case: 3 0 0 -1 1 1 1 0 2The closest point is (0, 1) which is not among the 3 points in input.
 » 5 years ago, # |   +2 So where is the tutorial ?
•  » » 5 years ago, # ^ |   +1 They said it will be posted tomorrow.
 » 5 years ago, # |   0 can anyone tell me what is the logic behind div2 B ?
•  » » 5 years ago, # ^ |   +4 The beautiful number are in the form of 1, 10, 100, 1000, 10000, ..., and there is at most one non beautiful number. So you only need to print the non-beautiful number, followed by as many zeroes as there can be. However, you should be careful with the case where there is zero or no non-beautiful number.
 » 5 years ago, # |   +10 WOW!!! We have 9 Legendary grandmaster now!!! :D
•  » » 5 years ago, # ^ |   +7 There were only 5 after the rating changes if I remember correctly. I wonder what happened, wasn't the new system supposed to counter rank inflation?
 » 5 years ago, # | ← Rev. 2 →   +31 I passed the pretest of problem D with a little issue, and I skipped my old solution and lost 145 points when I found the issue. But when I submitted my old solution today I just surprisingly found it pass the system test.Your text to link here...This is the correct one. Just press "compare" to view the old code and the obvious issue.
 » 5 years ago, # |   -6 It seems that the contest will be with no Editorial :(
•  » » 5 years ago, # ^ |   +3
 » 5 years ago, # |   0 NICE
 » 5 years ago, # |   0 That moment when you realise that E is solvable faster than all other problems (except A). :(Just because there's no different cases and the most complex operation is modular plus.
 » 5 years ago, # |   +90
 » 5 years ago, # |   0 hello, have a question: is double on the system a single-precision float? because i believe my solution of the problem C of DIV-2 was correct and on my computer i had correct outputs and apparently on the system it has output different answers.
•  » » 5 years ago, # ^ |   0 No. I don't know any system where double has a single precision.
•  » » 5 years ago, # ^ |   0 Use %lld to read numbers.
 » 5 years ago, # | ← Rev. 2 →   0 I think problem A is one of the most Hacked problems on Codeforces.I hacked 11 and an other 15 solutions failed system test .every one will know how to handle overflow after this contest :D .
 » 5 years ago, # |   +31 just another way to describe div-2 A
•  » » 5 years ago, # ^ |   +3 how did you do in the contest? I am surprised that you found time. Syllabus finished?
 » 5 years ago, # |   0 I am getting wrong answer on Case 56 for Div2 C . i used ternary search.. Can someone please help ???
•  » » 5 years ago, # ^ |   0 if( abs(x2-x1) < 10e-10 ) I feel vertical lines you don't like.
•  » » » 5 years ago, # ^ |   0 Oh thanks buddy , got accepted.. I owe you one :) :)
 » 5 years ago, # |   +6 There wont be any editorial for this round?!
•  » » 5 years ago, # ^ |   +2 should have been published today
 » 5 years ago, # |   0 How to solve problem C from Div.2? I assumed that it is necessary to subtract the area of the minimum of the maximum circumference. But it is not so. Thanks
•  » » 5 years ago, # ^ |   0 Find the largest (R) and smallest (r) distance from point to the rectangle. Then calculate pi*R^2 — pi*r^2
•  » » 5 years ago, # ^ |   0 Yes we need to find the area between the farthest point as radius and the nearest point as radius. farthest point is just the vertex at maximum distance from P , but the nearest point can be a vertex or an edge . So just find the distance between each edge and P and take minimum.
•  » » »