Блог пользователя halin.george

Автор halin.george, история, 9 лет назад, По-русски

Всем привет!

17 июня в 19:35 MSK состоится очередной раунд Codeforces #358 для участников из второго дивизиона.

Автором всех задач являюсь я, и это мой дебютный раунд на Codeforces. Надеюсь, что задачи вам понравятся.

Хотелось бы сказать большое спасибо Глебу GlebsHP Евстропову и Данилу danilka.pro Сагунову за помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD

Разбалловка: 500-1000-1500-2000-3000

UPD

Разбор

UPD

Поздравляем победителей!

Div.2:

  1. zijue

  2. dacaiji

  3. dan19

  4. yusufsholeh

  5. BIT-silence

Div.1:

  1. MrDindows

  2. Um_nik

  3. anta

  4. uwi

  5. Shik

  • Проголосовать: нравится
  • +239
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

Hoping to turn green today :D

»
9 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

halin.george, your graph is inspiring.

»
9 лет назад, # |
Rev. 10   Проголосовать: нравится -30 Проголосовать: не нравится

break;

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

What's up with these hoping comments?

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I don't what I should say.

»
9 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

hoping be a rated contest

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hoping for delicius problems

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wish to be Specialist today =D

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Off topic question.

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

Code with local mid
Code with global mid
  • »
    »
    9 лет назад, # ^ |
    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!

  • »
    »
    9 лет назад, # ^ |
    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    global vs local variable.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

    Code
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Hoping to turn black and red today

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

GOOD LUCK EVERYONE! GET MORE RATING!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем halin.george (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wish my rating higher than 1700

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Сложно Ее взгляд упал на строки s и t, длины которых равняются n и m соответственно. Как обычно, Алёне быстро наскучило читать, и она решила переключить внимание на строки s и t

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

 Kek

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

Just look at the top 3 of div 2 participants.

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

what is the point of creating fake accounts?

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится -18 Проголосовать: не нравится

ХОЧУ БОЛЬШЕ МИНУСОВ

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +42 Проголосовать: не нравится

    i'm only 9th 'cause Shokoladnitsa sucks :(

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +35 Проголосовать: не нравится

      Мы в русской ветке. У меня есть неплохая идея, какие хэндлы вам нужно взять на следующий div2-only контест, если сможете занять топ таблицы в правильном порядке.

      Спойлер
  • »
    »
    9 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится -15 Проголосовать: не нравится

    ХОЧУ БОЛЬШЕ МИНУСОВ

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Что-то не так с таблицей результатов: некоторые посылки не отображаются. Например, 1e18 вроде решил первую задачу (посылка 18547785), но этого не видно.

Upd: Fixed

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

»
9 лет назад, # |
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...

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Who dis?

»
9 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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!

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится 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??

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Wrong solution:

    3
    1 10 15
    1 -100
    2 115

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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..

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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!

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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 × 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?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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 ...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anybody used hashing in D?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Dp :-?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There's a pretty simple dp solution: http://codeforces.net/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.

»
9 лет назад, # |
  Проголосовать: нравится +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 ;_;

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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...

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve E (without random shuffle) ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve C ?

  • »
    »
    9 лет назад, # ^ |
    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 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).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will system testing start? :(

»
9 лет назад, # |
  Проголосовать: нравится -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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    Use ArrayList instead...

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -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.

»
9 лет назад, # |
  Проголосовать: нравится 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.net/contest/682/submission/18551509

http://codeforces.net/contest/682/submission/18550284

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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

»
9 лет назад, # |
  Проголосовать: нравится +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"? :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

»
9 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
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.net/blog/entry/4827

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Rating changes disappeared from graph and contest tab of user profiles

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

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Seriously. I missed Blue by 1 rating -_-

»
9 лет назад, # |
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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

»
9 лет назад, # |
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 .

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

http://codeforces.net/contest/682/submission/18561628

EDIT: Nvm, I think I got it.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice Contest, Well Done!

»
9 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Check this comment regarding your TLE.

    • »
      »
      »
      9 лет назад, # ^ |
      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...

»
9 лет назад, # |
  Проголосовать: нравится 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.net/contest/682/submission/18585400

»
8 лет назад, # |
  Проголосовать: нравится 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?