halin.george's blog

Codeforces Round #358 (Div. 2)
By halin.george, history, 8 years ago, translation, In English

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 danilka.pro 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:

  1. Subway_Sandwich

  2. mcdonalds

  3. KentuckyFriedChicken

  4. zijue

  5. dacaiji

Div.1:

  1. MrDindows

  2. Um_nik

  3. anta

  4. uwi

  5. Shik

  • Vote: I like it
  • +239
  • Vote: I do not like it

Comments Comments (211)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by halin.george (original revision, translated revision, compare)

→ Reply
»
8 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Semester final! The very next day. :'( But well, who cares? xD

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
»
8 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Hoping to turn green today :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +122 Vote: I do not like it

    Hoping not to turn Green today :D

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      Hoping to remain blue

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Codeforces has invented a way for its users to comment even if they are inside a dream

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        But I think my color is blue, and your color is green...

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hoping to become blue...?

        → Reply
»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

halin.george, your graph is inspiring.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    There's a huge gap from July 2013 to April 2014. He must have trained very hard in that time.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I wish to achieve something like that :') ancien, thanks for making us notice it

    → Reply
»
8 years ago, # |
← Rev. 10   Vote: I like it -30 Vote: I do not like it

break;

→ Reply
»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Email for regular rounds is always saying that the contest duration is 2.5 hours and it will contain 6 problems.

→ Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

it's said that on your birthday everything goes well. lets see :)

→ Reply
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I have went back to green, and it makes me sad for several days QAQ

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

halin.george your graph is truly inspiring for us. hope to get positive rating.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Although there will be a exam tomorrow, thanks for this contest，hoping to turn green(just rating + 1)!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to perform well in this contest..... working hard :-) hope i get blue :-) n its inspring to see graphs like these !! thanks :-)

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

What's up with these hoping comments?

→ Reply
»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

hoping not to repeat the mistakes made in the previous round and making no new mistakes :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The only way to learn is to learn from mistakes :)

    → Reply
»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I don't what I should say.

→ Reply
»
8 years ago, # |
  Vote: I like it +36 Vote: I do not like it

This my first time to take part in Codeforces. I'm very excited!!

→ Reply
»
8 years ago, # |
  Vote: I like it -12 Vote: I do not like it

hoping be a rated contest

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    Hoping that you will learn english

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      No need to be rude.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      think twice about grammar, write once :v

      → Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It will be my first round on codeforces. Just learnt coding this month Wish me luck :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good luck and welcome to CF community!

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

no matter how bad it is or how bad it gets ......i'm going to make it.......

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys I am Beginner from India,is this Contest for me or not? Any suggestions?

→ Reply
»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Series of Contest coming , two div1+div2 contests :D

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    Also in the last 5 days, 4 contests in Codeforces, among them 2 contests are being rated. It's amazing !

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for delicius problems

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish to be Specialist today =D

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Off topic question.

Why do these codes give different output for run(0,3)?

Code with local mid
Code with global mid
→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    global vs local variable.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    Code
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Hoping to turn black and red today

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

GOOD LUCK EVERYONE! GET MORE RATING!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish my rating higher than 1700

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Kek

→ Reply
»
8 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Just look at the top 3 of div 2 participants.

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

what is the point of creating fake accounts?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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...

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    And I thought you were about to say something humourous :P

    → Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Who dis?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    fake accounts , CodeForces must reduction of this phenomenon

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how?

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      Just relax. In McDonalds especially for you we have an open cleaning position. 10$/hour

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        You are good with algorithms but bad as a person. Hope you get banned

        → Reply
»
8 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My facepalm moment when I realised that i had misunderstood D as a harder version of the problem :(

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    when sum(root,V) < 0 you should make it 0

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      before sum(root,V) > a[V] every node will push back to queue.

      although sum(root,V)< 0 it will be pushback

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can it be solve using BFS ? because I use DFS

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Wrong solution:

    3
    1 10 15
    1 -100
    2 115

    your solution doesn't delete any leaf, but need delete leaf number 3.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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..

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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!

    → Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

First time to get pretests passed with 4 problems, I hope they survive the main tests :P

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was my worst contest ever, I spent one hour to solve A and i am still not understanding how to solve it efficiently

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 × 5
    1 + 9 = 2 × 5
    1 + 14 = 3 × 5
    ...

    Even more clearly:
    1 + (4 + 0 × 5) = 1 × 5
    1 + (4 + 1 × 5) = 2 × 5
    1 + (4 + 2 × 5) = 3 × 5
    1 + (4 + 3 × 5) = 4 × 5
    ...

    Do you get it?

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, you just need to find the triangle with largest area... but I have no time to implement it T_T

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it -7 Vote: I do not like it

    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 :(

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate?

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, and this can be optimized to n^2 by using two pointers. All I need is time...

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, it is TLE using ternary search.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ...

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody used hashing in D?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dp :-?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's a pretty simple dp solution: http://mirror.codeforces.com/contest/682/submission/18566989

    The 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.

    → Reply
»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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 ;_;

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

I'm so sick of these red's fakes which win Div 2 contests

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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...

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E (without random shuffle) ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve C ?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 7   Vote: I like it +13 Vote: I do not like it

    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 when
    a[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).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It should be a[v]< max(dist)

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D is exciting, DP but not simply DP :)) :))

→ Reply
»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We participate Out of Competition, so Div 2 rating is not affected. You can uncheck the button "show unnoficial" in the standings

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I think he is referring to the Div 1 people who participate with a fake account.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      He is talking about the 'funny guys' that ended up in first to third position using fake accounts.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will system testing start? :(

→ Reply
»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Use ArrayList instead...

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/682/submission/18551509

http://mirror.codeforces.com/contest/682/submission/18550284

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    BY shuflling the array anti-quick sort test case doesn't work

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

It's incredibly unfair to make such test cases for Div2 B. Every solution that uses java.util.Arrays.sort failed with TLE.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Not all. Only those that passed an array of primitives to Arrays.sort

    → Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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"? :P

But seeing all the java solutions getting TLE in an anti quicksort test case I now feel damn lucky to have been drunk :P

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

So.....fake participants won't be eliminated?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So sad, B problem has a test that kills Arrays.sort in Java. I only had to change long for Long, after results. :(

→ Reply
»
8 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/blog/entry/4827

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Turned Blue :D But.. I can't think of Dp solution for D. Can anyone help me out?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Rating changes disappeared from graph and contest tab of user profiles

Ratings have been updated. My rating improved by 1 :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    And the unrated people from top 10 removed also :D

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +4 Vote: I do not like it

          Registered as in, registered on codeforces with a new handle. Maybe they should inspect all handles that were registered just hours before the contest.

          → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you for eliminating fake accounts! I think it should be stated clearly that fake accounts violate rules of CF.

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Seriously. I missed Blue by 1 rating -_-

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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 .

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Once fake accounts got removed, you should change the list of winners too.

→ Reply
»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not sure how they did it, but you are removed, at least from the top contestants.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Can somebody please explain me what is wrong with my solution for problem C? Thank you in advance! :)

http://mirror.codeforces.com/contest/682/submission/18561628

EDIT: Nvm, I think I got it.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Contest, Well Done!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Check this comment regarding your TLE.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/682/submission/18585400

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply