INOI discussion 2021

Ping me when the exam ends for solutions (idk, I left early)

Did you get 200?

Maybe. I reckon I’ll FST tho

What is your score on pretest?

200

Is the exam done?

Yes

Okay, here are rhe solutions

Among Us

The problem is immediately reduced to a directed graph, with edge weights either 1 or 2 (accuse vs vouch).

A bit of fiddling shows that if a vouches for b, both or none of them are imposters. And if a accuses b, exactly 1 of them is an imposter.

The problem is now graph coloring, such that edges of type 1 connect nodes of the same color and edges of type 2 connect nodes of different colors.

For any node in each connected component, color it either of the colors and compute the maximum number of imposters attainable.

String Breaking

Define cost of a subsegment as number of 1s - number of 0s.

Claims (without proofs, figure them yourself).

  1. Every segment except the last should have cost exactly \pm K
  2. All segments should either have positive or negative cost.

Now we try making segments with either positive or negative cost greedily (maximising the length of each segment).

This can be implemented efficiently by maintaining an array B where B[i] is the largest index with prefix sum equal to i.

1 Like

What might the cutoffs be?

Let’s make a spreadsheet.
https://forms.gle/YiiSs1H7bkRkQVLN6

Here are the details: https://docs.google.com/spreadsheets/d/1LyyTCeo7HmwAfBVyRcLpqIyzuL5l5IEILzhrC9d0vk0/edit?usp=sharing

1 Like

Can somebody please help me sort the form values (and add the corresponding add functions)

For future readers of the sheet, the total score column is off by one. :slight_smile:

Expecting either 185 or 170.

I was marked 100 for Among Us + 85 for String Breaking but I expect that I should get 70, since my solution there was O(n^2).

Did anyone else run into this quadratic solution passing time limits?

What was your O(N^2) idea @evenvalue? I’m wondering if it passed due to weak data or because it simply is faster than O(N^2).

Please use your real name (or your cc/cf handle) rather than fake names. All invalid entries have been deleted.

What’s the expected cutoff for class 11? I am getting 170.

I’d say weak data, I was doing a linear search O(n) times.

My O(n^ 2) solution is as follows :

I do a linear search to see how far I can extend the current string piece. Then start over from that point…

Yep, quadratic which jumps to the farthest valid index seems to pass the pretests for 85. Funnily enough, my initial implementation of that ACed all but the last case of the last subtask. I’m pretty sure that it’s easy to restrict the solution to lesser points, so the pretests for P1 seemed sketchy.

2 Likes

How did you prepare for INOI this year can you guide me ?