Final standings of SPC Round 69 is here

Editorial :

A. Minimize Maximum Pair Sum:

To minimize the maximum pair sum you can pick maximum + minimum, 2nd max + 2nd min, 3rd max + 3rd min..... Among all such pairs, the maximum pair sum is the answer. You can do this using two pointer after sorting the array.

Time complexity : O(nlogn)

Code

B. The Ancient Tree of Fahimland.

In this problem, the tree will not remain tree anymore if vertex u is an ancestor of vertex v. Because it will create a cycle containing u and v. So now the problem has been simplified as finding u is an ancestor of v or not. if LCA(u, v) is u, u is an ancestor of v and you can answer NO.otherwise YES. To find LCA you can use binary lifting. Tree can have maximum depth 2^20. Too many good blogs / tutorials are available in google YouTube. You can check the topic.

Time complexity : O(20N + 20Q)

Code

C. Colorful Puzzle:

Imagine Fahim's luck is worse than the worst. If he pick 2N balls where was N red balls, N green balls. (shit) Okay Let's pick one more ball, now it’s confirmly he will pick the blue ball because all remaining balls was blue. So, 2N+1 balls he should pick to get all colors of balls at least one.

Time complexity :o(1)

Code

D. The Magical Palindromic Potion:

For every integer, if It's palindrome then add it to the answer.

Time complexity : o(nlog(1000))

Code

E. Fahim's Binary Sorting Puzzle:

The greedy part is : for every 0, you need to do p operations where p is count of 1's left of that 0. Go from left to right, keep a counter of 1. For every 0 you found add counter to your answer.

Time complexity : O(n)

Code

F.The garden Fence :

You are given the perimeter n. Let say two side is a and b. 2(a+b)=n, a+b=n/2. To maximize your area, you need to maximize the minimum among a and b. So if a+b is even then a = b = (a+b)/2, otherwise a = (a+b)/2 and b = (a+b)/2+1. Then a*b is the answer.

Time complexity :O(T)

Code

G. Evenly Digitized:

You can see that only first position can have 4 digits and other positions can have 5 digits. As leading zero is not acceptable. For length x, the answer will be 4x5^(x-1). Using larg exponentiations, you can find for every digit in logarithmic time. Then use prefixsum technique Precomputation to find every segments sum in query with o(1) complexity.

Time complexity : O(10^6 logn).

Code

Hope you find this round educational. Thanks for participating this round.

We are going to arrange a programming contest. Hope you will find it Educational. This contest is suitable for below EXPERT on codeforces

SPC Round 69

This Friday, 25 october at 9:00 pm (Bangladesh standard time).

Duration : 3 hour

Contest link : here

SPC Round 68 has been finished. Congratulations to all of the winners of this round.

The standings of this round is :here

The problem set of this round is:here

Editorial:

A.Programmer Homecoming :

Imagine three straight lines a, b, c. a = distance of (0,0) to pillar, b = distance of pillar to home, c = distance of (0,0) to home. These distances are euclidean. If the pillar is on the way to line c, then can't go home. If a + b = c then the pillar must belong to line c otherwise not.

Time complexity :O(1)

code

B.Love palindrome :

According to the palindromic character we need to make equals of A[i] and A[n-i+1], (1 <= i <= n/2). All such pairs are unique. For, every n/2 pairs the cost will be minimum of their distance and x. Sum up all n/2 costs for final answer.

Time complexity :O(n)

code

C.Nice Pairs:

It can be proved that two numbers p and q can be Nice Pair if there is an integer x that satisfies x^3 = p and x^2= q. Because p^2 = x^6, and q^3 = x^6 so, p^2 = q^3.

Instead of going for p or q we will go for x. So, it's enough to iterate x from 1 to 10^6 because our element limit is 10^18. If x > 10^6 then p will cross 10^18 which doesn’t exist in our array, we don't need to go beyond 10^6. for every x we add frequency(x^3) * frequency(x^2) to our answer. As combining them for every p with every q.

Time complexity : O(10^6)

code

D.HUNGKY MUNGKY:

We need to count the number of such elements which is either dividable by A or dividable by B or dividable by C (dividable by at least 1 element among A,B,C) and not more than N. We can get them by answer = N/A+N/B+N/C. But some elements might be counted multiple times. How many elements are counted multiple times? N/lcm(a,b), N/lcm(b,c),N/lcm(a,c) elements are counted multiple times. We must subtract them.so, answer = N/A+N/B+N/C-N/lcm(a,b)-N/lcm(b,c)-N/lcm(a,c). But N/lcm(a,b,c) valid elements are subtracted of their all occurrences. So we need to add them again. answer = N/A+N/B+N/C-N/lcm(a,b)-N/lcm(b,c)-N/lcm(a,c)+N/lcm(a, b, c).

Time complexity : O(T log(10^9)).

E.Children's intelligence game:

This can be solved multiple way but I want to explain about hashing + binary search. Let's see how we can find the lexicographically smaller string between two string using binary search. Using binary search, our target is to find the smallest position where character of two strings differs. If we can find that position then we can find the smaller string by comparing only that character. In binary search, for every mid if we find hash of s1[l...mid] = hash of s2[l...mid] then we need to go to right because left part are equal otherwise we need to go to left because somewhere in the left has difference.

Let's use it in our problem. Given string s has length n. Declare, str=s+s. Create hash of string str of length 2n. keep an pointer p that points the position where the lexicographically smallest string starts, initially 1. Now, iterate over i = 1 to n, compare between substring str[p, p+n-1] and str[i, i+n-1]. If you find the str[i, i+n-1] smaller then update p=i. At last print the substring s[p....n] + s[1....p-1].

Time complexity :O(nlogn)

code

F. Fahim's magic stones:

Precompute the L array of length n where L[i] stores maximum subarray sum that ends at position i (1 <= i <= n).

Precompute the R array of length n where R[i] stores maximum subarray sum that starts at position i (1 <= i <= n).

What will be the maximum subarray sum if you don’t remove any value from the array? The maximum value of the array L and R. Keep that maximum value in the answer initially.

Then for every index i (1 < i < n), if you remove the index, you will get L[i-1] + R[i+1]. Update this with your answer. Removing the first and last element has already been calculated while taking the max of L array and R array.

Time complexity :O(N)

code

Thanks for participating this round.

Hope you find this round educational. For the furthermore contest updates join our discussion group here.

We are going to arrange a programming contest. Hope you will find it Educational. This contest is suitable for below EXPERT on codeforces

SPC Round 68

This Friday, 18 october at 9:00 pm (Bangladesh standard time).

Duration : 2 hour

Contest link : here

The problem set of SPC Round 67 is here

The final standings of this round is here

Congratulations to the winners of this round.

Last digit :

You dont need to care about any other digit except last digit of every elements. Multiply and go forward and keep modding the result by 10 so that the multiplication result always remains one digit.

Time complexity :O(n)

IEA Capital :

This problem can be break down as 'all pairs distance sum of the tree' and the result will be multiplied by 4. Because you travel 4 times between every pair (u, v).

Now Let's solve the problem : all pairs distance sum of a Tree.

Maintain an array sub[n], that keeps the subarray size of every node. When backtrack from dfs update parent nodes subarray size as sum of its all child's subarray size. And then add one for the node itself. Let's see how we can use the idea of contribution here. If we notice carefully that our final answer constitutes only the edges of our tree. (i.e.,) Our final answer is just a collection of edges taken many times. So, our basic entity of the final answer is my edge of the tree. Let's iterate on each edge and find its contribution. Basically, I am fixing my edge say (u,v), and trying to find how many of the paths contain this (u,v) edge. Number of nodes left to this edge times Number of nodes right to this edge. Because if any nodes you select from left of the edge as starting and any nodes you select from right of the edge as ending then (u, v) edge belongs to their path. Left nodes is actually sub[u] and right nodes are actually N-sub[u] (v is parent of u). Edge (u, v) contributes sub[u]*(N-sub[u]) to the answer.

After finding the answer, just multiply it with 4.

Time complexity :O(n)

Ideal array :

You can't change the last value of the array. So, calculate the number of elements which is not equal to last element. That will be the answer.

Time Complexity :O(n)

Ideal array | :

For every value A[i], you can make all value equal to A[i] that costs N-frequency[A[i]]. For all i from 1 to N, count the minimum cost to make all elements equal to A[i]. Maintain a variable that keep tracks of minimum cost among all A[i]. That will be the answer.

Time Complexity : O(n log n).

Permutation subarray :

Store positions of all array elements in a pos map or array. We will go from 1 to MEX of the array and maintain two pointer lo and hi. initially make lo = n+1, hi = -1. for every i, update lo and hi with pos[i].
if pos[i] < lo, lo = pos[i] if pos[i] > hi, hi = pos[i] If hi-lo + 1 == i, that means the subarray [lo....hi] is a permutation. update your maximizing answer with this length. Lastly you got the answer.

Time complexity :O(nlogn)

Divide by 9:

If you set x = 1, then N will be divided by 9. because, N looks like N = 99999....

now go through all the multiples of 9. like x = 1 + 9*0, 1 + 9*1, 1 + 9*2, 1 + 9*3, 1 + 9*4........ 1 + 9*y. If y is even positive number then 1 + 9*y must be a prime number. Otherwise not. Now you have to find p-th smallest y which is even. And that y is nothing but p*2. So, answer will be 1+9*(p*2) = 1 + 18p.

Time complexity :O(t).

Last character:

go through the last character to first character of the string, if you find any lowercase letter then output that and break. If your iterator goes front of the first character that means there is no lowercase letter in the string, print -1 in that case.

Time complexity :O(n)

All the submissions of this round is open. You can check them out from the contest page.

Hope you find this round educational. Thanks for your participation. Any kinds of suggestions are welcomed.

We are going to arrange a programming contest. Hope you will find it Educational. This contest is suitable for below EXPERT on codeforces

SPC Round 67

This Friday, 11 october at 9:00 pm (Bangladesh standard time).

Duration : 2.5 hour

Contest link : here

The SPC Round 66 problemset are here

BCB :

Just keep all the names in a string array and find is the given string available in that array or not

Bosses of an array :

Iterate from last to first and maintain a max_value variable that keeps track the maximum value of the suffix of that array. If current position is equal to the max_value then count it as boss.

Successive Number :

you need to maintain the ratio equal among a:b and b:c. Let's say r = a / b then c = b * r

Calculate from valid expression :

Keep track a parity (initially even). Your current integer may be positive or negative. Let's say positive means even team and negative means odd team. Then if even parity and even team or odd parity and odd team found then the current integer will be added to your answer otherwise it will be subtracted. The parity can be changed if "-(" is found anywhere and also can be changed if ')' is found and it is ending of a "-(" starting. We can use stack to keep track that. Also be careful, a number between two arithmetic sign may not fit in 64 bits. So, keep moding the answer carefully.

An usual function :

Hash the frequency of the array elements. Do sieve, and add contribution to all multiple of current value by current value's frequency. The find the maximum contribution.

All submissions are open in this contest. You can check them from every challenges page. Thank you for attending this round.

The Contest link is : here

EDITORIAL :

Simple Game:

Intuition : For this problem , it can be proved that for any number not having length 2 , you can make any digit to remain last digit. So the minimum digit of the number is the answer if the number is more than 9 and less than 100, the last digit will be the answer as alice has only one possible move.

For more than two digit, keep the minimum digit in the second position, and do operation on other positions. When the minimum digit comes at the end then swap it with the first number. In this way Alice can make the minimum digit as answer.

Time Complexity : O(T log N)

Space Complexity : O(1)

Code : here

Two Jar:

Intuition : The jar who contains maximum kg of food is the answer.

Time Complexity : O(1)

Space Complexity : O(1)

Code : here

Make more Profit:

Intuition : Suppose you are selling the book on i-th day (1 <= i <= n) , then you should buy the book the minimum costs of x-th day (1 <= x <= i) . Then you get maximum profit for selling i-th day. The profit will be A[i]-A[x]. SO, for every i (1 <= i <= n) we have to find this profit and the maximum profit among them is the answer. So we go through i from 1 to n and update a minimum value and calculate the profit.

Time Complexity : O(n)

Space Complexity : O(n)

Code : here

A pond of Lotus:

Intuition : We saw that the lotus becomes double for every night. So, from one lotus, we found X amount of lotus where X is a power of two. Now we have to find minimum k where N = X1 + X2 + X3 + …… + Xk. In bit manipulation we know that the number who is power of two has exactly one set bit. So, if N has M set bit then this M will be the minimum possible k that earlier I mentioned. So count of set bit of N is the minimum number of Lotus you have to buy. Then k * P will be the minimum taka you need.

Time Complexity : O(T log N)

Space Complexity : O(1)

Code : here

Mex of subarray:

Intuition : You have to use contribution technique for this problem. Firstly keep track of the posititons of all the elements. Them go through value 1 to n , calculate their contribution on the answer. Let’s calculate contribution for x (1 <= x < n) . Let’s say The number of subarray that’s MEX is x is equal to C. Then x contributes C times x to our answer. Let’s see how we can calculate. We kept all the position of value 0 to x — 1 in a set. Now, find a segment [L, R] with minimum distance or R-L such a way that all positions of value 0 to x-1 remains >= L and <= R. The L is actually minimum value of the set and R is the maximum value of the set. We can get this with logarithmic complexity from set.begin and –set.end . To make x as a mex for any subarray starting form l and ending at r, we need to cover the segment [L, R] by [l, r] as the values 0 to x-1 remains in segment [L, R]. So, we can say that l <= L and r >= R. If the position of x is greater than L and smaller than R , we can not get any subarray that makes mex = x. So , we can skip there, but if x is smaller L or x greater than R then we should calculate C . C is number of subarray [l, r] that covers [L, R] but not covering position of x, as we want x as mex.

If position of x < L then possible l are L-pos[x] and possible r are N-R+1.

If position of x > R then possible l are L, and possible r are pos[x]-R. 

Then the C = possible l times possible r. And contribution of x = x times C. After calculating for the x, update the position of x to your set.

Time Complexity : O(N log N)

Space Complexity : O(N)

Code : here

We are open , We are looking for Problems:

Intuition : This is very basic dp problem . If you calculate the beautiful names of type — Z or Type — A then it’s enough. Because Type — A and Type — Z has equal number of beautiful names. But there are 26 common names which is also type A and Z. those are n equal character x, a <= x <= z. So, calculating only Type — Z is enough.

To calculate the Type — Z, use dp of n times 26 states. For every position, keep track what was the character of the following previous position. If the previous state was character x (a <= x <= z) then try to keep the character y ( x <= y <= z) in the current position and move forward and calculate. Make sure you calculate for all possible length before test case to cover in time limit.

Time Complexity : O(26 * N)

Space Complexity : O(26 * N)

Code : here

Thanks for your participation of the SPC Round 65. Hope you enjoyed this round.

You can follow us on facebook for next contest update here.

We are going to arrange a programming contest. Hope you will find it Educational. This contest is suitable for below EXPERT on codeforces

SPC round 65

This Friday, 7 September at 9:00 pm (Bangladesh standard time).

Duration : 2 hour

Contest link : here

tourist became Tourist !!!

But once I caught anotherTourist !

The contest link is here.

EDITORIAL :

SONAMONIDERPROGRAMMINGADDA :

Tutorial : The greedy part of the problem is you can make string S any of it's permutation. So, You just sort the given string and "SONAMONIDERPROGRAMMINGADDA" string , after sorting if both of them are equal then it's yes possible otherwise not.

Time Complexity : O(|S| log |S|)

Space Complexity : O(|S|)

C++ Code

Alice wants to win :

Tutorial : Alice will win only if the number of moves becomes odd. Now imagine a number _n >= n and _n is multiple of m. Now , the game will progress like n → _n → 0. In this way if you get odd number of moves then it's yes Alice wins. Otherwise the moves is even. now, you can go one more multiple of m. In this way if you go n → _n + m → 0 then parity of move will only change if m is even. Because if m is odd then you move odd times forward and one time backward. ultimately the parity will not be changed. So, now just check if m is even then moves parity will change and you can say yes otherwise there's no way to make your moves count odd.

Time Complexity : O(T)

Space Complexity : O(1)

C++ Code

Diagonals on a board :

Tutorial : In the sample testcase description you will find that 2*n-1 diagonals are available for n*n board.

Time Complexity : O(T)

Space Complexity : O(1)

C++ Code

Free Diagonals on a board :

Tutorial : You can use binary search to find maximum free diagonals. Imagine a mid for the free diagonals , then calculate calculate minimum possible amount of cells holding these diagonals so that maximum buttons can be kept other cells . To calculate this you can choose a greedy part that the cells amount series looks like 1, 1, 2, 2, 3, 3, ...... n-1, n-1, n. From this series you should pick first mid elements sum. Then occupied cells will be C = n*n — sum of first mid elements. You can make equations for the sum of first mid elements. Now if C >= K , then mid diagonals are enough to keep their all cells empty. sol go for right segment for more free diagonals otherwise go left.

There's one corner case, The n can be equal to 0, in that case answer shouldn't be -1, answer will be 0. It's silly harassment though.

Time Complexity : O(T*log N)

Space Complexity : O(1)

C++ Code

Searching more AND :

Tutorial : For every bit 33 to 0 you just calculate AND of all elements in this way : if the bit is off for ith value upadate current AND by AND operation with (A[i] + k) otherwise just update current AND by A[i]. For all 34 different AND , the maximum AND is the final answer.

Time Complexity : O(N * 34)

Space Complexity : O(N)

C++ Code

360 Clock :

Tutorial : Maintain a set of elements that represents the all possible positions where you are just before the current move. As there are at most 360 positions , so the size of the set must not exceed 360. For every position , update all positions with +A[i], and -A[i]. If there were X positions just before this move, now 2*X positions will be after the current move. But as you maintaining a set of size 360. The set size will never get more than 360. Always do not forget to keep the positions inside [0, 360) by mod with 360.

After all N moves print the set size and all the positions.

Time Complexity : O(N * 360)

Space Complexity : O(N * 360)

C++ Code

Fever is called Jor not Xor :

Tutorial : This is very basic problem on Trie. You need to keep track on 33 bit to find the answer for the current position while going with pre Xor and update the bits for pre Xor on the Tree. For all maximum answer between 0 to i the maximum value is the answer for the ith index. You can maintain a dp array to keep track the maximum of the back. You can find a related helpful video here.

Time Complexity : O(N * 33)

Space Complexity : O(N * 33)

C++ Code

Substring of string

Tutorial : You can create a rolling hashing structure to get substring hash. and match any substring of S with t in o(1). Just go from 1 to |s|-|t| and check if the hash of substring [i, i + |t|-1] of s is equals to hash of string t then count one more. You can also solve this using KMP algorithm and Z-algorithm.

Time Complexity : O(|s| + |t|)

Space Complexity : O(|s| + |t|)

C++ Code

For further contest updates you can follow our facebook page here.

We are glad to share that we are going to arrange a programming contest. This contest is suitable for those who are below EXPERT on codeforces.

In this round , the problem setters are : piyash_basak , FahimR and mahfuzswe

I hope you guys take part in this contest and support us for our little efforts.

Contest Link : Click here

Contest Time : 23 August at 21:00 (Bangladesh Standard Time)

Duration : 2 hours 15 minutes

Hope you find all the problems interesting and difficulty will not be sorted. I apologize for any kind of mistakes if we do. Thank you.