Lich_Sandro's blog

NEERC 2014. Eastern subregional contest.
By Lich_Sandro, 10 years ago, In Russian

Четвертьфинал ЧМ по программированию по Восточному подрегиону NEERC пройдёт с 9 по 12 октября 2014 года в Уральском федеральном университете (г. Екатеринбург). Основной тур состоится 11 октября.

Традиционно на Тимусе будет проходить интернет-версия соревнования.

Официальная группа соревнования: https://vk.com/qf2014. В ней, кроме собственно новостей по четвертьфиналу, я каждый день буду писать по байке на тему истории спортивного программирования (в основном, на Урале, но это как пойдёт). Заходите, читайте, комментируйте.

Кстати, а кто-нибудь знает, даты каких четвертьфиналов NEERC уже известны?

UPD:

На Snarknews появилось расписание четвертьфиналов:

Рыбинск — 14-16 октября

Саратов — 20-22 октября

Москва — 26 октября

Санкт-Петербург — 8 ноября

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the problem E:Magic and Science solution

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

    I guess it's just a lot of boring geometry

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

      Also:

      1. You should construct a physic model of this problem. Some physics knowledges are still needed.

      2. You have to solve one simple differential equation at some point.

      3. In the end you should solve three trigonometric equations that have general form V = A*sin(x) + B and find necessary intervals (when the magion moves quite fast).

      And of course you should properly construct the path magion moves.

      At least all of this were in my solution. As you can see — all inclusive! =) I tried to solve this problem using discrete solution — but I didn't pass the time limit.

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

Where can I found solutions ? Especially the two most hardest ?

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

Can someone who did H and F share their solutions?

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

    F : We need to find some partition of people in two non-empty groups without contradictions in each of groups. It is not hard to prove that if every two people in group don't contradict, then there is no contradiction in all group. So we have next graph: vertexes are people, edges are contradictions in their testimonies. In statement it is said, that this graph can be 2-colored. We need to find its 2-coloring with smallest non-empty set of first color vertexes. It is easy to see that every connected component can be 2-colored in exactly 2 ways that differ by inversing colors of every vertex. It means that we have to color every connected component in 2 colors by simple dfs and blame crime on smallest part. Also there is the case, when nobody contradicts nobody, we can blame anybody (but exactly one person).

    How we check contradictions? Two people don't contradict, if their testimonies are about same location (because everybody could have been there), if their testimonies are about different locations, they contradict if and only if they both have seen somebody (i. e. 1 says 3 was in one location, 2 says it was in another), including them.

    UPD. About absence of more than 2-people contradictions : if we have several people that don't contradict by pairs, than everybody is located in not more than one place by their testimonies, so there is not any "big" contradiction without smaller ones.

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

      Thanks! But I can't understand why this 2-coloring is better than greedily choosing the vertex to be "removed" (treated as criminal). I was choosing the vertex by their degree (in this case, amount of other vertices that has contradicting testimonials with the vertex). It seemed to work and I couldn't find any counterexamples.

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

        As I said, there are only two ways of 2-coloring a connected component (and they differ by inversing the color. If we have connected 2-colored graph with different sizes of independent sets it is partitioned in, and also there are two vertexes with maximal degree in different sets, you can't tell them apart and can pick up one that is in bigger of independent sets at first turn. If you picked up "right" vertex at first turn in the connected component, you are destined to get smallest part, however. So, if you do that greedy one time, you will fail with high probability on some test cases (consisting of several connected components with described qualities).

        So you technique should work if you work for components independently, use random when in doubt and repeat process several times (about 25 should be enough with a fair margin) for each component, using the smallest result you get. But it is much more harder to implement than simple dfs, IMHO.

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

          Nice explanation, thank you very much

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

          What if some component wasn't 2-colorable? A cycle of odd length for example?

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

            Graph is 2-colorable because of statement. Statement says there is a way to 2-color graph ( real innocents and real killers).

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

              Didn't read the statement carefully, my bad!

              Thank you for the explanation.

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

    H : First about algorithm : we will have stack (at first moment it is empty). Stack will contain ghosts and hunters. We will add ghosts and hunters in the same order as in input. We will call ghost and hunter pair, if hunter can attack ghost.

    What can happen when we add new ghost/hunter? 1) Stack is empty. We simply add it to stack. 2) Top of stack is pair to object. Let hunter of that pair attack ghost of that pair and pop the top of stack. 3) Top of stack is not pair to object. We simply add it to stack.

    If stack is empty after we add all 2n objects, we have found match, else there is no match.

    Why it works? Well, it is quite obvious, that solution we have found is always valid, because stack if LIFO. It is a bit harder the other way, though.

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

Could someone please explain me how to solve C?

I've been told that it's solvable using a Segment Tree, but I couldn't come up with a solution.

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

    1) We can in for all letters find their positions in chronological order (first sent, second sent, ..., n-th sent).

    2) Suppose father already knows about letters with a1, a2, ..., ak money (ai is spent/earned money; if money was earned, it is positive, else it is negative) in chronological order (so first was gained/spent a1 roubles, than a2 and so on. Suppose (and s0 = 0). It can be proved that answer is min(s0, s1, ..., sk).

    3) If we add zero in any place of {a}, answer will not change. So we can assume letters say 0 before they are read by father.

    4) So now we will have segment tree on array s1, s2, ..., sn. It will have to add something on suffix (when 0 is changed to x on k-th position, si increases by x for all k ≤ i ≤ n, other si don't change) and say maximum on whole array. It is quite easy to do with lazy updates.

    5) At start si = 0 for all 1 ≤ i ≤ n. Then we process queries in input order next way: when we read next letter (which is k-th in chronological order), which tells about m of money, we add m to sk, sk + 1, ..., sn. After that we print min(0, min(s1, s2, ..., sn)). We can second argument in with our segment tree).

    So total asymptotic is .

    P. S. Input size is quite big and you should use input method as fast as possible (I TLE'd with scanf).

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

      Couldn't think about [2] when trying to solve it :(

      Very good explanation, thanks for the reply!

      → Reply