Real Cool Problems and Answers

Real Cool Problems and Answers
In this blog I will keep updating the most beautiful questions I find in the day and the concept behind it and also briefly explain it. This would help me make notes and you to see beautiful problems with some hints.
Before starting, prepare yourself to try some of the best problems you have on codeforces and hackerrank and much more.
Please comment good questions and concepts you want to understand(I am not a pro, we would understand it on our way).

• Mixing Water:

Link:https://codeforces.com/contest/1359/problem/C

Concept: Simple yet elegant math. A simple question but the catch is somewhat tricky.Simple two equations. Let x be number of cups of hot water, y be number of cups of cold water, and the net temperature would be (x*h+y*c)/(x+y). We want this to be as close as possible to t.
Suppose ths expression is equal to t then equation becomes (x*h+y*c)=t*(x+y). and my x can be y or y+1(think about it or comment if you can't figure it). So two equations, two variables and if you have done your class eighth quite well you can figure the rest. If you still get an error(which you would if you don't do right type conversion) please check out my submission

Solution link:https://codeforces.com/contest/1359/submission/81882214
 

•  Largest Rectangle:

Link:https://www.hackerrank.com/challenges/largest-rectangle/problem
Concept: You can use a simple brute force for 26 points which is O(n^2). Just find all subarrays and calculate area of rectangle. Very simple.
For full points there are two ways:

1. Divide and Conquer: A simple divide and conquer idea. Just find minimum element in the array and the answer would be maximum of the the answer in left part of minimum , right part of minimum and the answer which contains minimum. But to find minimum if you use simple for loop then the approach will become in O(n^2) in worst case. So use of segment trees to calculate minimum value will be required. Would update once done.
2. Stacks: No idea about it. Would update soon.

• AND XOR OR

Link:https://www.hackerrank.com/challenges/and-xor-or/problem
Concept: First try to reduce the big function they gave you. It would reduce to m1^m2. Comment if you need help here.

A piece of advice: Whenever you try to solve any question related to bit manipulation, just visualize the process, and never hit and try in such cases because bit magic is the most dangerous magic, never directly search or look for an end result.

So that was quite simple. Now the big problem is again the time complexity. If you do brute force it would be O(n^2) which is not gonna accepted as N can be as large as 10^6.
So the solution is based on stacks and it is not at all intuitive.

• XOR SUM

Link:https://atcoder.jp/contests/abc050/tasks/arc066_b
Concept: I am still confused on it and have no clue would update you soon.

• The Best Vacation

Link:https://codeforces.com/contest/1358/problem/D
Concept: A bit hard implementation problem. Though the logic is quite simple, you have to find the biggest sub-array with the maximum sum but the twist is that the array you are given is not simple.
Okay, so you have to create a new array b(let original array be a) which will hold the corresponding values of hugs(actually they should have said kisses) he would receive(yeah, its bad to be single and I am really jealous) with n*(n+1)/2 formula. Then there are two cases:

1. The number of days in any one is greater than or equal to x. Simple you would do max_days*(max_days+1)/2-x*(x-1)/2
2. Else to be updated soon: /
    

• Chef, Chefina and Their freindship

Link:https://www.codechef.com/COOK118B/problems/CHEFSHIP

Concept: okay, so I am not sure why they give problems with a romatic story, but let it be. This question can be solved using brute force due to weak test cases but if we be loyal; to ourselves then it should be done using string hashing or KMP algorithm . If you want to know more about string hashing refer this link they have explained it in great detail.:https://cp-algorithms.com/string/string-hashing.html So once you have gone through this the implementation is quite simeple:to be updated.

ALERT: NOW I WOULD BE GIVING LINKS TO YOUTUBE VIDEOS WHICH I WANT TO SEE BUT HAVEN'T SEEN IT.
Binary Indexed tree:https://www.youtube.com/watch?v=DxN5-Y8Ld4c&t=93s 
Recursion:Click here
Segment Trees:https://www.youtube.com/watch?v=nWwt7w2s1So&list=PL2q4fbVm1Ik6v2-emg_JGcC9v2v2YTbvq
Dynamic programming:https://www.youtube.com/watch?v=_dbviFz2aZs&list=PL2q4fbVm1Ik4ktv2_1O1atXoeV7whMAy_

• Spy String

Link:https://codeforces.com/problemset/problem/1360/F

Concept:Would update soon

• Kth Beautiful String

Link:https://codeforces.com/problemset/problem/1328/B

Concept: A simple but hard to detect.(atleast for me it was hard)

Hint1: There are only two b's(I know it's not a hint but think now)

Hint2:The positions of these b's have  a pattern(not direct). How many positions does the first character of b cover before the second b can move? Suppose the second b is at position x(from left). The first b moves n-x positons(or there are n-x words before second b holds the next position.

Now, we got a nice idea.  In each iteration cut off n-x-1 from k if k>n-x-1(because this number of words have been covered) else my b would be at the xth position and second b would be at n-k position. Still confused? Go check my solution and do a dry run to understand code better.

Solution:https://codeforces.com/contest/1328/submission/83919624

1. Pair of topics

Concept: A simple again(just shuffle the equation. The equation given to you is a[i]+a[j]>b[i]+b[j]

Just rewrite it as a[i]-b[i]>b[j]-a[j] or if we make an array c where c[i] represents b[i]-a[i] then this equations turns out to be -c[i]>c[j]. But we need to find all possible c[i] , the obvious naive approach is O(n^2)(I am not going to discuss it here) But if we wanted to do O(n^2) why not just pull all the pairs? So,, the O(nlogn) approach is quite simple. Sort c and then iterate over c to find -c[i] by lower bound(google it if you don't know).

Solution link:https://codeforces.com/contest/1324/submission/83920196 

 

• Special Elements

Concept:Okay, so we can do it in O(n^2) time but we have to do it in O(n) auxiliary space. Now read the question backwards. You got it. Don't worry if you didn't. So, the simple trick is don't first go to an element then search for a[i]+...a[j] be equal to current element but search for an element after computing the sum. Now, you could have used lower_bound here but the time complexity is rather strict and you have to do it in O(n^2) only. So, instead make an array(I named it "is") if is[i]==1 then, i is special

Solution link:https://codeforces.com/contest/1352/submission/83901578

• Nice Matrix

Concept: We want to make the four points equal: a[i][j],a[i][m-j-1],a[n-i-1][j],a[n-i-1][m-j-1], and that is pretty obvious. But we would make them equal to a same number, say x, such that abs(x-a)+abs(x-b)+abs(x-c)+abs(x-d) is minimum. And median minimizes the sum of absolute deviations. Proof is here

Solution link is here