Toph Hints

• Toph: XORs
• Toph: Arya and OR
• Toph: Horrible Queries
• Toph: XOR Master
• Toph: Range Product

Toph: XORs

Problem link: XORs

Solution:

We will be given some integers. We are asked to output the cumulative xor sum of all possible pair from those integers; where pair (a[i] ^ a[j]) and 1 <= i, j <= n [i, j = index]

Given the array 1 2 2 4 5, we have to perform our operation like below->

For 1, take all possible pairs:

• (1, 2) = 1 ^ 2 = 3
• (1, 2) = 1 ^ 2 = 3
• (1, 4) = 1 ^ 4 = 5
• (1, 5) = 1 ^ 5 = 4

For 2, take all possible pairs:

• (2, 2) = 2 ^ 2 = 0
• (2, 4) = 2 ^ 4 = 6
• (2, 5) = 2 ^ 5 = 7

For 2, take all possible pairs:

• (2, 4) = 2 ^ 4 = 6
• (2, 5) = 2 ^ 5 = 7

For 4, take all possible pairs

• (4, 5) = 4 ^ 5 = 1

So, we get values: 3, 3, 5, 4, 0, 6, 7, 6, 7, 1 and out output would be
3 ^ 3 ^ 5 ^ 4 ^ 0 ^ 6 ^ 7 ^ 6 ^ 7 ^ 1 = 0

So, how can we solve this? If we try to use bruteforce approach, complexity would be so much and we will surely get TLE in the process.

Let's consider the previous array 1 2 2 4 5, here for 1 we have exactly 4 pairs, for 2(first) we have 3 pairs, for 2(second) we have 2 pairs... for 5 we have no pair. Can you see the pattern here? Well let's talk about it, why the number of pair is important for us.

We know, if we xor an integer odd number of times, it becomes 0 (zero) and for even number of times, it becomes the integer itself. For the 4 pairs of 1, we get the following result by xoring all of the pair for 1 like this: (1^2)^(1^2)^(1^4)^(1^5). We can see, as we have xored odd number of one (1), [1 ^ 1 ^ 1 ^ 1]. We can conclude that it will finally be zero (0). So we don't need this in our calculation. What we need is that the xor of (2^2^4^5). Similarly for 2(first) we get 3 pairs, as we are xoring two 2's, and two is even, so we have to xor 2 with the result. So it will look something like this: 2^(2^4^5).
For second 2, we get (4^5).
For 4, we have one pair (zero xor, as zero is even, we need to xor with 4), Finally we get: (4^5).
For 5, we have no pair, so we don't need to do anything.

I hope now you understand why we need the number of pair. We can get the number of pair simply by (n - index_of_the_element). And for each element, we need the cumulative xor of all the element from index+1 to n of that particular index. We can pre calculate the cumulative xor of all the elements in an array. Remember, we need to pre calculate in reverse order for our purpose.

Dev Skill: Another Bigmod Problem

Problem link: Another Bigmod Problem

In this problem, we are given three integers A, B, C; we need to calculate A^B % C.

Solution: We can calculate it by using modular arithmetic. We know

• (a * b) % c = ( (a % c) * (b % c) ) %c 
• (a + b) % c = ( (a % c) + (b % c) ) %c 
• a^b = a * a^(b-1)

So with this we can write this following code to calculate A^B % C

This algorithm is called classical bigmod algorithm. But in this problem, we still have problem. Look at line 9 : x = ( x * x ) % c;

Here, since c can be as large as 10^18, the value of x can be (10^18 - 1 ). When we multiply x with x, it will overflow. For example, try with input a = 10^18 - 1, b = 2, c = 10^18.

So how do we calculate ( x * x ) % c, without overflowing? We use the same divide and conquer approach like above. But this time we will use addition instead of multiplication. It's called bigmultiplication, we will write the function as following:

So finally our full code would look like this:

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

CodeChef: February Long Challange 2018

Chef And His Characters: Given a string, we need to find four contiguous characters that can make a string "chef". We need to print how many four contiguous characters ('c','e','f','h') we found. If we found any simply write "lovely (the number of contiguous four characters we found)" else print "normal" without the quotes.

Solution:  The easiest problem of the set. Simply bruteforce through the string from 0 to length-4 and each time see if four contiguous characters are found or not. If found, increase the counter. Finally output the result.

Chef and The Patents: Given N patents we need to complete all of them in M months with K workers. Also each worker can work only one patent at most, that is, if we use a worker for a patent, we can't use him anymore. Every single patent needs exactly one month to finish. And we are also given X, that is at most X workers can work in a month. We are finally given a string of length K denoting the workers. On odd month, workers with character 'O' can work and on even month, worker with character 'E' can work.

Solution: It's a greedy problem. Some key things to notice:

• Worker can work only one month (after working one month, current worker would no longer be available).
• Restriction in odd and even month.
• At most X workers can work on a single month.

We just need to calculate for each month, how many workers can be used to finish how many patents. As a single worker can finish single patent at a time and there is a restriction of even and odd month, we will simply iterate through all the months from 1 to M. Then for each month, we will select minimum(number of workers, X). This is the value of the number of patents we can get in a month. In odd month, the number of worker should be the number of 'O' in the string. Similarly for even month the number of workers would be the number of 'E' in the string. Every time we get minimum workers, we will discard that number from that particular type of worker as a worker can at most work 1 month, so he won't be available after he has done his part. We will store the value every time we count how many workers can work in every month, then simply check if the value is >= N or not. If >= N, then 'yes', else 'no'

Permutation and Palindrome: Given a string, we need to make that string a palindrome re-arranging it's characters and output the indices of those characters that made the palindrome string.

Solution: It's a greedy implementation problem. Some key things to notice:

• If the string length is even and at least one character has odd frequency, we can't make it a palindrome. ex: "aacb"; Here, 'c' and 'b' has frequency = 1, which is odd, and the string length is 4, which is even, so no palindrome can be made.
• If the string length is odd and at least two character has odd frequency, we can't make it a palindrome. ex: "acccb"; Here, 'a', 'b' and 'c' has frequency 1, 1 and 3 respectively, which is odd and the string length is odd. So we can't make a palindrome.

Now how to make the palindrome. We can simply check all the frequency of the characters. If frequency is even, then we will take first half of the position (index) in our first vector, say X.
And second half will go to vector Y. For even length, we won't have any odd frequency, so we will simply reverse Y and then merge it with X to get final output. For odd we need to get the odd element's index first. let's see for even length:

string = "abababab"
We will push the indices accordingly in a vector containing frequency of each character. So,

vector['a'] = 1 3 5 7
vector['b'] = 2 4 6 8

Now, we will iterate through the character's frequency. For 'a'
The first half will go to vector X, and second half will go to vector Y. So.
X = 1 3
Y = 5 7
Now, for 'b', similarly
X = 1 3 2 4
Y = 5 7 6 8

Now, reverse the Y and merge it with X to get the final result.
Final = 1 3 2 4 8 6 7 5

If we observe the indices, we can make this: "aabbbbaa"; which is a palindrome.}

Similarly, we can make this for odd length. There will be one character with odd frequency. we will take first index of that character from our vector[] array, then everything else follows exactly same.
Before merging Y with X, we need to push that odd frequency index to X first.

Car-pal Tunnel: In this problem we are given N tunnels and each consecutive tunnel has D meter distance. There are C cars each having same velocity S meter per second.

Each tunnel has a toll booth that takes Ai second to process a single car. At the time of processing one car, no car can come to that booth for processing. All the tunnels are linearly connected via these toll booths. We need to calculate the delay time between the first and last car after all of them is processed by all the toll booths.

Solution:

After a bit of observation, we will see that, the maximum time of a toll booth will be the distance between any two cars. So if there are C cars, then the answer will simply be (C-1)*maximum (Ai). Let’s see this case:

3
5 15 8
2 3 1

Here, 3 toll booth which have 5,15,8 second to process each car respectively. We have 2 cars each having velocity 1 meter per second. Each tunnel has 3 meter distance. So for a single car to cross a tunnel, it needs 3/1 = 3 second. Now let’s see, when the first car is being processed at the first booth, after 5 second, it will go out from the booth and second car will start processing. 

• 1 second goes, first car moves 1 meter, second car’s process time is also 1 sec.
• 2 second goes, first car goes 1 meter, second car’s process is 2 second.
• 3 second goes, first car is now at second booth for processing, second car’s 3 sec processing time is finished at first booth.

 So the distance between two cars will be 3 second.

Now, after 4,5,6 second, the second car will arrive at the second booth, but the first car is still being processed at that booth. So the second car will stop there. So our delay is now updated to 15 second,
as we clearly know, after processing of the first car (which will take 15 second for 2^nd booth) only then the second car can start processing. So the distance between them will be then 15 second. So the answer is 15*(2-1) = 15; [15 is the maximum toll booth time for a particular booth].

This observation is correct when C is equals to two. If there are more cars, then we need to keep the distance is calculation too. The delay is D/S for every car that takes D/S second to pass D meter distance. But if we happen to come to any case where D/S is greater than maximum of toll booth time, then we need to take the maximum (D/S, toll booth time). Notice this is applicable when there are cars more than two. If only two car is present, then maximum of toll booth is the correct solution.

LightOJ: Points in Rectangle

Problem link: loj 1266

Technique: Binary Indexed Tree

If you don't know about Binary Indexed Tree, first learn it. You can also check BIT here BIT

Given two types of query,

• 0 x y: we got a new point at co-ordinate (x,y) [ if already a point exist in the same co-ordinate, this query does nothing ] 
• 1 x1 y1 x2 y2: we are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).

We will maintain a 2-D BIT(Binary Indexed Tree) to solve this problem. For query 0 x y, we will call update function each time we got a new point (x,y). For the second query, we will call out query_sum function with parameter (x,y); it means we will get the sum of the rectangle that's lower left co-ordinate is (1,1) and upper right co-ordinate is (x,y). Let's see a testcase:

1
4
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5

We got two points (1,1) and (2,6), let's plot these points:

Now let's see the first query, we have to find how many points are inside (1,1) and (6,6). We will call out query_sum function with parameter (6,6), And this will cover the whole area from (1,1) to (6,6) and we will get output = 2
Ok, for the second query we need to find points inside (2,2) and (5,5). We will call our query_sum function with (5,5) and the selected area would be like this:

But we have some extra area here as our query starts from (2,2). So we need to remove those extra area. Basically we need to calculate our desired area as follow:

area = query_sum(x2,y2)-query_sum(x1-1,y2-1)-query_sum(x2-1,y1-1)+query_sum(x1-1,y1-1)

Let's see how does it look, Here:

A = query_sum(x2,y2)

B = query_sum(x1-1,y2-1)

C = query_sum(x2-1,y1-1)

D = query_sum(x1-1,y1-1)

     

 

We added D because, while subtracting B and C, D got subtracted twice. So we need to balance it by adding. Hope you understand what we need to do here.

Code:

Akash and GCD 1

Problem link: Akash_gcd_1

We need to perform query based on given function F, that

F(x) = GCD(1, x) + GCD(2, x) + ..... + GCD(x, x)
Where GCD is the Greatest Common Divisor
Now in the problem, given an array A of size N, there are 2 types of queries:

1. C X Y: Compute the value of F(A[X]) + F(A[X+1]) + F(A[X+2]) + .... + F(A[Y]) (mod 10^9+7)
2. U X Y: Update the element of A[X] = Y

Solution:

At first we need to pre compute the value of F(x). Also we need help of Euler's Totient Function for this purpose. You can learn Euler Totient from here: Euler's Totient
Also we need to compute summation of GCD(i,n) for i = 1 to n. If you don't know how to do that, see here: GCD summation

This problem can be solved by segment tree. But as we only need prefix sum and simple update query, we can also solve it using binary indexed tree. As binary indexed tree is easy to code and simple, it's preferable.

Code:

Notice at line 86, the computed value might go negative less than 10^9+7. So we used a while loop to check while the value is below zero, we will add the mod value to make it positive. If we checked the negative value mod in the qeury function, this wouldn't be necessary.

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:

Lexicographic rank of a string(without duplicate character)

লেক্সিকোগ্রাফিক বলতে বুঝায় অ্যালফাবেটিকাল অর্ডার। যেমনঃ কোন স্ট্রিং "xyz" হলে, আমরা বলতে পারি এই স্ট্রিং এর লেক্সিকোগ্রাফিক অর্ডারের প্রথমে আছে "xyz", এরপরে "xzy" .. অর্থাৎ স্ট্রিং এর সকল পারমুটেশন এর সিরিয়াল, যারা কিনা ছোট থেকে বড় আকারে সর্টেড অবস্থায় আছে। এখন এরকম একটি স্ট্রিং দেখে আমাদের বলতে হবে এর র‍্যাঙ্ক কত। যেমনঃ "abc" এর ক্ষেত্রে, rank of "abc" = 1, rank of "acb" = 2 .... এভাবে।
একদম ব্যাসিকভাবে চিন্তা করলে আমরা সকল পারমুটেশন জেনারেট করে দেখতে পারি যে স্ট্রিং টি কততম পারমুটেশন এর সাথে মিলে গেছে। তাহলে সেটিই আমাদের স্ট্রিং এর র‍্যাঙ্ক।



এভাবে আমাদের টাইম কমপ্লেক্সিটি অনেক বেড়ে যাবে, প্রায় এক্সপোনেন্ট হারে!! (exponent) এজন্য আমাদের আরো ভালো এপ্রোচ দরকার।
আমরা একটি স্ট্রিং ধরি, "FRIEND" এর র‍্যাঙ্ক বের করতে হবে। এখানে প্রথম ক্যারেক্টার  "F" এবং "F" এর চেয়ে ছোট ২ টি ক্যারেক্টার আছে ("D", "E") এবং "F" কে তার জায়গায় ফিক্সড করলে আমাদের বাকি থাকে আরো ৫ টি জায়গা এবং "F" এর আগের ২ টি ক্যারেক্টার ঐ ৫ টি জায়গায় বসতে পারবে ৫ ফ্যাক্টরিয়াল (5!) উপায়ে। তাহলে ২ টির জন্য কম্বিনেশন হবে ২*৫!
এখন আমরা তাহলে "F" এর কাজ শেষ হলে, "F" কে ফিক্সড করে দেই। মানে "F" নিয়ে আমাদের আর মাথা ব্যথা করতে হবে না। এখন দ্বিতীয় ক্যারেক্টার "R" নিয়ে দেখি। "R" এর চেয়ে ছোট ৪ টি ক্যারেক্টার আছে ("D", "E", "I", "N"). ["F" কে আমরা ফিক্সড করে দিয়েছি, কাজেই "F" বাদ] 
তাহলে আমরা "R" এর জন্য পাবোঃ ২*৫! + ৪*৪! (আগের "F" এরগুলোও ধরতে হবে)।
একই ভাবে আমরা বাকি ক্যারেক্টার গুলোর জন্য করে ফেলিঃ

"I" = 2*5! + 4*4! + 2*3!
"E" = 2*5! + 4*4! + 2*3! + 1*2!
"N" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1!
"D" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0!
তাহলে, "FRIEND" এর জন্য র‍্যাঙ্ক হবে ঃ 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0! = 351
যেহেতু, র‍্যাঙ্ক ১ থেকে শুরু হয়, কাজেই আমাদের ফাইনাল রেজাল্ট হবে 1 + 351 = 352.



এর কপ্লেক্সিটি O(n²)। আমরা একটু বুদ্ধি খাটালে এর কমপ্লেক্সিটিকে কমিয়ে আনতে পারবো। এজন্য আমরা কিউমুলেটিভ ভাবে প্রতিটি ক্যারেক্টারের চেয়ে ছোট ক্যারেক্টারকে একটি অ্যারেতে সেভ করে রাখবো।এরপরে প্রতিবার সেখান থেকে কাউন্ট নিয়ে আমরা কাজ করবো O(n) কপ্লেক্সিটিতে

Light OJ Hints

• Algebraic Problem
• Points In Rectangle

1000 (Greetings from LightOJ) - Simple adhoc problem.
1001 (Opposite Task) - Exact opposite of problem 1000, carefully notice testcases and read the statement clearly.
1002 (Country Roads) - Modified Dijkstra algorithm is the key. We just need to modify a single line in our regular Dijkstra algorithm as when we use,
if(a[i][j] + dist[i] < dist[j])dist[j] = a[i][j] + dist[i];
while here we should use
if (max(a[i][j], dist[i]) < dist[j]) dist[j] = max(a[i][j], dist[i]);
1003 (Drunk) - We have to find if there a cycle exist in the graph, if there is a cycle he can't drink all.
1004 (Monkey Banana Problem) - Basic DP problem.
1005 (Rooks) - Basic recursion problem
1006 (Hex-a-bonacci) -  Replace the recursion with a for loop. Also make sure to take the modulo before storing the values in array as the values can be quite large.
1007 (Mathematically hard) - The input require very first IO method. scanf and printf would be the best choice. We need to use a modified version of the Sieve method for this problem. One approach can be-> first store the prime numbers using the sieve method and then to use a sieve like method to calculate phi of n. Take extra care to use llu while printing out the answer as the output is in the range of unsigned long long.
1008 (Fibsieve`s Fantabulous Birthday) - Observe the pattern of how the numbers are appearing.
1010 (Knights in Chessboard) -  Adhoc problem. Find the pattern.
1012 (Guilty Prince) - Basic bfs problem.
1014 (Ifter Party) - The simplified task is to find the divisors of p - l which are greater than l.
1023 (Discovering Permutations) - One simple way is too use c++'s next_permutation library function.
1033 (Generating Palindromes) - Find the LCS of the given string and the reverse string. Then subtract the LCS from the actual length of the string. Find LCS using DP.
1042 (Secret Origins) -  Adhoc problem. Don't use brute force. See how the bits changes from input to output answer.
1065 (Number Sequence) - Basic matrix exponentiation problem.
1096 (nth Term) - Matrix exponentiation. try to implement the matrix first.
1110 (An Easy LCS) - Find LCS using DP, then backtrack the LCS string if there is any. Also remember to maintain lexicographical smaller order.

Even the Odds!

Contest link: Intra AUST Preliminary Fall - 17

Problem name: Even the Odds!

Required knowledge: Modular arithmetic, big multiplication.
Editorial: Firstly, try reading this Modular Arithmetic or you can google about modular arithmatic and it's properties. Now let's analyze the problem.

Given N and M, we need to find summation of first N even numbers modulo M and summation of first N odd numbers modulo M.
We can observe that the first N odd numbers summation can be found by calculating N * N and first N even numbers summation can be found by calculating N * (N+1).
let, N = 4,

Odd : 1 + 3 + 5 + 7 = 16 = 4 * 4
Even : 2 + 4 + 6 + 8 = 20 = 4 * 5
As the modulo M is really big we can't simply calculate ( (N % M) * ( (N+1)%M) )%M, because the N can be as large as 10¹⁸ - 1 and M can be 10¹⁸, then at the time of multiplying, it will overflow. How can we do this without overflow? We will simply use a divide and conquer technique to calculate N * N by adding N with N, N times, instead of multiplying them. Let N = 10¹⁸ - 1, M = 10¹⁸.


Now, from modular arithmatic we know that
- (a * b) % m = (( a%m ) * ( b%m ))%m
- (a + b) % m = (( a%m ) + ( b%m ))%m
Say, a = 10¹⁸ and b = 10 and m = 10¹⁸ - 1.
So, ( (10¹⁸ - 1) %10¹⁸ ) * (10¹⁸ - 1) %10¹⁸ ) ) % 10¹⁸= ( (10¹⁸ - 1) * (10¹⁸ - 1) ) % 10¹⁸ = 0 ; here (10¹⁸ - 1) * (10¹⁸ - 1) will cause overflow.
But,(((10¹⁸ - 1)%10¹⁸) + ((10¹⁸ - 1)%10¹⁸) + ....

We can easily add (10¹⁸ - 1 + 10¹⁸ - 1) and then mod it with 10¹⁸. We will do this 10¹⁸ times, and by using modulo operation each time, there won't be any overflow.
As 10¹⁸ is also a very big number, we can do this is O (log10(N)) times with folowing divide and conquer algorithm.


We will use this bigmul function to calculate ( a * b ) % c. We will simply add the number a, b times each with modulo operation. As the range is too big, we can't simply use loop, so we will use this recursion technique of calculating big multiplication in logN time.

Intra AUST Preliminary Round (Senior group) Editorial

Contest link : Intra AUST Preliminary Spring - 17

Diamond lover : Just implement the diamond shape and carefully calculate the spaces between the diamonds.

Easy to solve 1 : From 0 to N, if we X-OR all the integers, we get a binary representation which length is exactly the same length as N. As N is large, using brute force to generate result won't help. We just need to find the binary representation of N and replace every digit with "1". The decimal format of that is the answer.

Strength check :  Just check all the information about the password is whether present in the string or not.

Can you solve it? : It's a bit manipulation problem. If you are familiar with the concept of bit handling it should be easy for you. However, I found a pattern and solved it accordingly. Here is how : Can you solve it?

Longest String : A simple brute force will be enough for the solution. Just implement the code and keep in mind about the alphabetical order.

Can you solve it?

Link: https://www.hackerrank.com/contests/intra-aust-preliminary-round-senior-group/challenges

আমাকে N দেয়া হবে এবং আমার ১ থেকে N পর্যন্ত সব ইন্টিজার এর বাইনারি রিপ্রেসেন্টেশন এ কতটি ১ আছে, তা বলতে হবে। ধরি N = ৮। উপরের চিত্র তে আমি ০ থেকে ৮ পর্যন্ত সংখ্যাগুলির বাইনারি লিখেছি। লক্ষ্য করলে দেখা যায়, এই বাইনারি এর মাঝে একটি নির্দিষ্ট সময় পরপর ১ আসে। প্রথম ঘর এর জন্য একটি ০, একটি ১, এভাবে, দ্বিতীয় ঘরের জন্য দু'টি ০, দু'টি ১, এভাবে... খেয়াল করলে দেখা যায় ব্যাপারটা আসলে ২ এর পাওয়ার হিসেবে আসতে থাকে। আমরা বাইনারি নম্বর এর এই ব্যাপারগুলি অবশ্যি জানি। এখন আমি এই জিনিসটি থেকে একটি প্যাটার্ন বানানোর চেষ্টা করবো।

যেহেতু আমার N জানা আছে, কাজেই প্রথমে N এর বাইনারি বের করে ফেলি। ৮ এর ক্ষেত্রে ১০০০। এখন খেয়াল করি, (ডান দিক থেকে ০ - ৮ সকল নম্বর) প্রথম ঘরে, ০ থেকে ৮ এর মাঝে ১ আছে মোট ৪ টি। দ্বিতীয় ঘরেও ৪ টি, তৃতীয় ঘরেও ৪ টি, চতুর্থ ঘরে ১ টি। মোট ১৩ টি ১ আছে। প্রতি ঘরের জন্য এই ১ এর কাউন্ট টা কিভাবে করবো ? কিছু টেস্টকেস চিন্তা করলে ব্যাপারটা সবার ধরতে পারার কথা। প্যাটার্ন বের করতে পারলে ভালো, নাহলে চিত্রের বামদিকে আমি আমার প্যাটার্ন এর ফরমুলা লিখে দিয়েছি। এখানে xtra জিনিসটি একটু ইম্পরটেন্ট। নরমালি আমরা ১,২,৪,৮,১৬... ২ এর পাওয়ার এর ব্যাপারগুলি সহজে প্যাটার্ন এ ফেলেতে পারি, কিন্তু যদি ৯,১৩,২১,...এরকম নম্বর থাকে, যেটা আসলে কমপ্লিট প্যাটার্ন এর মধ্যে পরে না, তাদের জন্য বারতি কিছু যোগ এর দরকার হয়। ৯ এর জন্য চিন্তা করলে এমনটা দেখা যাবে। যাহোক, এখানে ব্যাপারটা হল N এর বাইনারির length পর্যন্ত আমাকে লুপ চালায়ে আর কিছু ক্যালকুলেশন করে টোটাল কতটি ১ আছে তা বের করতে হবে।

Timus 1014 : Product of Digit

Prob link: Timus 1014: Product of Digit

প্রব্লেম এ চাওয়া হয়েছে যে , আমাকে একটা integer দেয়া হবে, আমাকে minimum এমন একটা integer বের করতে হবে যেখানে ঐ integer এর প্রত্যেক digit এর গুনফল ঐ integer এর সমান হয়।
test case চিন্তা করলে দেখা যায়, N = 10 ;
10 কে এভাবে লিখা যায়ঃ (2 * 5) , (5 * 2) .. দেখা যাচ্ছে যে আসলে 10 এর গুননীয়ক গুলা নিয়ে আমাদের চিন্তা করা লাগবে। দেখা যাচ্ছে  25 , 52 ,... 25 হচ্চে সবচেয়ে ছোট, তাই answre 25 for N = 10;

আমরা কিন্ত ( 1 * 10 ) এই combination টা নেইনাই , কারন 1,1,0 or 1,0,1 এর digit এর গুনফল N এর সমান হয়না।

এখন এটা solve করা যায় কিভাবে ? প্রশ্নে এ বলা হইছে digit এর গুনফল  N এর সমান হবে, এরমানে একটা জিনিস বলা যায় যে আমার উত্তর আসলে 0 to 9 digit এর কোন সংখ্যা হবে।
তাহলে loop এর code অনেকটা এরকম হবেঃ

for ( int digit = 9 ; digit > 1 ; digit -- )

{

         // rest of the code

}

তাহলে তো প্রব্লেম টা খুবই সহজ হয়ে গেলো। আমাদের দেখতে হবে যে 2 থেকে 9 এর মাঝে কোন কোন digit দিয়ে N কে mod করা যায়, মানে ভাগশেষ শুন্য হয়। যখনই কোন সংখ্যা দিয়ে N ভাগ যাবে ঐ সংখ্যা দিয়ে N কে ভাগ করতে থাকতে হবে যতক্ষন N  আর ভাগ না যায়।

 অর্থাৎ,

while ( N % digit ==0 )

আমাদের মূল কাজ হল N এর divisor digit গুলি বের করা,মানে যেসব digit দিয়ে N কে মড করা যায় এমন digit.

এখন যেহেতু আমাদের নতুন একটা integer বের করতে হবে, কাজেই কেবলমাত্র একবার N কে মড করার পরেই থেমে গেলে হবে না, যতক্ষন মড করা যায় করতে থাকতে হবে। কাজেই , while লিখা হয়েছে।
উদাহরন দিলে ব্যাপারটা বোঝা সহজ হবে ,
N = 50  >>  ans = 255
N = 120 >> ans = 358

( Digit নিয়ে কাজ করার এইটা একটা reason , অনেকে Digit না নিয়ে only sqrt ( N ) পর্যন্ত লুপ চালায়ে first যেটা দিয়ে ভাগ যায় সেই সংখ্যা আর  N /  ( সেই সংখ্যা ) ans print করে , যা ভুল ; 120 এর জন্য খেয়াল করলেই বুঝা যায়ঃ

for ( int digit = 2 ; digit <= 9 ; digit++ ){
if ( N % digit == 0 ) {
cout << digit << N / digit << endl ;

                    return 0;

           }

}

120 এর জন্য হবে 260 ,যেটা ভুল কারন  2 * 6 * 0 == 0  ( not 120 )

valid code:

for ( int digit = 9 ; digit > 1 ; digit-- ){
       while ( N % digit == 0 ){
       // rest of the calculation
       }
}
এখন হিসাবের জন্য N = ১০ ধরি,
---> 10 % 5 == 0
কাজেই এটি while লুপ এ ঢুকবে। লুপের ভিতর আমরা দেখি যে 5 একটি ভ্যালিড ডিজিট আমাদের ফাইনাল রেজাল্ট এর জন্য, তাই আমরা 5 কে আমাদের প্রথম ডিজিট হিসেবে নিয়ে একটি ভ্যারিয়েবল ( SUM ) এ সেইভ করে রাখবো।এখন SUM এর মান 5, কাজেই আমাদের এখন N কে 5 দিয়ে ভাগ করতে হবে, কেননা আমরা 5 কে আমাদের ডিজিট হিসেবে নিয়ে নিয়েছি।

কাজেই N = N / 5 = 2

এরপর আমরা আবার দেখবো N % 2 == 0, কাজেই আমরা আমদের পরের ডিজিট টিও পেয়ে গেলাম।

 ( আশা করি এতক্ষনে সবাই বুঝে গেছি আমরা কেন লুপ ৯ থেকে ২ পর্যন্ত চালিয়েছি। )

কাজেই আমাদের ফাইনাল রেজাল্ট হবে এরকমঃ
25  =  2 * 10 + 5 * 1 ( multiple করার ব্যাপারটা তোমরা নিজেরা try করে দেখো )
অর্থাৎ রেজাল্ট = 25।
120 এর জন্য :  3 * 100 + 5 * 10 + 8 * 1 = 358.

Critical test case:

N = 0 হলে আমাদের রেজাল্ট হবে 10, কারন 0 পজিটিভ, নেগেটিভ কোনটিই না এই প্রব্লেম এর জন্য। কাজেই 10 হচ্ছে প্রথম পজিটিভ রেজাল্ট।
N = 1 হলে রেজাল্ট হবে 1.
এখন N যদি প্রাইম নাম্বার হয়? এখানে একটি কন্ডিশন আছে, যা লুপ এর শেষে N কে চেক করে, আমরা এটি বুঝতে পারছি যে, লুপের শেষে N যদি 1 হয়, তাহলে আমাদের ফাইনাল অ্যান্সার হবে -1, কারন কোন ডিজিট ই N কে মড ( MOD ) করতে পারেনি। এটি আশা করি সবাই বুঝে গেছো।

ধন্যবাদ কষ্ট করে পড়ার জন্য।

UVA 11254: Consecutive Integers

Prob link: UVA 11254: Consecutive Integers

Problem টায় বলা হয়েছে আমাকে একটা integer দেয়া হবে, আমাকে ঐ integer টি আরো কতোগুলি consecutive integer এর summation এর মাধ্যমে বানানো যায় তা print করতে হবে।
Suppose 15 কে আমরা লিখতে পারি এভাবে ------>

15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
15 = 15

দেখা যাচ্ছে যে এর মধ্যে প্রথম টির integer সংখ্যা বেশি, তাই আমাকে প্রথম টি ই print করা লাগবে।print করার জন্যে question এ যে format এর কথা বলা হয়েছে, সে অনুযায়ী print করলে আমাদের output হবে এরকম  :::
15 = 1 + ... + 5  ( অর্থাৎ আমাকে consecutive integers এর  first এবং last integer টা print করতে হবে )
যদি এমন integer হয়, যাকে কোন consecutive integer এর summation এ ফেলা যায় না, তখন কেবল ঐ integer টাই print হবে।
Ex : For N = 8  ans   ===   8 = 8 + ... + 8

Solve Technique:

আমরা sum of arithmetic progression সম্পর্কে নিশ্চই জানি।
যদি n তম integer পর্যন্ত summation বের করতে হয়, তাহলে সূত্র ঃ sum, Sn ( n terms ) = n / 2 + [ 2 * a + ( n - 1 ) * d ]
যেখানে , a = first term , n = last term , d = interval between numbers .
আমরা এই সূত্র ব্যবহার করে আমাদের উত্তর বের করবো।
যেহেতু আমাদের বলা আছে , consecutive integers, so আমাদের d এর মান হবে  one  ( 1 ) .
এখন আমাদের n জানা আছে, আমরা চাইলে brute force করে করতে পারি,  কিন্তু আমাদের range টাকে ( 10 ^ 9 ) মাথায় রাখতে হবে।
এতবড় জিনিস বারবার loop চালায়ে করলে TLE  ( Time Limit Exceeded ) খাওয়ার সম্ভাবনা অনেক বেশি, তাই আমরা আমাদের সূত্র ব্যবহার করে একটা ফরমুলা বানানোর চেষ্টা করবো যাতে আমাদের brute force এর time complexity কম হয়।
সূত্র টাকে আরেকভাবে লিখা যাক,  a = ( 2 * Sn + n - n * n ) / ( 2 * n )
হিসাবের সুবিধার জন্য আমরা এভাবে লিখলাম, এখন খেয়াল করে দেখো আমাদের জানা মান হল Sn , যা qs এ দেয়া থাকবে, আমাদের বের করতে হবে a এবং n । আমরা ২ টা কাজ করতে পারি, প্রতি a  এর জন্য লুপ চালায়ে n বের করতে পারি, অথবা উলটা কাজটাও করতে পারি।

এখন কথা হল লুপ চালাবো কতক্ষন ?
equation খেয়াল করলে দেখা যায় আমাদের R.H.S এ আছে 2 * Sn , আমরা square root of 2 * Sn থেকে 1 পর্যন্ত integer এর উপর লুপ চালায়ে n  এর মান বের করতে পারি এবং n  এর মান আমরা equation এ বসায়ে  a এর মান এর validity check করতে পারি।যখন ই আমরা valid একটা মান পাবো তখন আমাদের result এর a হবে
equation থেকে প্রাপ্ত মান এবং n হবে   a + ( যেই মান এর জন্য আমরা valid a পেলাম সেই মান) - 1 ।

Qs 1 : Why sqrt ( 2 * Sn )  ?

Ans : equation থেকে এটা easily observe করা যায়, n * n এই value টার আগে minus sign আছে, কাজেই, আমার  n এর মান sqrt ( 2 * Sn ) এর বেশি হলে negative integer আসবে , যা আসলে ভুল result দিবে।

Qs 2 : a এর validity check করবো কিভাবে ?

Ans : আমরা a = ( 2 * Sn + n - n * n ) / ( 2 * n )  এই সূত্র টা কাজে লাগাবো, sqrt ( 2 * Sn ) থেকে 1 পর্যন্ত লুপ চালায়ে আমরা প্রতি n এর জন্য  a এর মান এর validity দেখবো। a valid হবে তখনই যখন আমার equation এ n এবং Sn বসালে তা সত্য হবে।

a = ( 2 * Sn + n - n * n )  এটা থেকে আমরা একটা মান পাবো, এখন কখন এই মানটা সত্য? যখন a কে  ( 2 * n ) দিয়ে মড করলে মান শুন্য আসবে, কেবলমাত্র তখনই আমরা a এর একটা integer value পাবো এবং value টা হবে ( 2 * Sn + n - n * n ) / ( 2 * n ).

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

LightOJ: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of aⁿ+bⁿ. a and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this mat expo if you don't know about how to create a matrix from a recurrance relation.
First let's observe some cases.

If n = 0, a⁰+b⁰ = 1+1 = 2
If n = 1, a¹+b¹ = a+b - 0
If n = 2, a²+b² = (a+b) (a+b) - 2ab
If n = 3, a³+b³ = (a+b) ( (a+b)² - ab ) - 2ab (a+b)
..............     ..............     .............     .................
So, basically the recurrence somehow turns like this -->
(a¹+b¹) = (a+b) + (-0)
(a²+b²) = (a+b) (a+b) + 2(-ab)
So,

base  =  | (a+b)   -ab  |
             |   1           0   |
We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.
So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)¹  = (a+b) * (a+b) + 2 * (-ab) = (a+b)² - 2ab
When n = 3, ans will be (base)²  = (a+b) * [(a+b)² -ab)] + 2 * [-ab*(a+b)]
Let's see this : (for n = 3)

In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)² -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (aⁿ+bⁿ) modulo 2⁶⁴, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.



"Don't directly copy code. First try to understand how each step works, then do your own coding."