INOI 2019 Discussion

Let’s discuss INOI 2019 here.
Also fill this https://docs.google.com/spreadsheets/d/1izZiXM3S8TTNy012cl8aVGH12DtXhUqn7ONJaQuZeFI/edit#gid=0

Can someone post a rough idea of the questions?

Problems 1:

You are given N jobs of type 1 and M jobs of type 2. Jobs of type 1 have to be done in their ordered sequence while jobs of type 2 can be done in any order. The order of doing all the jobs can be a mixture of jobs of both type, i.e, you can do the N+M jobs in any order as long as the order of jobs of type 1 is not changed.

Job i of type 1 takes P(i) time to be finished and jobs of type 2 takes Q(j) time to be finished.

Moreover, for all jobs of type 2, you are given T(j), denoting that the jth job must be in progress during the T(j)th second, i.e, if a job to type to starts at S(j) and takes Q(j) second, then S(j)<T_i<=S(j)+Q(j) (unsure where the equality sign was).

Find the minimum time to complete all the N+M tasks.

Subtask 1: N,M<=10 (10 Points)

Subtask 2: N=0, M<=3000 (13 or 16 Points)

Subtask 3: Q(j)=1, N,M<=3000 (13 or 16 Points)

Subtask 4: N, M<=3000 (61 Points)

Problem 2:

You are given an array A of N integers. A sequence of this array is denoted by [i(1), i(2), … i(k)]. This sequence has length k. Note that indices can be repeated too.

This sequence is called interesting if A_i(1)>=A_i(2)>=…>=A_i(k). The cost if this interesting sequence is = min{|i(1)-i(2)|, |i(2)-i(3)|, … |i(k-1)-i(k)|}. Find a sequence of the given array having maximum cost.

Subtask 1 (7 Points): N<=500, A(1)>A(2)>A(3)…>A(N)

Subtask 2 (7 Points): N<=500, A(1)>=A(2)>=A(3)…>=A(N)

Subtask 3 (14 Points): N<=500, All elements of A are distinct.

Subtask 4 (14 Points): N<=500

Subtask 5 (25 Points): N<=5000, All elements of A are distinct.

Subtask 6 (33 Points): N<=5000