prophet_ov_darkness's blog

[GYM] 2017 Bangladesh National High School Programming Contest ( National Round, Senior Group ), NHSPC 2017 Tutorial
By prophet_ov_darkness, 8 years ago, In English

Tutorials are written by corresponding problem authors. I'm just assembling all those tutorials in one place.

101353A - Charm Is Not Always Enough

Problem Author: raida_ash, Tester: khairat

It is a simple ad-hoc problem. We can solve it in . Simply iterate over all the bottles and add the amount of liquid spilled to the answer.

Problem Author's Solution

101353B - Max and Alexis Plan to Conquer the World

Problem Author: Tanzir5, Tester: s_h_shahin, shapnil092

The number of kittens is N initially and rate of increase in the number of kittens is R% per year. Let's divide R by 100 and then we can use the formula of compound interest here to get that after X years, the number of kittens will be:

N × (1 + R)X

Now we can do a binary search over X to find out which is the lowest value of X that satisfies the following equation:

N × (1 + R)X ≥ P ( Where P is the required number of kittens given as input )

So the time complexity is . Now if you take the highest end of your binary search range too large, then you will get TLE as you can see the range you take has direct effect on the complexity. You can do some calculation to find that answer can never be more than around 5000 for the given constraints.

Another way to solve the problem would be to use a direct formula. From the above formula, we can come to this:

N × (1 + R)X ≥ P

So now we can get the minimum value of X from this formula. But you have to be careful with the calculations and take care of the cases specially where P ≤ N i.e. the answer is 0.

Problem Author's Solution

101353C - Being Common is Too Mainstream

Problem Author: nafisiham, Tester: De_La_Grandi_Mephstophls

The problem setter’s and the alternate writer’s solution are nearly same, and it is not the best but an easy way to solve this problem.

The naïve solution is to keep calculating GCD of every set of numbers that can be taken and keep dividing the elements of the sets by those GCDs until, there remain some co-prime numbers. The answer is their product. Actually, we are trying to divide every number with whatever common divisor it shares with any other number.

So, for every prime divisor, its remaining exponent will be the absolute difference between its highest and second highest exponent in any number. For subtasks 2 and 3 a fairly small array of primes sufficed.

For subtask 1, naïve approach was taken using Euclidean algorithm.

Problem Author's Solution
Tester's Solution

101353D - ShaatChara

Problem Author: immuntasir, Tester: raida_ash

As noted, this is a normal nim game of n piles. In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the piles is nonzero. In this problem we want to know in how many ways the first player can move such that the second player gets a losing state. That means the first player wants to move such that the xor-sum becomes zero. Now note the properties of a xor operation.




Now, we can consider the piles in binary and get some rows and columns of 0s and 1s. The first player is only concerned with the number of bits which are 1 in the current xor-sum. Now note that, each 1 bits of the xor-sum are there because there were 1s in that position in odd number of piles. Now, we have to choose such piles where there is a 1 in the same position of the leftmost bit of xor-sum, and choose the bits in a way such that the number of 1s become zero for all column. So, the solution comes down to this: the number of winning moves are the number of 1’s in the leftmost column with an odd number of 1.

Problem Author's Solution

101353E - Just One Swap

Problem Author: bertho_coder, Tester: prophet_ov_darkness

The answer is equal to the number of ways you can choose two different numbers from the given array. It can be done easily with the help of the frequency array of the given numbers. But if there is at least one number having frequency greater than 1, then you can swap any two numbers having the same value and get the initial given array. So, in that case, you need to add 1 to the answer.

Problem Author's Solution
Tester's Solution

101353F - Halum and Candies

Problem Author: shadowfax, Tester: MesbahTanvir

The naïve solution would be to sort the candies in descending order. Now we give a guest K candies from first K flavors where a1 > 0, a2 > 0, ..., ak > 0. Then we sort them again and do the same step until one of the a1, a2, ..., ak becomes 0. This method works for the smaller subtask but for bigger constraints of ai it fails to solve within time limit.

To solve for the larger constraints, we can accelerate the above algorithm. We sort them in descending order and subtract ak from a1, a2, ..., ak. This way we surely have given candies to ak number of guests. Now from the remaining sum of ak + 1, ..., an flavors, we can assign them in empty spots from a1, a2, ..., ak. This means that we could easily chose to give from these flavors when any of the a1, a2, ..., ak flavors gets less. We use binary search on answer to find the maximum such assignments.

Tester MesbahTanvir also used binary search on answer, but with a quite different approach. Let’s say we can satisfy X guests. Then we find how many candies we have in total so that we can give X guests. Now we just have to check if SUM / X ≥ K, to satisfy our condition.

Problem Author's Solution
Tester's Solution

101353G - XOR 'em all

Problem Author: Riddho, Tester: s_h_shahin

The first observation to be made here is that if any integer having a parity of X is XOR'ed with 220 - 1 (a number whose binary representation is 11111111111111111111), its parity will become 20 - X.

To handle the updates and queries, a segment tree can be used, each of who's nodes shall contain a bitmask, of 20 bits each. The Pth bit of the bitmask in any node shall be 1 if any of the integers in the interval represented by the node has a parity of P, and 0 otherwise.

Thus, during a range update, the new mask of a node can be created simply by reversing the previous mask (since the ith bit of the new mask will equal the (20 - i)th bit of the old mask).

For answering the query, if the parity of the given number v is P, we first query to find if any number with parity P exists in the given range. If not we find the highest parity Q < P that exists in the range, and the smallest parity R>P that exist in the same.

Case 1: If (P - Q) < (R - P) print the position of the leftmost number in the range with parity Q.

Case 2: If (P - Q) > (R - P) print the position of the leftmost number in the range with parity R.

Case 3: If (P - Q) = (R - P) find x, the position of the leftmost number in the range with parity Q, and y, the position of the leftmost number in the range with parity R, and print the minimum of x and y.

To find the position of the leftmost number with a certain parity p, in a given range, we can query through the segment tree in . If we are certain that at least one number with parity p exists in the range represented by a node, then obviously, either the left child or the right child contains a number with the parity p. Since we are looking for the leftmost position, if a number with parity p appears in the left interval (which we can find out using a segment tree query on the range specified by the left interval), we go to the left child, otherwise to the right. Once we reach a leaf of a tree, the array element represented by it is the answer to the query.

Time Complexity:

Problem Author's Solution
Tester's Solution

101353H - Simple Path

Problem Author: prophet_ov_darkness, Tester: bertho_coder

Firstly let's check out an optimized brute force solution to this problem. Here we'll fix a subroot in linear time. Then from each of those subroots we'll run DFS in the corresponding subtree. For each edge in a subtree, we'll count the number of times it appears in all possible simple paths present in that subtree. Let's take an edge u - v, where u is the parent of v. Now the number of times this edge will appear in subtree rooted at node r will be S(v) × (S(r) - S(v)), where S(x) =  size of subtree rooted at x. This count will have to be multiplied by the weight of edge u - v and added to the actual result. This part is pretty straight-forward. Think about it for a moment if it's still unclear.

Now let's optimize this solution into a linear one. For that we'll have to use dynamic programming. Let's say DP(x) =  answer for subtree rooted at x. Suppose we are computing DP(x) now. Let y be a child of x and u - v an edge in the subtree of y, where u is the parent of v. Firstly we'll have to add DP(y) to DP(x). Secondly we'll have to add the impact edge x - y puts in DP(x). This part is discussed in the previous paragraph. Finally we'll have to count all those simple paths which start in the subtree of y and goes through node x and finishes in another part of the subtree of node x. Let, W(x) be the weight of the edge which leads node x to it's parent.

We know the impact node u - v puts while computing the answer of subtree rooted at y: S(v) × W(v) × (S(y) - S(u))

Impact of edge u - v in the answer of subtree rooted at node x: S(v) × W(v) × (S(x) - S(u))

The difference is: S(v) × W(v) × (S(x) - S(y))

So, we'll have to add with DP(x) to get the final answer.

Here, ST(x) =  set of proper descendants of node x

Overall time complexity:

Problem Author's Solution
Tester's Solution
  • Vote: I like it
  • +39
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In C for subtasks 2 and 3 another solution is make a list of all the prime divisor which occurs at least in two number then divide the elements of the array for every prime divisor until there two or more elements divided by that divisor.The answer is product of the array's elements.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Here is another solution for G problem and it works in N * log(N) * 20 + Q * log(N) * 20.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please explain why the result of this test case for problem D

1

4

5 1 4 5

is 3

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    101 001 100 101 You can to any of the following: 1. Remove all from the first pile. 2. Remove 3 from the 3rd pile. 3. Remove all from the 4th pile.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My linear straight-forward solution for D: ShaatChara

We know that if the first player can make xorsum of the array equal to zero then he wins. Let xorsum of the given array be x. Observe that the only way to make the xorsum zero by taking out some non-zero stones from pile i is to reduce the value of a[i] to a[i]^x. Hence we do cnt++ for all i's where a[i]^x is strictly lesser than a[i] since we need to take out at least one stone.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, Shouldn't the answer of [2,4,8] be 1 ?? My explanation — divide the whole array by 4 to get [2,1,2] and then divide the whole array by 2 to get [1,1,1]

→ Reply