Problem 1 Line of Battle (Programming)

Problem Description

WillyPillow is recently obsessed with a mobile game called Azure Line, which involves multiple ships lining up and forming fleets. In the game, each ship is characterized by two parameters: a leadership factor and a team awareness factor. In addition, we define a fleet as a non-empty set of contiguous ships in which the ship that comes first is the flagship. For a fleet to be efficient, the leadership factor of the flagship has to be no smaller than the sum of the team awareness factors of the other ships in the fleet.

Now, WillyPillow is given a line of N ships, and he wants to calculate how many combinations of fleets he can form such that all fleets are efficient and one ship is assigned to exactly one fleet. Two combinations are considered different if there exists a pair of ships that are in the same fleet in one combination but are in different fleets in the other.

Formally speaking, he has to count the number of ways to partition a list into segments, with every segment [l,r] satisfying, where a_i and b_i are the leadership and team awareness factors, respectively, of the i-th ship.

Input

Due to the sheer size of the input data, you are required to use the generator in the link below to generate data on the fly:

https://gitlab.com/snippets/1904475

Specifically, you need to paste the given generator at the beginning of your source file, and use it as follows:

int n = ada::Init(); // Get N for (int i = 0; i < n; i++) leadership[i] = ada::GetLeadership(); for (int i = 0; i < n; i++) team_value[i] = ada::GetTeamValue();

You may not interact with the standard input by any other means, e.g., scanf and cin.

Note that in all test groups, the leadership and team awareness factors are in the range [0,10⁹].

Test Group 0 (0 %) Sample InputTest Group 1 (5 %) 1 N 500

Test Group 2 (15 %) 1 N 5 103Test Group 3 (80 %) 1 N 2 106

Output

Please output an integer (to the standard output) indicating the number of ways to form combinations of fleets, modulo the prime 10⁹ + 7.

Sample Input 1

5 20 20 1537688804 584589912 3972715898 2166415565

Sample Output 1

2

Sample Input 2

10 20 20 4041108152 584535659 2466603739 198973427

Sample Output 2

46

Problem 2 Chunithm (Programming)

Problem Description

You are playing a game chunithm. As the most talented student at NTU CSIE, you want to make sure that you can win the game with the least effort.

In the beginning of the game, you are given a song. The song is N seconds long and there is exactly one note at one second. You have a keyboard with M different notes, and all notes in the song can be played with this keyboard. You play the song with two hands on the keyboard. If the song contains the note j at i-th second, one of your hands must put on the note j of the keyboard at that second. The distance between notes j₁ and j₂ on the keyboard is |j_i j₂|.

The effort of playing the game is defined as follows:

During the interval between i-th and (i+1)-th seconds, you can move each of your hands for distance K without any effort. (Both of your hands can move at the same time.) If you move a hand for more than distance K in one second, the effort of moving the hand is (the number of steps you movedK). Initially, you can put your hands at any position without any effort. The effort will accumulate over time and the effort experienced by both hands will add up.

Given the song, the size of the keyboard M, and the distance number you can easily move K, please output the minimum effort you need for finishing playing the song (the hands can start from anywhere on the keyboard).

Input

The first line of the input consists of 3 integers N, M, and K. The second line consists of N numbers a₀, a₁, , a_n1. a_i indicates the note of the song at ith second.

• 1 N 100000
• 1 M 300
• 1 K M
• 0 a_i < M

Output

An integer indicates the amount of effort.

Subtask 1 (30 %)

• N 100,M 100

Subtask 2 (30 %)

• N 3000

Subtask 3 (40 %)

• No other constraints.

Sample Input 1

7 7 1

0 1 2 6 5 4 0

Sample Output 1

0

Sample Input 2

8 7 1

0 6 4 3 2 1 5 0

Sample Output 2

1

Problem 3 Pokemon GO (Programming)

Problem Description

WillyPillow is a Pokemon trainer, and he has N Pokemon. Each Pokemon has a unique ID from 1 to N, where the Pokemon with the ID i has three attributes: a attack power A_i, a potential value B_i, and an experience point E_i which is initially set to zero.

The battle between WillyPillow and his rival has K rounds, and both of them have to pick K Pokemon and arrange their attacking order. Let p_i be the ID of the Pokemon WillyPillow summons in the i-th round. The Pokemon will first cause (A_pi E_pi) damage to the opponent, then it will use its magic power to increase B_pi experience points of all other WillyPillows Pokemon which have not yet be summoned.

Because WillyPillow is busy preparing for the ADA exam, you, who live on Pokemon betting and have spent all money on this battle, decide to help him choose K Pokemon and arrange their attacking order such that the maximum total damage can be achieved.

Input

The first line of the input contains two integers N and K, indicating the number of Pokemon WillyPillow has and the number of rounds in the battle, respectively.

N lines follow, the i-th of which contains two integers A_i,B_i, denoting the attack power and the

potential value of the Pokemon with ID i.

• 1 K N 100
• 0 A_i,B_i 100

Test Group 0 (10 %) Test Group 2 (80 %) K = N No other constraints.

Test Group 1 (10 %)

• N 10

Output

Print an integer indicating the maximum possible total damage that can be achieved if K Pokemon are chosen and arranged optimally.

Sample Input 1

9 4

6 8

0 13

14 14

14 1

14 4

13 5

3 11

5 6

3 12

Sample Output 1

994

Sample Input 2

6 6

10 7

0 8

5 3

10 7

2 9

1 3

Sample Output 2

673

Problem 4 Weigh Anchor (Programming) (15 points)

Problem Description

After WillyPillow assembled his fleet in Azure Line, he can now fight the war!

Aiming to win the war, WillyPillow picks three most well-trained ships, which have strengths s₁, s₂, and s₃, respectively.

The war consists of a set of battles. For each battle, he can select any subset of his ships to fight. He wins the battle if and only if the sum of the strengths of his chosen ships is no smaller than the strength of the enemy in this battle. Each ship can only be assigned to fight one battle per hour.

For example, he can fight two battles using ships s₁ + s₂ and s₃ in an hour, but he can not fight three battles using ships s₁ + s₂, s₂, and s₃ in an hour, since s₂ is used twice.

Since WillyPillow also needs to train Pokemon and prepare for the ADA exam (c.f. problem 3), he wants to spend as little time as possible on playing the game. Given the enemy strength of each battle, he wants to find out how much time he needs in order to win all the battles according to the rules above. Note that he can fight the battles in any order.

Input

The first line of the input file contains an integer indicating N, the number of battles.

The second line contains three integers separated by spaces, indicating s₁,s₂, and s₃, the strengths of WillyPillows ships.

The third line contains N integers separated by spaces, with the i-th integer indicating the enemy strength of the i-th battle, denoted by a_i.

• 1 N 2 10⁵
• 1 s₁,s₂,s₃,a_i 10⁸

Test Group 0 (5 %) N 4

Test Group 2 (85 %) No other constraints.

Test Group 1 (10 %)

• N 10

Output

Please output an integer indicating the minimum number of hours WillyPillow needs to win all the battles. If its impossible to defeat all enemies, output 1 instead.

Sample Input 1

8

6 11 7

10 20 13 12 20 3 5 10

Sample Output 1

5

Sample Input 2

8

7 16 9

4 17 8 4 15 6 13 1

Sample Output 2

3

Problem 5 Piepies Pie Shop (Hand-Written) (16 points)

Piepie is a genius developer in Coming Spiorad International Enterprise and also a world famous chocolate-pie maker. People are willing to line up for 49 hours in order to purchase the chocolate pie he made, even he can make 1025 chocolate pies per hour. Nevertheless, Piepie felt bored by making delicious chocolate pies after earning his first trillion dollars. Thus, he decided to open a brand new pie shop.

The new pie shop has only one table that can accommodate a group of N customers at the same time. A group of N customers will come to the shop together and leave together. Each customer i will have his/her customized pie that takes Piepie p_i minutes, and the customer will finish eating the pie exactly e_i minutes after the pie is served. Piepie only makes one pie simultaneously, and there is no time gap between two pies.

After opening the shop, he notices that the order of making pies affects the groups leaving time. In order to make the group leave as fast as possible and make big money, he is seeking the best strategy of arranging the order and the corresponding minimum time needed for finishing serving the group of customers with the given information. Although he is a genius, he is sometimes too lazy to think. Can you please finish the task for him?

For this problem, each customer can be represented by a number from 1 to N.

Note that if you use Greedy or Dynamic Programming in any subproblem of this problem, you should prove their properties.

• (2pts) Given the preparation time and eating time of a group of N = 5 customers, [(2, 13), (4, 2), (3, 4), (7, 3), (5, 5)]

Please show your arrangement and the minimum time needed.

• (4pts) Please design an algorithm to provide your arrangement and calculate the total time needed. Your algorithm should run in O(N lgN) time. Also, you need to explain why your algorithm meets the time complexity requirement.
• (4pts) Please prove the correctness of your algorithm in (2).
• (3pts) To reach the true power of making pie, he decided to learn more in the Ninja School. After he returned, Piepie is able to perform SHADOW CLONE JUTSU. To enhance the productivity of his pie shop, he clones himself into piepie00 and piepie01. piepie00 and piepie01 always work separately at the same time; that is, they cannot work on the same pie simultaneously. Furthermore, one can make his next pie only when he finishes making his previous pie. They believe that they can perform the best when following the same strategy used in subproblem

(2).

Prove their daring thought or disprove with a counterexample.

• (3pts) In addition to SHADOW CLONE JUTSU, Piepie also learned CHIDORI to kill at most one of the customers. He is wondering who he kills will minimize the time needed. Please give an algorithm that runs in O(N lgN) time complexity and briefly explain the correctness and the time complexity of your algorithm.

Note: This subproblem is not related to subproblem 4, there is only one Piepie making Pie 🙂

Problem 6 Mobile Diners (Hand-Written) (14 points)

In an another world of strange dimension, there is a Natural University (will be called NU in the rest of this problem). The world is so strange that all the classrooms in NU are located on the only avenue, Pineapple Avenue. NU is made up of N classes, to simplify the problem, we assume that each class i locates on x_i, indicating its x_i units far from the entry of NU.

When it comes to lunch time, the students have no choice but to choose from the mobile diners. Each mobile diner has a delicious rate d, indicating that the students will only move at most d units from their classrooms to have their lunch on that mobile diner.

Its currently the recruiting stage and there are M mobile diner candidates and the delicious rates are d₁,d₂,,d_M, respectively. Due to the property of the strange world, the mobile diner with a smaller index should always be located on the side of a smaller coordinate. In order to reduce the personnel costs, you are asked to make a plan that makes all the students be able to have meal with fewest mobile diners.

In this problem, please assume that x is monotonic increasing, that is, for any i < j, x_i < x_j.

Note that if you use Greedy or Dynamic Programming in any subproblem of this problem, you should also prove their properties.

• (2pts) Please show your plan when there are 5 classes and they locate on x = {1,7,11,12,17} and there are 4 mobile diner candidates and the delicious rates are d = {3,2,5,4}.
• (2pts) In this subproblem, please assume that all the mobile diners are identical and share the same delicious rate d.

Please provide an algorithm to find the minimum number of mobile diners needed. Your algorithm should run in O(N + M) time complexity. Briefly explain the correctness and why your algorithm meets the time complexity requirement.

Note: You can get full credit of this problem if you answer subproblem (3) correctly.

• (4pts) The president of NU collects dirty money from the mobile diners, and has been using an unfair priority. The priority is exactly the index of the mobile diners!

Please consider the following scenario in this subproblem: For any two mobile diners with indices i < j, j is picked only if i is picked.. That is, if K mobile diners are selected, they must be the first K ones.

Please provide an algorithm to find the minimum number of mobile diners needed. Your algorithm should run in O(N + M) time complexity. Briefly explain the correctness and why your algorithm meets the time complexity requirement.

• (6pts) The corruption was revealed and the president is forced to quit. The new president is now open and enlightened. In subproblem (4), there is no priority among the mobile diners anymore. However, the rule that mobile diners with smaller indices should locate on smaller coordinates still remains.

Please provide an algorithm to compute the minimum number of mobile diners. Your algorithm should run in O(NM) time complexity. Briefly explain the correctness and why your algorithm meets the time complexity requirement.

Problem 7 Rainbow Rarity Rally (Hand-Written)

Rainbow Rarity Rally is an annual flying race held in Cloudsdale, Equestria. There are N 7 magical rainbow candies floating in the sky on the same 2-dimensional plane, indexed from 1 to N. Each candy has a color from one of the seven colors of rainbow, ROYGBIV(red, orange, yellow, green, blue, indigo and violet, indexed from 1 to 7). For each color, there is at least one candy with that color. There is also a start point on the ground. A contestant needs to fly upwards from the start point on the ground to the sky, and then fly downwards back to the start point, collecting all candies in the process.

1

2

3

4

5

6

7

Let C be an integer greater than or equal to N. We use N + 1 points p₀,p₁, ,p_N described in Cartesian coordinate system to represent a race. p_i = (x_i,y_i), where y_i represents the vertical height of the point.(x_i,y_i Z,0 x_i,y_i C). The start point is p₀, where y₀ = 0. The i-th candy is on the point p_i, and has color c_i(c_i Z,1 c_i 7). In order to uphold the holy tradition of the great pegasi race, y_i < y_i+1 for all i {0,1, ,N 1}.

Since Equestria is a magical kingdom ruled by chromatic sapient ponies who speak English, law of physics from our world dont apply there. Therefore, it takes a pegasus f(i,j) = (x_i x_j)²+(y_i y_j)² units of time to fly from p_i to p_j.

Each contestant has to design his/her own route that satisfy the following conditions. A route consists of two parts.

• Part 1. Contestants start from p₀ and fly upwards in the sky, stopping at p_N.
• Part 2. Continued from part 1, contestants start from p_N and fly downwards, stopping at p₀.
• In order to collect all candies, for all i {1,2, ,N},p_i is visited exactly once in the route.
• Contestants can fly through a candy without collecting it. For example, let a = (0,0),b = (1,1),c = (2,2),d = (3,3). Both (a c d b a) and (a b c d a) are allowed.

Rainbow Dash is an ambitious pegasus athlete who aims for the trophy. She want to know the smallest amount of time required to finish the race. She has a special aerobatics called Sonic Rainboom that can only be performed if for each color she collects at least one candy with that color in part 1 of her route. We call a route a Sonic-Rainboomable route if it allows Rainbow Dash to perform Sonic Rainboom. Rainbow Dash is not an egghead! She doesnt have time to do the math! Please help her!

Formally speaking:

• A route is an integer sequence a of length N + 2.
• a₀ = a_N+1 = 0 and each i {1,2, ,N} appears in a exactly once.
• Let q be an index of N in a.
• i [0,q 1],y_ai < y_ai+1.
• i [q,N],y_ai > y_ai+1.
• a₀,a₁, ,a_q is called part 1 of the route.
• a_q,a_q+1, ,a_N+1 is called part 2 of the route.
• The time required to fly through a route is
• A route is Sonic-Rainboomable if |{c_ai | i [1,q]}| = 7

(Task 1) (8 points) Whats the smallest amount of time required to finish the race? Please design a dynamic programming algorithm that calculates it with O(N²) time complexity.

(Task 2) (6 points) Please design a dynamic programming algorithm that solves (Task 1) with O(N²) time complexity and O(N) space complexity.

(Task 3) (4 points) Whats the smallest amount of time required to finish the race if Rainbow Dash wants to perform Sonic Rainboom? Please design a dynamic programming algorithm that calculates it with O(N²) time complexity.

(Task 4) (2 points) Please design a dynamic programming algorithm that solves (Task 3) with O(N²) time complexity and O(N) space complexity.

(Bonus) (6 points) Let t_OPT be the smallest amount of time required to finish the race if Rainbow Dash wants to perform Sonic Rainboom. Let a_OPT be a route (an integer sequence) that the time required to fly through it is t_OPT. If your algorithm in (Task 4) can find a_OPT with the same time and space complexity, you get extra 6 points!

Example

An instance of the problem with N = 10,C = 50.

i	0	1	2	3	4	5	6	7	8	9	10
xi	25	32	40	45	1	50	49	5	10	32	25
yi	0	1	5	10	18	25	32	40	45	49	50
ci	None	1	2	3	4	5	6	7	1	2	3

(a) {0,5,7,8,6,3,2,9,1,4,10,0} is not (b) {0,1,2,3,5,6,9,10,8,7,4,0} is a (c) {0,1,2,3,4,5,6,7,8,9,10,0} is a a route. Pink arrow means flying up- route, but not a Sonic-Rainboomable Sonic-Rainboomable route. wards and blue arrow means flying route.

downwards.

Note

1. You have to prove the correctness and complexity of your algorithm!
2. If you solved task 2, you get score from task 1 automatically. If you solved task 3, you get score from task 1 automatically. If you solved task 4, you get score from task 1,2,3 automatically. Start saving ink today! Save our Earth!
3. O(1) = O(2) = O(7) = O(127). We all love 127 🙂

Time and Space Complexity and Computational Model

1. We use Word RAM (Wikipedia contributors, 2019b) as the computational model in this problem. It is a kind of Random-access machine(Wikipedia contributors, 2019a). If you dont want to read long articles or the following descriptions, just think of it as a single thread C program running on your personal computer.
2. Let K = 2C²(N +1). Let T be the set of integers in range [K,K]. Let w = 1+dlog₂(K +1)e.
3. A w-bits signed integer using the twos complement representation is the basic data structure in this problem. Lets call it word . Obviously, we can store any x T in a word .
4. In this problem, we assumed that a word takes O(1) space.
5. Assignment of a word takes O(1) time.
6. Arithmetic operations (addition, subtraction, multiplication, bitwise NOT, bitwise AND, bitwise OR, bitwise XOR, bitwise left shift, bitwise right shift) of two word take O(1) time.
7. Comparison operations (equal to, not equal to, greater than, less than, greater than or equal to, less than or equal to) of two word take O(1) time.

References

Wikipedia contributors. (2019a). Random-access machine Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Random-access machine&oldid= 915665148. ([Online; accessed 15-October-2019])

Wikipedia contributors. (2019b). Word ram Wikipedia, the free encyclopedia. https:// en.wikipedia.org/w/index.php?title=Word RAM&oldid=883343686. ([Online; accessed 15October-2019])