IHaveBeenToldWhatToDo's blog

IZhO 2019 Day 2
By IHaveBeenToldWhatToDo, 6 years ago, In English

Can someone share the results, please?

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

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

https://m.imgur.com/17CHYWa

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

Results

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

There are more participants in the CMS ranking but less in the official site. Which of them will be considered while dividing medals?

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

    In CMS rating is all participant (official and non-official), while official site count only official participants. Medal will be given to official ones

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

What is the official solution for E? I solved it onsite with dp and lazy segtree, but the number of solves confused me (in our team's opinion there were easier problems that were solved less), so I wonder if there is an easier solution.

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

    Convert the problem to the following dp:

    DP[position][answer] — maximum position j, such that the last jump was the interval [j; position] and the number of jumps was answer.

    To get we will have the obvious transition from DP[pos] to DP[pos+1] (the values can stay the same) and we also will have additional transitions. We will just binary search on partial sums to find the closest position to the right, such that we can jump to it and increase the answer in the state. This way we have O(N) transitions for each position.

    We can easily make the state have O(N) by not keeping the position. Now the only last observation is that we only need to consider the largest/last 2 values in the dp and do binary search for them only. This way we get solution.

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

    P.S sorry for my poor English

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

Hi, sorry for necroposting but really interested in problem XorActive and its legitimacy.

Does anyone actually have a provable solution for this problem? I managed to cheat through to AC but my solution fails on some simple test cases with $$$n = 10$$$. Even more notable, the sequence only contains 0s and 1s. I actually believe I have a proof the problem is indeed unsolvable even on only a 01 sequence. Let us simplify the queries, we give a subset of indexes and the interactor returns min(number of 0s, number of 1s). This should be equivalent to the original problems, at least when we concern ourselves only with 01 sequences. So the interactor always returns an integer between $$$1$$$ and $$$50$$$ which makes the number of possible interactions $$$50 ^ {15}$$$ which is strictly less than the number of possible inputs which is around $$$2 ^ {100}$$$. This actually proves there is a class of at least $$$10 ^ 5$$$ possible inputs which we can't differentiate with 15 queries. If this proof is true, I believe such problems shouldn't be posed at olympiads because a contestant has to guess how good the test cases really are.

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

    Note: Although not mentioned in the problem statement, all elements in the sequence a are distinct.

    At the top of oj.uz although it should probably be highlighted. In that case, there is a provably correct solution.

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

      Oh, that explains it! Usually when I solve on oj.uz I tend to not look around the problem statement not to see how many solves it has. Then lost about one hour trying to come up with a solution that works for non-distinct :/. Thanks!

      Although I am interested in whether the problem without the distinct condition is solvable in less than $$$N$$$ queries.

      → Reply