LCC '22 Contest 4 S3 - Skewed Statistics

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Bob is an avid chess player who has recently been accused of cheating during a tournament. To defend himself, he has consulted a statistician who has analyzed N of his games (numbered 1 to N), each of which he either won or lost. Each game's opponent was assigned a distinct score a_i representing their skill during that game.

In this scoring system, if a player has a score of X, they will likely beat any opponent with score less than X and be beaten by any opponent with score greater than X. If the scores are equal, they may win or lose the game with equal probability. The minimum possible score is 0 and the maximum possible score is 10^5.

To prove that Bob is innocent, it suffices to assign him a score B that is consistent with the games that he played (i.e. for each game, a statistically likely result occured). Additionally, since the scores are estimates, Bob will consider a score B consistent if there are no more than K games where the result was statistically unlikely. Note that while it's impossible for any two of Bob's opponents to have the same score, Bob may have the same score as one of his opponents.

Please find whether Bob may be assigned a consistent score in this scoring system. If it is possible to do so, please find the minimum and maximum score that he may be assigned.

Input Specification

The first line will contain two space-separated integers, N (1 \le N \le 10^5) and K (1 \le K \le N).

The second line of input will contain N integers, a_1, a_2, ..., a_N (0 \le a_i \le 10^5).

The third line of input will contain N integers, b_1, b_2, ..., b_N (0 \le b_i \le 1). For each game, Bob lost the game if b_i = 0 and he won if b_i = 1.

Output Specification

On the first line, output INNOCENT if Bob may be assigned a score, and GUILTY if he may not.

If he may be assigned a score, output on the second line two space-separated integers, the minimum and maximum score.

Sample Input 1

3 1
5 3 2
1 0 1

Sample Output 1

INNOCENT
2 100000

Sample Explanation 1

Any score greater than 5 is consistent since Bob will likely beat a score of 2 and 5 and K = 1 allows him to ignore a statistically unlikely loss when facing against a score of 3. Therefore, Bob's maximum score is the maximum possible score, 10^5.

Bob may not have a score less than 2 since there would be 2 statistically unlikely results against scores of 2 and 5. However, he may have a score of exactly 2 since there would only be 1 unlikely result, against the score of 5. Therefore, his minimum score is 2.

Sample Input 2

5 1
0 2 10 4 5
1 0 1 0 1

Sample Output 2

GUILTY

Comments

There are no comments at the moment.