Thank you for participating in Kick Start 2019 Round E!
Cast
Cherries Mesh: Written by Bartosz Kostka and prepared by Seunghyun Jo and Lalit Kundu.
Code-Eat Switcher: Written by Archie Pusaka and prepared by Reyno Tilikaynen.
Street Checkers: Written by Bartosz Kostka and prepared by Jonathan Irvin Gunawan.
Solutions, other problem preparation, reviews and contest monitoring by Anushi Maheshwari, Himanshu Jaju, Zhang Chen, Sadia Atique, Yang Xiao, Teja Vardhan Reddy Dasannagari.
Analyses were authored by Kevin Tran, Alan Huang and Anushi Maheshwari.
Your friend is recently done with cooking class and now he wants to boast in front of his school friends by making a nice dessert. He has come up with an amazing dessert called Cherries Mesh. To make the dish, he has already collected cherries numbered 1 to N. He has also decided to connect each distinct and unordered pair of cherries with a sweet strand, made of sugar. Sweet strands are either red or black, depending on the sugar content in them. Each black strand contains one units of sugar, and each red strand contains two units of sugar.
But it turns out that the dessert is now too sweet, and these days his school friends are dieting and they usually like dishes with less sugar. He is really confused now and comes to your rescue. Can you help him find out which all sweet strands he should remove such that each pair of cherries is connected directly or indirectly via a sugar strand, and the dish has the minimum possible sugar content?
The first line of input gives the number of test cases, T.
Each test case begins with a line containing two integers N and M, the number of cherries and the number of black sweet strands, respectively.
Then M lines follow, each describing a pair of cherries connected to a black strand. The i-th line contains cherries numbered Ci and Di, it indicates that Ci and Di cherry are connected with a black strand of sugar.
Note: Any other pair of cherries not present in the input means that they are connected by a red strand.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is minimum possible sugar content.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100
M ≤ N*(N-1)/2
1 ≤ Ci ≤ N, for all i.
1 ≤ Di ≤ N, for all i.
Ci ≠ Di, for all i.
Every {Ci, Di} is distinct.
1 ≤ N ≤ 100.
0 ≤ M ≤ 100.
For at least 90% of the test cases:
1 ≤ N ≤ 1000.
0 ≤ M ≤ 1000.
For all test cases:
1 ≤ N ≤ 105.
0 ≤ M ≤ 105.
2 2 1 1 2 3 1 2 3
Case #1: 1 Case #2: 3
n the second sample case, we can keep the black strand between cherry numbered 2 and cherry numbered 3, and remove any of the red strands, which leads to a minimum sugar content of 3.
Umon is a foodie coder. Do you know what two activities that he loves the most? Of course, coding and eating! He always spends the whole day doing only those two activities. However, he thinks that some times of the day are better spent coding, and others are better spent eating.
To illustrate this problem, Umon divides his day into S time slots. During the i-th time slot, if Umon codes 100% of the time, he will achieve Ci units of coding. On the other hand, if he eats 100% of the time, he will achieve Ei units of eating. But of course, Umon can also use only a fraction of the time for coding, and the remaining for eating. Formally, he will choose a real number f (0 ≤ f ≤ 1), code for f of the time, and use the remaining (1 - f) time to eat. This way, he will achieve f × Ci units of coding and (1 - f) × Ei units of eating. The total amount of coding Umon achieves for the day is simply the sum of all units of coding he achieved in each of the time slots. The total amount of eating is calculated in a similar way.
Umon needs to plan his schedule for the next D days. On the i-th day, he needs to achieve at least a total amount of Ai units of coding and Bi units of eating. For each day, determine whether there is a way for Umon to achieve his target.
The first line of input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers D and S, the number of days and the number of time slots in a day, respectively.
Then S lines follow, each describing a time slot. The i-th line contains two integers Ci and Ei, the amount of coding units achieved if Umon codes for 100% of the time slot, and the amount of eating units achieved if he eats for 100% of the time slot, respectively.
Then D lines follow, each describing a day. The i-th line contains two integers Ai and Bi, the minimal total amount of coding and eating that needs to be achieved on that day.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string with D characters, where the i-th character is Y if there exists a schedule that can fulfill the target for the i-th day, otherwise it should be N.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ci ≤ 104, for all i.
1 ≤ Ei ≤ 104, for all i.
0 ≤ Ai ≤ 108, for all i.
0 ≤ Bi ≤ 108, for all i.
1 ≤ S ≤ 2.
1 ≤ D ≤ 10.
For at least TODO% of the test cases:
1 ≤ S ≤ 103.
1 ≤ D ≤ 103.
For all test cases:
1 ≤ S ≤ 105.
1 ≤ D ≤ 105.
2 4 2 3 8 6 10 0 18 3 13 10 0 7 3 1 2 4 4 4 4 0 0
Case #1: YYNY Case #2: Y
In the first sample case, there are 4 days and 2 time slots for each day.
In the second sample case, note that the value of characteristics for the time slots may not necessarily be different from each other.
Alice and Bob are playing a new virtual reality team game - Street Checkers. The game is set on an insanely long street divided into tiles which are numbered from 0 to 109(inclusive of both). At the start of the game, Alice and Bob are standing on tile number 0 and are given a random number X in range [L, R] (both ends are inclusive). Alice only jumps to odd numbered tiles, while Bob only jumps to even numbered tiles. If the number on the tile divides X, then the player landing on it has to color it with their favorite color. The game is over after tile X has been colored.
A game is considered interesting by both the players if the absolute difference between the number of tiles painted by each is not greater than 2. Help Alice and Bob find how many numbers in the interval [L, R] could make for an interesting game.
The first line of the input gives the number of test cases, T. T lines follow each containing two integers L and R, the start and end of the interval used to generate the random number X.
For each test case, output one line containing Case #x: y, where x is
the test case number (starting from 1) and y is the count of numbers in interval
[L, R] which results in an interesting game for Alice and Bob.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ R - L ≤ 105.
1 ≤ L ≤ R ≤ 106.
1 ≤ L ≤ R ≤ 109.
2 5 10 102 102
Case #1: 5 Case #2: 1
For the first sample case, let us look at all the possible number in range [5, 10]:
In the second sample case, we have only one number 102. Alice would paint 4 tiles : {1, 3, 17, 51} while Bob would paint 4 tiles : {2, 6, 34, 102}. The game would be interesting since the absolute difference is 0.
First, let's rephrase the problem: Given a complete undirected graph, where each edge has weight 1 or 2, what is the cost of the Minimum Spanning Tree? There are a few different algorithms for solving this problem, such as Prim's Algorithm and Kruskal's algorithm. Using Kruskal's Algorithm gives an O(N2 log N) solution per test case, while Prim's Algorithm gives an O(N2) solution per test case.
Intuitively, we want to include as many edges of weight 1 as possible. Once we have included as many such edges as we can, then we know that the remaining edges in the spanning tree will be of weight 2.
Using this idea, we have the following solution: first create a spanning forest using only edges of weight 1. We can now connect each of the components of the spanning forest together using X-1 edges of weight 2, where X is the number of components (we can always connect these components since the graph is complete).
Since we only need to print the minimum cost and not the actual minimum spanning tree, we can simplify the problem to simply counting the number of components in the graph where we only consider the edges of weight 1.
This solves the problem in O(N).
Let's start with the brute force way of solving the problem. We can iterate through all possible coding units for slot 1, let's say X. Now, we can calculate the coding unit left for slot 2 (Ai - X). Using this we can calculate eating unit we can achieve for both slot 1 and slot 2 and compare it with Bi. Time complexity for each test case would be O(Cmax*D).
Let's first solve for only 1 day. So assuming two time slots Si(Ei, Ci) and Sj(Ej, Sj) we can see that to achieve every 1 unit of eating in Si slot we are losing Ci/Ei unit of coding, similarly for Sj slot. Hence, we can observe that it's always a better choice to choose time slot Si if Ci/Ei ≤ Cj/Ej. Now, we have the order in which we should achieve the required eating unit.
For calculating minimum coding requirement we can maintain prefix cumulative and suffix cumulative sum of maximum coding and eating unit that can be achieved in a time slot. Then using binary search on prefix cumulative sum array, we can find out which minimum indexed time slot will give us eating more than required and we can remove the excess fraction of time for use in coding. We can compute the maximum coding unit achieved from unused time slots by using the suffix cumulative sum. This will take O(SlogS + S) preprocessing time and O(DlogS) for each test case.
Let's rephrase the problem into counting the number of values X within the range [L, R] that satisfies |(# of odd divisors) - (# of even divisors)| ≤ 2.
To solve this problem under the constraint that R < 106. We can simply preprocesses each X between 1 and 106 whether X is interesting or not. To find whether X is interesting, we can apply any O(√X) time algorithm finding out all divisors of X. After storing the result for each X, we build a prefix sum array F storing for counts. Thus, each query can be answered by computing F[R] - F[L-1] in constant time. The total time complexity would then be O(Rmax√Rmax + T), which suffices to pass the first test set.
We need a slightly sophisticated observation here. The intuition comes from observing that any divisor to an odd integer is still odd. For any integer X we can extract all power of 2 factors and rewrite as X=A*2X, where A is an odd integer and X is a non-negative integer.
Now, we can partition all divisors to X into sets of divisors leading with each odd divisors d1, d2, ..., dk of A:
{d1, d1*2, d1*22, ..., d1*2X},
{d2, d2*2, d2*22, ..., d2*2X},
...
{dk, dk*2, dk*22, ..., dk*2X}.
By looking at the above diagram we can infer that X has X odd divisors and X*X even divisors. The criteria to a number being interesting is now equivalent to |X*(X-1)| ≤ 2.
There are only a few cases of (X, X) pairs that satisfies the above expression:
So, what we really need to do here is to count the number of X's in the range [L, R] satisfying each case.
Case 1 implies that X=1 or a odd prime. One can count the number of primes within range [L, R] using Sieve of Eratosthenes. Case 2 implies that A can be any odd integer, so in this case X is in the form of (4*X+2) and hence can be counted in O(1) time. Case 3 implies that A=1 or an odd prime. One can count the number of primes within range [L/4, R/4]. Case 4 implies that X=8. Count it whenever 8 belongs to the range.
From the above case analysis, one can see that the running time is dominated by Sieve of Eratosthenes. Fortunately, we only need to use sieve method on arrays of size O(R-L+1) to count the number of odd primes within ranges [L, R] and [L/4, R/4]. If we apply sieving using numbers 2, 3, 4, ..., √R, the algorithm runs in O(T*(R - L + 1)*log(√R)) time, which suffices to pass this test set.
For a more efficient algorithm, one can sieve using prime numbers no more than √R. These prime numbers again can be obtained by a sieving algorithm. At the end you will get an algorithm that runs in O(√R log log √R) + O((R - L + 1) log log √R) time per test case.