Kartik-Singh's blog

How to efficiently Implement a Checker for the problem D in CF 1015
By Kartik-Singh, history, 18 months ago, In English

The problem link is : Problem

I can only think of an exponential checker.

What complexity checkers are feasible for contest problems in polygon ?

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

»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kartik-Singh (previous revision, new revision, compare).

→ Reply
»
18 months ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

Let's say we want to eliminate number X then we do so greedily starting from the first occurrence easy to proof its correctness, now go from numbers 0 to n and try to eliminate them, this can be done by storing for each number the indices it occurs in, nlogn for easy implementation, o(n) is easily achievable as well.

We stop at the first number we are able to eliminate and it's our mex.

The general idea of the algorithm is the same as finding the minimum number of segments of length x that cover a set of indices which is doable in o(n) greedily if the indices are sorted

→ Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it -38 Vote: I do not like it

Basically, if (M+1)*K is still less than or equal to N, it is always better to loop from 1 to (N/(M+1)). If (M+1)*K is larger than N, then you can just loop from 1 to K. You do not want to loop from 1 to a smaller number than K, though. I think this is easier than complexity checkers

→ Reply