IOI '15 P3 - Teams - Olympiads Online Judge

IOI '15 P3 - Teams

Points: 35 (partial)

Time limit: 1.4s

Memory limit: 512M

Problem type

Allowed languages

C, C++

There is a class of $N$ ~N~ students, numbered $0$ ~0~ through $N-1$ ~N-1~. Every day the teacher of the class has some projects for the students. Each project has to be completed by a team of students within the same day. The projects may have various difficulty. For each project, the teacher knows the exact size of a team that should work on it.

Different students may prefer different team sizes. More precisely, student $i$ ~i~ can only be assigned to a team of size between $A[i]$ ~A[i]~ and $B[i]$ ~B[i]~ inclusive. On each day, a student may be assigned to at most one team. Some students might not be assigned to any teams. Each team will work on a single project.

The teacher has already chosen the projects for each of the next $Q$ ~Q~ days. For each of these days, determine whether it is possible to assign students to teams so that there is one team working on each project.

Example

Suppose there are $N=4$ ~N=4~ students and $Q=2$ ~Q=2~ days. The students' constraints on team sizes are given in the table below:

Student	0	1	2	3
A	1	2	2	2
B	2	3	3	4

On the first day there are $M=2$ ~M=2~ projects. The required team sizes are $K[0]=1$ ~K[0]=1~ and $K[1]=3$ ~K[1]=3~. These two teams can be formed by assigning student 0 to a team of size 1 and the remaining three students to a team of size 3.

On the second day there are projects $M=2$ ~M=2~ again, but this time the required team sizes are $K[0]=1$ ~K[0]=1~ and $K[1]=1$ ~K[1]=1~. In this case it is not possible to form the teams, as there is only one student who can be in a team of size 1.

Task

You are given the description of all students: $N$ ~N~, $A$ ~A~, and $B$ ~B~, as well as a sequence of $Q$ ~Q~ questions — one about each day. Each question consists of the number $M$ ~M~ of projects on that day and a sequence $K$ ~K~ of length $M$ ~M~ containing the required team sizes. For each question, your program must return whether it is possible to form all the teams.

You need to implement functions:

void init(int N, int A[], int B[])

The grader will call this function first and exactly once.
N: the number of students.
A: an array of length $N$ ~N~: A[i] is the minimum team size for student $i$ ~i~.
B: an array of length $N$ ~N~: B[i] is the maximum team size for student $i$ ~i~.
You may assume that $1 \le A[i] \le B[i] \le N$ ~1 \le A[i] \le B[i] \le N~ for each $i=0,\dots,N-1$ ~i=0,\dots,N-1~.

int can(int M, int K[])

After calling init once, the grader will call this function $Q$ ~Q~ times in a row, once for each day.
M: the number of projects for this day.
K: an array of length $M$ ~M~ containing the required team size for each of these projects.
The function should return 1 if it is possible to form all the required teams and 0 otherwise.
You may assume that $1 \le M \le N$ ~1 \le M \le N~, and that for each $i=0,\dots,M-1$ ~i=0,\dots,M-1~ we have $1 \le K[i] \le N$ ~1 \le K[i] \le N~. Note that the sum of all $K[i]$ ~K[i]~ may exceed $N$ ~N~.

Subtasks

Let us denote by $S$ ~S~ the sum of values of $M$ ~M~ in all calls to can(M, K).

subtask	points	$N$ ~N~	$Q$ ~Q~	Additional Constraints
1	21	$1 \le N \le 100$ ~1 \le N \le 100~	$1 \le Q \le 100$ ~1 \le Q \le 100~	none
2	13	$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~	$Q = 1$ ~Q = 1~	none
3	43	$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~	$1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~	$S \le 100\,000$ ~S \le 100\,000~
4	23	$1 \le N \le 500\,000$ ~1 \le N \le 500\,000~	$1 \le Q \le 200\,000$ ~1 \le Q \le 200\,000~	$S \le 200\,000$ ~S \le 200\,000~

Comments

-5

kobortor commented on Oct. 18, 2016, 3:19 p.m.

Size?

This comment is hidden due to too much negative feedback. Show it anyway.

4

r3mark commented on Oct. 18, 2016, 3:28 p.m. ← edit 2 →

Read the line under the Subtasks header.

Let us denote by $S$ ~S~ the sum of values of $M$ ~M~ in all calls to can(M, K).

-3

kobortor commented on Oct. 18, 2016, 4:06 p.m.

ah thanks, ctrl F wasnt returning anything useful.

4

Xellos commented on Sept. 26, 2016, 1:30 a.m.

Was there 2s time limit during the original IOI contest? It seems pretty tight and this problem has a higher TL on other OJs (Yandex: 8s, wcipeg.com: 5s; my TLE solution passes with 1.5s on wcipeg.com, so it can't be just due to a slower testing machine). If that's not the original TL, I think it should be increased, at least to 3s.

3

FatalEagle commented on Sept. 26, 2016, 1:48 a.m. ← edit 2 →

I don't remember what the time limit was on the official IOI, though we left it at 2s here because there was an AC solution. I've increased the TL to 3s to reflect the other AC solution's max time being 1.5s, and have rejudged all previous submissions.

-7

imaxblue commented on Nov. 5, 2016, 6:13 p.m.

Can you increase memory limit as well? IOI gives you 2048M, as does PEG and other judges

This comment is hidden due to too much negative feedback. Show it anyway.