enoone's blog

eJOI 2017 problem discussing

By enoone, history, 7 years ago, In English

Hello everyone I am trying to solve the problem Game from this year's eJOI contest. I know the solution for 60 points (with priority_queue and prefixes), but i'd like to know the solution for 100 points. If there is anyone who has solved it, please tell the solution. Thanks

P.S if you want we can discuss other problems in comments :)

Problems day 1, day 2.

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

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

The required complexity was O(NK). For each query we will solve the complexity will be O(N).

Now we need to be able fast to find the largest element. It's pretty easy. As the elements are  ≤ N we can store for every of the numbers how many times does it appear in the current set. Let's also store the current maximum. For the initial set we simply will itterate all elements, increase the count and find the maximum. Now when we add a element it can either be  ≥  current maximum or  <  than the current maximum. If it's  ≥  we are sure that we will take this number at the current position. Else we will increase the count of the current element. Now we are left just witg finding the new maximum. Well we simply can decrease the current maximum untill we are at a value with count greater than 0. We will decrease the current maximum at most N times and so the complexity will be O(N).

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

    Some participants use priority queue for this problem.I ask from support guy that was at competition ,he said that this problem can solved with count sort.But i don't understand ,how make it with count sort when priority queue already can insert elements .Maybe it complexity will be less than O(N) that you say in comments, i don't know exactly .Can you explain ,how this problem can be solve with count sort ?

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

      Some participants use priority queue for this problem.

      Did they get 100 points with it?

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

        No only 50% ,it is a complexity problem that priority_queue do this.I have idea with segment tree to find max ,but to implement this it was difficult . The complexity for all queries must be O(n). The guy from Russia write it 90% ,but i think he didn't write good this algorithm . With count sort it must be 100% ,how support guy said,but i don't understand that how it can be with count sort .

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

          You can get 60% too. You need to do some optimizations for it.

          And what about support guy. I think he meant the solution of radoslav11, because as kpw29 said Radoslav's ___ solution is the intended one.

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

            maybe , the time was few ,and i can't to understand the solution full that support guy said . I will read and try to solve Radoslav's radoslav11 solution later, when i will have time.

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

    Thanks for your solution.

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

"If there is anyone who solved it" Does being a problemsetter count? =)

Radoslav's radoslav11 solution is the intended one. Some participants used a weird DSU or other approaches. I am eager to know others!

Fun fact from backstage — it was intended to be by far the easiest problem of the second day ;-;

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

OK I now want to discuss the problem Camel of the second day. You can easily get th solution for n=5, so it is 20 points. I think for n>5 i think we must separate it to 5*5 blocks and combine them to get the hole solution. Am I right?

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

    Yes you are right. Solving it for 5x5 (with backtracking for example) should give you an insight that it is quite easy to traverse a 5x5 grid. From there on, it's really handy if you notice that you can pick any starting and ending cell in a 5x5 grid and there is still a solution — a backtracking algorithm given the starting and ending cell finds such solution instantly.

    After you break the whole grid in 5x5 blocks, then you just have to traverse those in a way so that you finally end up in some block adjacent to the first one so that you can finish the tour back to where you started.

    It boils down to precomputing some solutions for 5x5 and using them to build the whole thing. Most solutions also have to handle the cases for N/5 being even or odd differently.

    P.S.

    I was in the scientific committee so feel free to ask about other problems as well. The solutions should be available online soon (in a few days — I hope).

    → Reply