MikeMirzayanov's blog

ACM-ICPC Southern Subregional (NEERC) Programming Contest 2012
By MikeMirzayanov, 12 years ago, translation, In English

Right now the onsite contest is in progress. You can view the curreny results here.

On Monday you can take part in unofficial contest mirror on http://acm.sgu.ru/. The contest starts on October, 22 (Monday), 2012, 12:00 (UTC). The official results will be integrated into the online contest standings. Hope to see you on [http://acm.sgu.ru/]!

Later the contest will be added as a training in Codeforces::Gym.

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

»
12 years ago, # |
  Vote: I like it -15 Vote: I do not like it

"Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Polygon system"

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

WIN

Problem Tree Queries Online is really great. (spoiler in the first revision)

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

    Any one can be solve it by link-cut tree ? .. .

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

    Can you tell me how to solve the problem Tree Queries Online?

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

is there any site related to this contest and has analysis of the problems ?

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

I'm still stuck at problem K(database optimization). any hint?

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

    Save all submasks of the first part of input (15*N strings or, better, their hashes, in total) in the hashmap. Then you can answer to each query very fast. Also, all submasks and queries should be sorted, this guarantees the correct comparison.

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

Where can I find solutions for this contest, there were a lot of interesting problems.

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

Did anyone solve problem Sultan's Pearls using two pointers method? It has been mentioned on the problem analysis, but now I think that it's wrong because the number of pearls stolen from the table does not always decrease with increasing the number of pearls stolen from the hanging part.

I have a test: n = 10, m = 3, weights are {1000, 1, 1, 1, 1, 1, 1, 1, 3, 1}.

If we steal no pearls from the hanging part, we can steal two pearls from the table:
{1000, 1, 1, 1, 1, 1, 1} + {1, 3, 1} -> {1, 1, 1, 1, 1} + {1, 3, 1}

Then, if we steal one pearl from the hanging part, we can steal only one pearl from the table:
{1000, 1, 1, 1, 1, 1, 1} + {1, 3, 1} -> {1, 1, 1, 1, 1} + {1, 1, 3}

And if we steal two pearls from the hanging part, we can steal two pearls from the table again:
{1000, 1, 1, 1, 1, 1, 1} + {1, 3, 1} -> {1, 1, 1} + {1, 1, 1}

So how to use two pointers method in this problem? Or it doesn't work here?

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

    I modified it a bit, so that the second pointer can move in both directions and it passed (the worst case seems to be n^2, doesn't it?). Instead of two pointers method, we can use binary search to find the position of second pointer.

    By the way, can you share the problem analysis?

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

      That's funny, I think there must be O(n^2) test (what if we make right part like "1 1000 1 ... 1 1000 1")?
      Maybe it's something like 1000*n in worst case?

      I know about binary search, I wonder if there is O(n) solution.

      Problem analysis that I have is in Russian only, recorded with the mobile phone camera, if you still want to watch it, check this link (there also are funny videos from Code Game Challenge on this channel).

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

    You can use binary search to find the rightmost position of the second pointer.

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

    Imagine that we decrease the number of pearls stolen from the hanging end. Greedy order is optimal, so after some math, we're left with queries for the largest prefix sum  ≤ x.

    Now, if the weight w of the last m pearls left on the hanging end after stealing decreases, x inreases and we can use the obvious 2 pointers to answer queries.

    If, in some step, w increases, then x (and the prefix we're looking for) decreases, so the cost of all pearls that can be stolen from the lying end doesn't increase. But in every step, the cost of all pearls stolen from the hanging end decreases as well, so this can't be the best solution. We just skip and wait until the prefix pointed 2 by our 2nd pointer is  ≤ x sometime later, and resume moving the 2nd pointer.

    → Reply