### halin.george's blog

By halin.george, history, 3 years ago, translation, ,

Hi everyone!

Codeforces Round #358 (Div. 2) will take place today on the 17th of June at 19:35 MSK.

I am the author of all the problems, and this is my first round on Codeforces. I hope you will enjoy it.

I'd like to thank Gleb GlebsHP Evstropov and Dan dans Sagunov for helping me in preparing problems, Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

There will be five problems and two hours for solving them. The scoring distribution will be announced later.

UPD

Scoring: 500-1000-1500-2000-3000

UPD

Editoral

UPD

Congratulations to winners!

Div.2:

Div.1:

• +239

 » 3 years ago, # |   0 Auto comment: topic has been translated by halin.george (original revision, translated revision, compare)
•  » » 3 years ago, # ^ | ← Rev. 2 →   -33 The comment is hidden because of too negative feedback, click here to view it
•  » » » 3 years ago, # ^ |   0 Poor trick :/
 » 3 years ago, # |   +56 Semester final! The very next day. :'( But well, who cares? xD
•  » » 3 years ago, # ^ |   +3 In my elementary school, it is also a math final examination. I don't care the score, but I care my father's stick fore when I don't get full score. All in all, I will have this contest in my quilt, and beat everyone who see this comment!
•  » » » 3 years ago, # ^ |   +11 It's very excited.
•  » » » » 3 years ago, # ^ |   +6 Road to Master
•  » » » » » 3 years ago, # ^ |   -21 What's your meaning?
•  » » » » » 3 years ago, # ^ |   0 Road to blue. xD
•  » » » 3 years ago, # ^ |   +9 Every time I saw your ID, I would mis-read it as JiBaYang.(For people who don't understand: This means "my dick itches" in Chinese.)
•  » » » » 3 years ago, # ^ |   0 I thought I was the only one...
•  » » » » 3 years ago, # ^ |   -17 You are bad man!
 » 3 years ago, # |   +46 Hoping to turn green today :D
•  » » 3 years ago, # ^ |   +122 Hoping not to turn Green today :D
•  » » » 3 years ago, # ^ |   -22 Hoping to remain blue
•  » » » » 3 years ago, # ^ |   +13 Codeforces has invented a way for its users to comment even if they are inside a dream
•  » » » » 3 years ago, # ^ |   -14 But I think my color is blue, and your color is green...
•  » » » » 3 years ago, # ^ |   0 Hoping to become blue...?
 » 3 years ago, # |   +47 halin.george, your graph is inspiring.
•  » » 3 years ago, # ^ |   +17 There's a huge gap from July 2013 to April 2014. He must have trained very hard in that time.
•  » » 3 years ago, # ^ |   +14 I wish to achieve something like that :') tsaad, thanks for making us notice it
 » 3 years ago, # | ← Rev. 10 →   -30 break;
 » 3 years ago, # |   +23 Email for regular rounds is always saying that the contest duration is 2.5 hours and it will contain 6 problems.
 » 3 years ago, # |   +21 it's said that on your birthday everything goes well. lets see :)
•  » » 3 years ago, # ^ |   +21 Hey, happy birthday.
•  » » » 3 years ago, # ^ |   0 thank you . and wish you high rating :)
•  » » » » 3 years ago, # ^ |   -7 Happy Birthday! and all the best :)
•  » » » » » 3 years ago, # ^ |   0 thank you :)
•  » » » » » » 3 years ago, # ^ |   0 how old are you?
•  » » 3 years ago, # ^ |   +5 happy birthay amigo
•  » » » 3 years ago, # ^ |   0 Thank you :)
 » 3 years ago, # |   +24 I have went back to green, and it makes me sad for several days QAQ
•  » » 3 years ago, # ^ |   +3 it is sorry.
•  » » » 3 years ago, # ^ |   -33 Hello gay， I love your id！
•  » » » » 3 years ago, # ^ |   0 Why you know he is a gay?
•  » » 3 years ago, # ^ |   +14 It's not green, it's cyan.
•  » » 3 years ago, # ^ |   +8 You will be blue again, I think.
•  » » » 3 years ago, # ^ |   +6 Thank you.
• »
»
»
»
3 years ago, # ^ |
Rev. 2   +5

## Can I get your facebook girl?

•  » » » » » 3 years ago, # ^ |   +15 No.oN
•  » » » » » » 3 years ago, # ^ |   +43 Dat palindrome.
•  » » » » » » 3 years ago, # ^ |   0 No.oИ Hello from Russia :)
•  » » » » » 3 years ago, # ^ |   0 Damn this guy.
•  » » 3 years ago, # ^ |   +3 Oh my god. There is no JIBANCANYANG's message here!!!
•  » » » 3 years ago, # ^ |   0 You can find it here: http://www.codeforces.com/blog/entry/45475?#comment-300556
•  » » » 3 years ago, # ^ |   0 It is here, and somehow he managed a +ve number of likes too! :P
•  » » » » 3 years ago, # ^ |   0 Do you mean I always get oppose?
•  » » 3 years ago, # ^ |   0 You'll make it, xiaoai. ;)
•  » » » 3 years ago, # ^ |   0 Подлизун
•  » » 3 years ago, # ^ |   0 I probably have missed blue this contest, at least I am diamond in league of legends!!!
 » 3 years ago, # |   +3 halin.george your graph is truly inspiring for us. hope to get positive rating.
 » 3 years ago, # |   0 Although there will be a exam tomorrow, thanks for this contest，hoping to turn green(just rating + 1)!
 » 3 years ago, # |   -14 Hurrah!!!!Thanks for the contest.Excited to solve good problems. :)
 » 3 years ago, # |   0 halin.george,after seeing your performance graph,i am inspiring myself to go to the top of the hill!
 » 3 years ago, # |   0 hoping to perform well in this contest..... working hard :-) hope i get blue :-) n its inspring to see graphs like these !! thanks :-)
•  » » 3 years ago, # ^ |   0 Did you light a candle? It may work :)
 » 3 years ago, # |   +20 What's up with these hoping comments?
 » 3 years ago, # |   -6 hoping not to repeat the mistakes made in the previous round and making no new mistakes :D
•  » » 3 years ago, # ^ |   0 The only way to learn is to learn from mistakes :)
 » 3 years ago, # |   -9 I don't what I should say.
 » 3 years ago, # |   +36 This my first time to take part in Codeforces. I'm very excited!!
•  » » 3 years ago, # ^ |   0 All the best man!
• »
»
3 years ago, # ^ |
-15

### Hello,girl.Can I get your facebook?

•  » » » 3 years ago, # ^ |   +1 Sorry.Facebook is a inexistent website in my country.
• »
»
»
»
3 years ago, # ^ |
0

### Can I get your Wechat?

•  » » » » » 3 years ago, # ^ |   0 Nope!
 » 3 years ago, # |   -12 hoping be a rated contest
•  » » 3 years ago, # ^ |   +53 Hoping that you will learn english
•  » » » 3 years ago, # ^ |   +7 No need to be rude.
•  » » » 3 years ago, # ^ |   0 think twice about grammar, write once :v
 » 3 years ago, # |   0 This , my first time to take part in Contest "Codeforces" . I'm very excited <3 !!
 » 3 years ago, # |   +7 It will be my first round on codeforces. Just learnt coding this month Wish me luck :D
•  » » 3 years ago, # ^ |   0 Good luck and welcome to CF community!
•  » » » 3 years ago, # ^ |   0 thanks bro :D
•  » » 3 years ago, # ^ |   0 Good Luck bro ;)
 » 3 years ago, # | ← Rev. 2 →   0 no matter how bad it is or how bad it gets ......i'm going to make it.......
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   -6 i wish to be blue today :D
 » 3 years ago, # |   0 Guys I am Beginner from India,is this Contest for me or not? Any suggestions?
•  » » 3 years ago, # ^ |   +3 Yes, the contest is open for all! All the best. :D
•  » » 3 years ago, # ^ |   0 Work hard bro! :)
•  » » » 3 years ago, # ^ |   0 yes i am,but struct at medium level problem ;)
•  » » 3 years ago, # ^ |   0 this looks like a fake acc
•  » » » 3 years ago, # ^ |   0 no no.....;) i am doing at codechef
 » 3 years ago, # |   +23 Series of Contest coming , two div1+div2 contests :D
•  » » 3 years ago, # ^ | ← Rev. 2 →   +14 Also in the last 5 days, 4 contests in Codeforces, among them 2 contests are being rated. It's amazing !
 » 3 years ago, # |   0 hoping for delicius problems
 » 3 years ago, # |   0 I wish to be Specialist today =D
 » 3 years ago, # |   +4 Off topic question.Why do these codes give different output for run(0,3)? Code with local midvoid run(int l,int r) { if(l==r) ; else { int mid=(l+r)/2; cout<
•  » » 3 years ago, # ^ |   0 semicolumn in if?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 In second code, mid value in run(l, mid) is not same as that of in run(mid + 1, r). You can just simulate the function calls till depth 2 or 3 and you will get to know more clearly!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 In the second code after running run(l, mid) recursion the mid variable will be different for run(mid + 1, r) (because it was modified in the other case). And in the first code it remains the same.
•  » » 3 years ago, # ^ |   +4 global vs local variable.
•  » » 3 years ago, # ^ |   0 if you want to keep mid as a global variable, you have to reassign it after the first recursion so it has the correct value again. Codeint mid; void run(int l,int r) { if(l==r) ; else { mid=(l+r)/2; cout<
 » 3 years ago, # | ← Rev. 2 →   +22 Hoping to turn black and red today
 » 3 years ago, # |   0 GOOD LUCK EVERYONE! GET MORE RATING!
 » 3 years ago, # |   0 Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).
 » 3 years ago, # |   0 Wish my rating higher than 1700
•  » » 3 years ago, # ^ |   0 GOOD LUCK
 » 3 years ago, # |   0 Kek
 » 3 years ago, # |   +39 Just look at the top 3 of div 2 participants.
 » 3 years ago, # | ← Rev. 2 →   0 My hacking page just seems to be loading. I am not able to hack :'(EDIT: Fixed :)
 » 3 years ago, # |   +6 what is the point of creating fake accounts?
 » 3 years ago, # |   0 How to solve D?
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   0 Nice solution, thanks. But how to calculate asymptotic complexity? It's O(nmk), right?
•  » » » » 3 years ago, # ^ |   -10 Yes
•  » » » » 3 years ago, # ^ |   0 No it's worst case O(nmk(n+m)) because of the while loop. That I guess is why it failed on TLE
•  » » » » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ |   +41 U need to go to KFC to solve such hard problems.
•  » » » 3 years ago, # ^ |   +14 You are not funny. Please delete this account. Use your 'normal' one. It's against the rules to have multiple accounts. I wish your red or nutella account get banned for this.
•  » » » 3 years ago, # ^ |   +3 th-th---thanks senpai!
•  » » 3 years ago, # ^ |   +8 D can be solve using dynamic programming. See my submission for details.
•  » » » 3 years ago, # ^ |   0 I made a similar recursive solution and was consistentaly getting WA at pretest 4. In this part of code if(a[i]==b[j]) { ret=max(ret,rec(i+1,j+1,k,1)+1); ret=max(ret,rec(i+1,j+1,k-1,0)+1); } I missed the second line ret=max(ret,rec(i+1,j+1,k-1,0)+1);. I thought that when characters are same then breaking into substring at this point is bad idea.
 » 3 years ago, # | ← Rev. 2 →   +1 The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > au, where au is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u. this statement is not clear...
•  » » 3 years ago, # ^ |   +35 And I thought you were about to say something humourous :P
 » 3 years ago, # |   +9 Who dis?
•  » » 3 years ago, # ^ |   +6 fake accounts , CodeForces must reduction of this phenomenon
•  » » » 3 years ago, # ^ |   0 how?
•  » » » » 3 years ago, # ^ |   0 like how facebook does
•  » » » » » 3 years ago, # ^ |   -17 "Codeforces must reduction of this phenomenon" "must reduction"
•  » » » » » » 3 years ago, # ^ |   0 Yes ,mr.faked
•  » » » 3 years ago, # ^ |   -29 Just relax. In McDonalds especially for you we have an open cleaning position. 10\$/hour
•  » » » » 3 years ago, # ^ |   0 faked accounts used to commercial business , Hello World !! Daaah
•  » » » » 3 years ago, # ^ |   +4 You are good with algorithms but bad as a person. Hope you get banned
 » 3 years ago, # |   +55 The facepalm moment when you realize that you have misinterpreted the variables u, v in the problem C. Normally I use v for child, u for current node. So I messed up in understanding the problem and instead implemented a slightly complicated solution.
•  » » 3 years ago, # ^ |   0 The exact same thing happened to me and I started solving D in the mean time. When I came back to have a look at C for the last time, I realised that I misinterpreted the u,v nodes and then I was able to solve it in 5 mins. Truly Facepalm!
•  » » » 3 years ago, # ^ |   0 My facepalm moment when I realised that i had misunderstood D as a harder version of the problem :(
•  » » 3 years ago, # ^ |   0 Same here. But thankfully realized that the figures in explanation of samples won't make any sense in such an interpretation, hence was forced to look back and check. Still, the notation used in statement is pretty unusual.
 » 3 years ago, # |   0 What is testcase 4 of problem C??????????????I using BFS from root=1 and I remove every child node of V when sum(root,V) > a[V]is it wrong solution??
•  » » 3 years ago, # ^ |   +6 when sum(root,V) < 0 you should make it 0
•  » » » 3 years ago, # ^ |   0 Why ?
•  » » » 3 years ago, # ^ |   0 before sum(root,V) > a[V] every node will push back to queue.although sum(root,V)< 0 it will be pushback
•  » » » » 3 years ago, # ^ |   0 Can it be solve using BFS ? because I use DFS
•  » » » » » 3 years ago, # ^ |   0 Both are fine
•  » » 3 years ago, # ^ |   +4 Wrong solution:31 10 151 -1002 115your solution doesn't delete any leaf, but need delete leaf number 3.
•  » » » 3 years ago, # ^ |   0 why delete leaf number 3?in this case sum(root, 3) should be 15 and a[3] = 15 so i think it isn't sad vertex..
•  » » » » 3 years ago, # ^ |   0 This is why your solution doesn't delete third vertex.But sum(2, 3) = 115 and a[3] = 15, so 2 is sad vertex. This is why you need to delete third vertex.
•  » » 3 years ago, # ^ |   +1 You don't need to check sum(root, V). This is because, the question states that a vertex V is not sad if sum of weights from node V to any node u in it's subtree should be <= a[u], but you are considering only sum from root. There may be a case where weight of root to all it's children is negative. So, we don't have to count the negative weights. For eg., Consider this graph : 1->2->3 Let wt(1->2) be -10, and wt(2->3) be 10. a[1] = 1 , a[2] = 10 , a[3] = 1. Here, vertex 2 is sad, because path 2->3 has weight 10, but a[3] < 10. However, you will end up considering weight as 0, because you will be adding the weight of 1->2 as well, which is not required here. Hope you understand. I haven't taken a look at the test cases yet, but I too had a WA on pretest 4, and this was the change I made to get Pretests Passed verdict. Hope this helped!
 » 3 years ago, # |   +9 First time to get pretests passed with 4 problems, I hope they survive the main tests :P
 » 3 years ago, # |   0 TLE Put me down twice I usually test with random inputs :// submitted got TLE and I didn't submit the latter solutions :/ good game .
 » 3 years ago, # |   0 It was my worst contest ever, I spent one hour to solve A and i am still not understanding how to solve it efficiently
•  » » 3 years ago, # ^ |   +3 You should combine 1 with [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15..] More clearly:1 + 4 = 1 × 51 + 9 = 2 × 51 + 14 = 3 × 5... Even more clearly:1 + (4 + 0 × 5) = 1 × 51 + (4 + 1 × 5) = 2 × 51 + (4 + 2 × 5) = 3 × 51 + (4 + 3 × 5) = 4 × 5... Do you get it?
•  » » » 3 years ago, # ^ |   0 I have a simpler method than that look at 18552140.
•  » » » » 3 years ago, # ^ |   0 It is not a solution.It is about how you should start thinking :)
 » 3 years ago, # |   0 For problem E, you just need to find the triangle with largest area... but I have no time to implement it T_T
•  » » 3 years ago, # ^ | ← Rev. 3 →   -7 You can fix two points, and then run ternary search to find the maximum. It is n²logn. This was the first time I solve E, but I didn't manage to solve C, D for some reason :(
•  » » » 3 years ago, # ^ |   0 Can you please elaborate?
•  » » » 3 years ago, # ^ |   0 You are right, and this can be optimized to n^2 by using two pointers. All I need is time...
•  » » » » 3 years ago, # ^ |   +3 Yes, it is TLE using ternary search.
 » 3 years ago, # |   0 This is my worst round. solution to A failed test 11, I took a long time checking code but still can't find what's wrong. solution to D is the same case, can't find the bug. my rating will have a big decreasing ...
•  » » 3 years ago, # ^ |   0 Maybe you forgot about using long long
•  » » 3 years ago, # ^ |   0 In A, the result can be larger than 32 bit int
•  » » » 3 years ago, # ^ |   0 I am so stupid .......
•  » » » » 3 years ago, # ^ |   0 Don't worry, I made this mistake too :(Using long longs for every A and B question from now on is probably a wise choice...that's what I'm going to do from now on. Overflows have cost me too many points xD
•  » » 3 years ago, # ^ |   0 I got the same result in A test 11, but after using long long int pretest passed .
•  » » 3 years ago, # ^ |   +1 Take a look at my graph and keep fighting bro!! We all have bad days :)
•  » » 3 years ago, # ^ |   0 maybe my solution could help?http://codeforces.com/contest/682/submission/18566989
 » 3 years ago, # |   0 Anybody used hashing in D?
•  » » 3 years ago, # ^ |   0 I did a dp on [i][j][used][using] where used is the # of segments started so far and using is whether a segment is running...I have no idea if this actually works; I just BSed a solution while being frustrated about missing TC 3 on C and it ended up passing pretests lel
•  » » 3 years ago, # ^ |   0 Dp :-?
•  » » 3 years ago, # ^ |   0 There's a pretty simple dp solution: http://codeforces.com/contest/682/submission/18566989The only solution with hashing i can think of is if you used binary search + hashing when "taking" a segment, to quickly find out for how long are both strings the same. Not sure if that solution would be fast enough, though.
 » 3 years ago, # |   +29 Do you care about my sad story?Today my family told me they're not proud of me. ;_;So I decided to compete today, just to get some acceptance ;_;
•  » » 3 years ago, # ^ |   0 And you got +67 rating, your family must be proud of you now :)
•  » » » 3 years ago, # ^ |   0 Unfortunately, they don't. I'm glad the judge at least accepted me
 » 3 years ago, # | ← Rev. 2 →   +30 I'm so sick of these red's fakes which win Div 2 contests
•  » » 3 years ago, # ^ | ← Rev. 2 →   -32 Are u referring to KFC logo being red?
•  » » » 3 years ago, # ^ |   0 Well, registred 3 hours ago, just before the contest -> total newbie here, but able to finish third? Seems legit...
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 ухади.
•  » » » » 3 years ago, # ^ |   -18 What?
 » 3 years ago, # |   +25 When I was hacking, I noticed that this submission 18550167 of problem B included the solution of problem A as comments. Does this count as rule violation? Some contestants might lock their B and be able to obtain a solution of A.I finished C 2 seconds after time's up...
 » 3 years ago, # |   +3 How to solve E (without random shuffle) ?
•  » » 3 years ago, # ^ |   0 I think you should get the convex hull, fix two points, then ternary search the third point for the largest triangle then do the scaling
 » 3 years ago, # |   +5 How to solve C ?
•  » » 3 years ago, # ^ | ← Rev. 7 →   +13 Read about Kadane's algorithm (maximum subarray problem) first (it is very easy — a 5 minute reading). Now let's take a look at some internal node vk. There is a path from root (v1) to that vertex:v1→...→vk The only thing we need to determing is whether vk makes feel sad ANY of the nodes on that path (that sentence is the key to understanding; read it again till everything is clear). The node vk makes some of the nodes on that path feel sad only whena[vk] > max(d(v1, vk), d(v2, vk), ..., d(vk - 1, vk)) Kadane's algorithm helps with finding max(...) value fast during dfs.dfs(v1)maxDist = max(0 + d(v1, v2), 0)↓dfs(v2)maxDist = max(maxDist + d(v2, v3), 0)↓dfs(v3)maxDist = max(maxDist + d(v3, v4), 0)↓...dfs(vk - 1)maxDist = max(maxDist + d(vk - 1, vk), 0) If vk makes someone sad — it is a bad vertex and we have to remove it with all of it's descendants (using the same dfs we calculate how many children every node has).
•  » » » 3 years ago, # ^ |   0 Is the vertex can be categorized as sad if a[k] > d(1,2)+d(2,3)+...+d(k-1,k)?How to deduce it to a[vk] > max(d(v1, vk), d(v2, vk), ..., d(vk - 1, vk))? Thanks
•  » » » 3 years ago, # ^ |   0 It should be a[v]< max(dist)
•  » » » 3 years ago, # ^ |   0 "The only thing we need to determing is whether vk makes feel sad ANY of the nodes on that path", That's ok , But what if vk makes feel sad any node outside the path ?? Because It can make sad node outside the path ,
 » 3 years ago, # |   0 problem D is exciting, DP but not simply DP :)) :))
•  » » 3 years ago, # ^ |   0 How is it any different from LCS? Am I wrong in assuming that the only added condition is that the answer of lcs >= k
•  » » » 3 years ago, # ^ |   0 Yeah abcdef abxef k = 1 LCS: abef
•  » » » » 3 years ago, # ^ |   0 Okay
•  » » 3 years ago, # ^ |   0 http://codeforces.com/contest/682/submission/18564850 Got WA :( Can someone tell what is wrong with this soln?
•  » » » 3 years ago, # ^ |   +3 You're not completely reseting your dp table. Loop until r <= 10, not r < 10.
•  » » » » 3 years ago, # ^ |   0 Thanks :) I realized that too late. :'( Failed in my first attempt to solve a D level problem.
•  » » 3 years ago, # ^ |   0 It is simply dp. Just 20 times more states than regular LCS, and one more line.http://codeforces.com/contest/682/submission/18566989
 » 3 years ago, # |   +47 Guys from Div 1! It's really not fun to see you competing with us, taking rating that we deserve. Why do you dissapoint others? Would you like this situation if you were in Div 2?
•  » » 3 years ago, # ^ |   0 We participate Out of Competition, so Div 2 rating is not affected. You can uncheck the button "show unnoficial" in the standings
•  » » » 3 years ago, # ^ |   +20 I think he is referring to the Div 1 people who participate with a fake account.
•  » » » » 3 years ago, # ^ |   +2 That makes more sense
•  » » » 3 years ago, # ^ |   +9 He is talking about the 'funny guys' that ended up in first to third position using fake accounts.
•  » » 3 years ago, # ^ |   -36 I m really sorry for taking about 300/number of participants which equals about 0.1 rating from you.
 » 3 years ago, # |   0 When will system testing start? :(
•  » » 3 years ago, # ^ |   0 Started.
 » 3 years ago, # |   -15 For problem B test case 105 is anti-quick sort one . So for all problems involving sorting can we hack other's submission by providing anti-quicksort case as in Java Arrays.sort juse quicksort rather than merge sort. Is it valid?
•  » » 3 years ago, # ^ |   -6 Use ArrayList instead...
•  » » » 3 years ago, # ^ |   -13 I know that but I thought that providing anti quick sort test case is against the rules.Once in an Educational round it had an anti quick sort case and after that contest I used to have merge sort implementation in my template but didn't use it.
 » 3 years ago, # |   0 Not a good contest for me..After solving 1 and 2 quickly, i decided that i will not be solving any more problems,but will learn hacking..I hacked one solution,in the 2nd attempt someone declared an array of size 10^5 for the 2nd problem and was using 1 indexing, i tried to give a test case of N = 10^5 but unfortunately it didn't get a Runtime Error..After this some expert in my room was using int ans for calculating the final ans for 1,and he had a long template in his code,i thought to hack it by giving a overflow case (10^6 10^6) and to my surprise it didn't get a WA, later on i observed each line of his template and he had declared "typedef int long long int"...Clearly not a good day..Learn't few things..Looking ahead to future contests :)
 » 3 years ago, # |   0 What's going wrong with problem B, s.o could explain for me the difference between these two solutions one takes only 186ms and the other exceeds the time on test 105 : http://codeforces.com/contest/682/submission/18551509http://codeforces.com/contest/682/submission/18550284
•  » » 3 years ago, # ^ |   -13 BY shuflling the array anti-quick sort test case doesn't work
•  » » 3 years ago, # ^ |   0 Arrays.sort uses quicksort which has a worst case time complexity of n^2. Test 105 must have made this happen. If you shuffle the array, then it will run in closer to nlogn time.
 » 3 years ago, # |   -13 It's incredibly unfair to make such test cases for Div2 B. Every solution that uses java.util.Arrays.sort failed with TLE.
•  » » 3 years ago, # ^ |   +2 Not all. Only those that passed an array of primitives to Arrays.sort
 » 3 years ago, # |   +9 Lesson for everyone, dont use vectors, use static memory always to be safe.My D MLEd on test 59 because I used vector to memoize. Changing to static array makes it AC :/With array: 18565081, with vector: 18558041
 » 3 years ago, # |   +5 for B, I don't know why I thought of adding the numbers to a hashset and then iterate over them and add them in ArrayList and then sort it and find the answer, even though it was such a simple question and later saw the solution I was like "was I drunk today"? :PBut seeing all the java solutions getting TLE in an anti quicksort test case I now feel damn lucky to have been drunk :P
 » 3 years ago, # |   +25 So.....fake participants won't be eliminated?
•  » » 3 years ago, # ^ |   0 You can't prove they are fake
•  » » » 3 years ago, # ^ |   +3 If CF's cheat detector could detect coding styles, then it would be possible.
 » 3 years ago, # |   0 So sad, B problem has a test that kills Arrays.sort in Java. I only had to change long for Long, after results. :(
 » 3 years ago, # | ← Rev. 8 →   0 Edit: never mind, I found out what's in common with the solutions failing B: primitive int arrays. Either Array.sort() is really bad at handling primitive ints as bodmas said, or the unwrapping when you cast Integer objects (from Integer.parseInt) to primitive ints is super slow. Wtf Java!Seems relevant: http://codeforces.com/blog/entry/4827
•  » » 3 years ago, # ^ |   +2 Java uses Quick sort for primitive type sorting, and merge sort for Object Sorting. Quick sort runs in O(N^2) in the worst case, so that alone would TLE your solution. ( Also this does not occur in every problem, sometimes random test cases happen to do that, or the author does it on purpose).Alternatively, a nice strategy is to shuffle the array before you sort, or declare it as Integer/Long instead of int/long, that way it becomes an Object and runs in NLogN.
•  » » » 3 years ago, # ^ |   0 Can I use Integer always or it is slower than int in other operations so I should only use it when I need to sort?
•  » » » » 3 years ago, # ^ |   0 Integer will be slower than int because there will be autoboxing/autounboxing involved with it(you can read about that here).That being said, the performance reduce because of Integer won't create a difference big enough for an AC solution to get TLE in competitive programming for almost all problems.But the best solution before sorting will really be to just shuffle the array.
 » 3 years ago, # |   0 Turned Blue :D But.. I can't think of Dp solution for D. Can anyone help me out?
•  » » 3 years ago, # ^ |   0 I also turned blue :D Hopefully I don't lose it this time. Maybe my solution could help? http://codeforces.com/contest/682/submission/18566989If you already know regular LCS dp, it's not hard to limit it to only take 10 substrings. And for regular LCS dp you can just google it.
 » 3 years ago, # | ← Rev. 2 →   +7 Rating changes disappeared from graph and contest tab of user profilesRatings have been updated. My rating improved by 1 :)
•  » » 3 years ago, # ^ |   0 Yeah
•  » » 3 years ago, # ^ |   +7 And the unrated people from top 10 removed also :D
•  » » » 3 years ago, # ^ |   0 Should be more than top 10, don't you think? Anybody who registered 5 hours before the contest and made it to top 100 is suspicious
•  » » » » 3 years ago, # ^ |   0 I say top 10 by guessing as i only advanced 5 positions.and look to this one ( mikezhw ) he registered 6 hours and ranked 17th, but anyway this is awesome that CodeForces admins made this choice this time :D
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 Registered as in, registered on codeforces with a new handle. Maybe they should inspect all handles that were registered just hours before the contest.
 » 3 years ago, # |   +3 Thank you for eliminating fake accounts! I think it should be stated clearly that fake accounts violate rules of CF.
 » 3 years ago, # |   +4 Seriously. I missed Blue by 1 rating -_-
 » 3 years ago, # | ← Rev. 2 →   +14 Seems like there is something wrong with checker for problem E: UPD: Here is the 18565596, starting from test #33 all outputs are "0 0"s and checker still says it's OK
•  » » 3 years ago, # ^ |   +16 You are undoubtly right, there was a problem with checker. Unfortunately, checker at the moment of the contest duration has not checked that the output triangle has non-degenerate area.This causes a bug in checking if the triangle contains all the points from the input, because it is implemented by checking the sum of three triangle areas equality to the original triangle area, i.e. if the ouput triangle is ABC and checker processes point P to check if it is inside, checker just ensures that S(ABP) + S(APC) + S(PBC) = S(ABC) states true, then it considers a point lying inside. Of course this is not true statement if, for example, A = B = C or the point P lies at the same line as the points A, B and C do (if they do). Of course, now we have fixed this bug and implemented additional checking on the triangle area.This unfortunately caused one solution to have accepted on the final tests (which it shouldn't get), but we have decided not to change the verdict because, firstly, because the participant had "Pretests passed" verdict during the contest, which he should not get the participant, secondly because his solution has the right logic and has some non-crucial bug causing the output triangle to be with degenerate area, and thirdly because we have found it late, very after the system testing. We hope the community will understand our decision right.We are very sorry for that, and I hope that the explanation above will help someone in contests or in preparing of those to not to allow this situation happen again.
 » 3 years ago, # | ← Rev. 3 →   +1 I've just noticed that my rating change increased by 3 , it was +93 but now +96 . Fake accounts have been deleted from scoreboard , I was in 136 place but now in 130 .
 » 3 years ago, # |   +1 Once fake accounts got removed, you should change the list of winners too.
 » 3 years ago, # |   0 dude where is the editorial ?
 » 3 years ago, # |   +40 Well, it looked like a good joke, but in fact it's not. We are really sorry for it and won't do it again. And I politely ask administration to remove us from scoreboard. And sorry one more time.
•  » » 3 years ago, # ^ |   0 I'm not sure how they did it, but you are removed, at least from the top contestants.
 » 3 years ago, # | ← Rev. 2 →   +5 Can somebody please explain me what is wrong with my solution for problem C? Thank you in advance! :)http://codeforces.com/contest/682/submission/18561628EDIT: Nvm, I think I got it.
 » 3 years ago, # |   0 Nice Contest, Well Done!
 » 3 years ago, # | ← Rev. 2 →   0 looking at other people's code for div 2 A (including red coders) the code looks pretty complicated at first sight. What was wrong with my code. It is simple and only a couple of lines long (excluding the includes) 18552140 . Can this code get hacked?
 » 3 years ago, # |   0 Is B even solvable in Java? My solution was literally the same as the solution in the editorial. I even modified it to use BufferedReader and String.split(" ") and it still fails on the last test case...Any ideas how to speed up the input?
•  » » 3 years ago, # ^ |   +1 Check this comment regarding your TLE.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 I just sent the same solution but with ArrayList instead of int array, and it passed. Are Collections.sort() and Arrays.Sort() different?EDIT: nvm, I read that sorting primitives is in quick sort, while sorting objects is in merge sort. Hmm a weird design choice if you ask me...
•  » » » » 3 years ago, # ^ |   0 Hm. I'm not sure, but checking the Java 6 documentation I see the following:Arrays.sort: "The sorting algorithm is a tuned quicksort..."Collections.sort: "The sorting algorithm is a modified mergesort ..."So this could explain it.
 » 3 years ago, # |   0 In D , why is my soln giving memory limit exceeded on n=1000 m=1000 k=10 I have used dp[n+1][m+1][k+1][2] array http://codeforces.com/contest/682/submission/18585400
•  » » 3 years ago, # ^ |   +9 Try to sort the array dimensions, i.e. change it to dp[2][k+1][n+1][m+1]. Will help you a lot for sure.
•  » » » 3 years ago, # ^ |   0 yup that was the problem Point noted
 » 3 years ago, # |   0 What are the prizes?
 » 3 years ago, # |   0 Hi halin.george :D I solved your problem Alyona and Triangles, but i was curious, about find a maximum area of a quadrilateral, instead of a triangle.Do you can help me? To find the maximum area of a quadrilateral in set of points? Do you know any problem about it?