Dev Skill: Game of MODs

Problem link: Game of MODs

In this problem, we are given an integer n with q queries. Each query we have k integer. We need to calculate the maximum and minimum number can be formed after removing k digits from n. Here the digits won't change their position.

Solution: Some things to observer first.

• If k == size of n (digits), then the answer would be 0 0
• If there are leading zeros, we need to remove them, say we got a number like 000000009. this should be changed to 9.
• If we have only 0 digit, then the answer would be zero

We will use recursion technique for building up our desired result. The idea is that a character among first (k+1) characters must be present in the resultant number. So we pick the first (k+1) smallest or largest depending on the situation. Put it on the result, then recur for remaining characters.
This is done in the legend function below. I used a counter variable for checking whether we are creating maximum or minimum number. Look at line 18 for understanding. Only the change in the index can produce two defferent result. Complexity is O(n), the number of digits. Considering all the cases, queries, complexity would be 100*200*11 = 220000

Toph: Range Product

Problem link: Range Product

Solution:

Given N and K, we have to find how many integers of K subarray has maximum product which starting index of the subarray is minimum. Also all the integers will be power of 2.
So, at first we will store the power of all the integers in an array. Then we will simply use brute force to check for maximum subarray summation (As we took only power, so we will check for summation here).

Why we took the power? Why we didn't simply multiply? As the multiplication's value will be far greater than long long in C++ data type, we simply can't do that. Also in the problem description there is no mention about modulo operator, so we definitely can't multiply. So we took out the power of 2's and add them to get our maximum muliplication subarray.

Toph: XOR Master

Problem link: XOR Master

Solution:

In this problem we are given N integers. We have to count the number of pairs (i,j) (1<=i<=j<=N) for which A[i] XOR A[j] will contain at least 1 in it's bit pattern.

Say for the case here:
4
1 2 2 2

Here are 3 such pair that A[i] XOR A[j] has at least one 1 in it's bit pattern. They are:

1 XOR 2 = 01(Binary of 1) XOR 10(Binary of 2) = 11 (has two '1's) ; for three 2's, and a single 1, we get 3 such pair of (1,2)

But as we can see, 2 XOR 2 = 10 XOR 10 = 00, here no '1' is present. So this will not be counted.

So, how can we solve this? Firstly, see that one integer can get at least one '1' in it's bit pattern if it is XOR-ed with any integers except itself. So, a simple binary search with upper_bound technique can be really helpful to find solution in O(log N). For frequent values, we can store them in a map data structure that is built in C++ function.

Toph: Horrible Queries

Problem link: Horrible Queries

Solution:

In this problem, we will be given some integers from 1 to 50. And also integer L,R,K. We need to find how many unique values have at least K occurence in the subarray between L & R, where L<= R.
As numbers can only be between 1 to 50, we can implement this simply without the use of segment tree. What we need to do is that, we will create 50 array of size N (each for 1 to 50 integers) to compute the occurence of every integers in a cumulative way. Then for each query, we will simply check for every integers if cumulative sum (occurence of that integer) of that integer in given range is at least K or not. Then we will simply increase the counter to get our answer. Try to implement it any way you like keeping in mind about the cumulative frequency of occurance. Then you can check my code below.

Toph: Arya and OR

Problem link: Arya and OR

Solution: 

Firstly, the maximum value we could get is the largest element of the array. So we will sort the array. Then our maximum value could get greater by doing OR ( | ) with other elements of the array. So in that case, what we will do is that, each time we will make bitwise OR with the largest element of the array with other elements in descending order. So, gradually, we will get values after everytime we OR them. If our current value is greater than our maximum value, then we will simply update the maximum value.

As there is a term "arbitrary group of numbers"
Arbitrary group should mean any group possible from the whole array, and in that case the bitwise or of the whole array is always the maximum answer

**ps: We don't even need sorting for this problem. Simply compute OR of all the numbers.

Code:

Codeforces: Squares and not squares

Problem Link: Squares and not squares

Editorial: At first we can pre compute square numbers from 0 to 31623, as 31623*31623 = 1000014129, which is greater than 10⁹.

Then we will take two seperate vectors, one for storing square numbers and other for non square numbers. We can store them at the time of taking input. Simply binary searching in the pre computed square numbers vector would be greate.
Now, we will count how many square numbers are there in the square vector. Say it is count1. And number of non squared number would be count2 = n - count1. Now-->

1. If count1 == n/2, then the answer is zero.
2. If count1 > n/2, then we need to make some of our squared numbers into non squared number.
3. If count1 < n/2, then we need to make some of the non squared number to squared number.

count1 > n/2:
We need to check what is the maximum number of the squared numbers. If max_value is <=0, then for each squared number to make a non squared number we need to add +2 if the number is zero (0) else +1.
For 0, we should add +2 to make it 2, as 2 is not a squared number, but 1 is a square number. And we need to make (  count1- n/2 ) non_squared numbers.

count1 < n/2:

Now we need to find the closest squared number for each element of our non squared vector. Simply iterate through all the values from non squared vector and we will find upper_bound of each element in our pre computed square vector. We will take another vector to store the minimum value we got from each element via upper_bound. Finally we will sort the vector, and print the sum of the first (  n/2 - count1 ) elements from that vector.
Here is the solution of mine : solution