IARCS Online Programming Contest, Jun 2006
Advanced Division Question Paper
--------------------------------------------------------------------------------
Welcome, venkatanathan.A (login id: venkatkenshi).
--------------------------------------------------------------------------------
venkatanathan.A first started download at Sat Jun 10 16:38:39 2006
--------------------------------------------------------------------------------
Problem 1: Red Card
Problem 2: Homework
--------------------------------------------------------------------------------
Problem 1: Red Card
The government of Siruseri issues a red coloured identity card to its Permanent Residents. A Permanent Resident of Siruseri is for all practical purposes a citizen of Siruseri. This has encouraged a large number of alien workers to apply for this status symbol.
The process of obtaining a red card is rather complicated and involves N stages. At each stage, an officer of the Siruseri government will examine the papers submitted by the applicant and verify that it meets some specific requirements. In order to speed up the process, the government has appointed M officials to handle the papers at each stage. Unfortunately, not all these officials are equally efficient. However, as part of the "Open Government" policy, the Siruseri government has released data on how long each official takes to process an application (in number of days).
In order to prevent the efficient officials from being swamped, the M×N officials have been grouped into M channels. A channel contains one official for each stage. An applicant may choose any channel and may also switch channels as he clears the N stages. However, these changes are restricted. A channel change is permitted only in between stages and not in the middle of a stage. Moreover, an applicant in channel i can only change to channel i+1. However, an application is also allowed to shift from channel M to channel 1. There is no limit on the number of channel changes.
For example, here is a description of the efficiency of the officials with 3 channels and 4 stages:
Channel 1 2 6 1 8
Channel 2 3 6 2 6
Channel 3 4 2 3 6
In this example, one option would be to simply stick to channel 1, which would take 17 days. However, an applicant could start with Channel 2, shift to Channel 3 for stage 2, then shift to Channel 1 for stage 3 and finally shift to Channel 2 for stage 4. This would take 12 days. You can check that an applicant cannot do better than this.
Your task is to determine the minimum number of days in which an applicant can complete all the stages.
Input format
The first line contains two integers N and M, indicating the number of stages and the number of channels, respectively. This is followed by M lines containing N integers each. The jth integer on line i+1 (1 ≤ i ≤ M) is the time taken by the jth stage official on channel i.
Output format
A single integer indicating the minimum number of days required to complete all the stages.
Test Data:
You may assume 1 ≤ N ≤ 2000 and 1 ≤ M ≤ 1000.
Example:
Here is the sample input and output corresponding to the example above.
Sample Input
4 3
2 6 1 8
3 6 2 6
4 2 3 6
Sample Output
12
--------------------------------------------------------------------------------
Problem 2: Homework
A teacher assigns homework at the beginning of the first day of class. Each homework problem carries one mark, plus a bonus if submitted within a specified number of days. The deadline for earning the bonus and the number of bonus marks are different for each homework problem. For instance, if a problem has a deadline of 6 days and carries bonus 10 marks, then it earns 10 bonus marks provided it is submitted before the end of the 6th day.
Each homework problem takes exactly one day to complete. For instance, suppose there are seven problems with deadlines and bonuses as follows:
Problem number 1 2 3 4 5 6 7
Deadline for bonus 1 1 3 3 2 2 6
Bonus marks 6 7 2 1 4 5 1
The maximum number of bonus marks one can obtain is 15, which can be achieved by completing the problems in the sequence 2,6,3,1,7,5,4. Note that there are also other sequences that achieve the same effect.
Your task is to find a schedule to complete all homework problems so as to maximize bonus marks. Input format
The first line contains an integer N, indicating the number of homework problems. This is followed by N lines (lines 2, ,N+1), each containing two integers. The first integer on line i+1 (1 ≤ i ≤ N) is the deadline for the ith homework problem and the second integer on line i+1 is the number of bonus marks assigned to the ith homework problem.
Output format
A single integer indicating the maximum number of bonus marks that can be obtained.Test Data:
You may assume that 1 ≤ N ≤ 200000.
Example:
Here is the sample input and output corresponding to the example discussed above.
Sample Input
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
Sample Output
15
--------------------------------------------------------------------------------