Contest Link : Kick Start - Google’s Coding Competitions
I was able to fully solve the 1st one. No idea how to approach 2nd or 3rd one.
Even getting a brute force algorithm was hard, I think.
Do share your approaches.
Thank you 
2 Likes
Bro can u please share your solution outline for the 1st prob. I got WA in the 1st one itself.
1 Like
Idea :
I can say this is similar to sliding window concept.
We will take the useful ones while we traverse and decrease the non - useful ones.
Detailed_description :
Maintain frequency array,
Also maintain a global counter which will help you answer queries for each i from 0 to n-1.
Maintain at which h you are currently, so we have
prev_h = 0;
While iterating,
1 . required_h = (prev_h +1 ) ;
2 . Increase freq[a[i]] ++ ;
3 . Check if we can include the value of a[i] in our global counter,
therefore, if( a[i] >= required_h ) counter++;
4 . Now check if our counter is equal to or greater than curr_h , if it is then we can increase our
value of prev_h . Then we need to subtract the non -useful values to our counter due to a[i] ==
curr_h which is counter = counter - frequency[curr_h]
5 . else continue;
My submission: Cmyz6j - Online C++0x Compiler & Debugging Tool - Ideone.com
3 Likes
I am sharing my solution for 3rd problem:- Its a part of code you can try out like this.
fr(kase, 1, T) {
memset(dp, 0, sizeof dp);
cout << “Case #” << kase << ": ";
int val = 0, cnt = 0;
fr(i, 1, 9) {
cin >> a[i];
int c = (a[i] + 1) / 2 - (a[i] / 2);
cnt += c;
val = (val + i * c) % 11;
}
dp[0][val][cnt + NN] = 1;
fr(i, 0, 8) {
fr(j, 0, 10) {
fr(k, 0, 2 * NN - 1) {
if(!dp[i][j][k]) continue;
fr(x, -min(50, (a[i + 1] + 1) / 2), min(50, a[i + 1] / 2)) {
if(k + 2 * x >= 0 && k + 2 * x < 2 * NN) {
int kk = ((j + 2 * (i + 1) * x) % 11 + 11) % 11;
dp[i + 1][kk][k + 2 * x] = 1;
}
}
}
}
}
if(dp[9][0][NN] || dp[9][0][NN + 1] || dp[9][0][NN - 1]) {
cout << “YES” << endl;
}
else {
cout << “NO” << endl;
}
}
return 0;
Can you please provide an explaination for your code?
Very nice approach bro. Got it now.
1 Like
I have solved it with BIT and Binary Search.
https://medium.com/@asheshvidyut7/google-kickstarter-round-h-2019-h-index-8d7bfdc0a1ae
There is no need of binary search in this case we know that ans could be increased by atmost one in each step so we just need to check the frequency is sufficient for that case.
solution link
my solution complexity is max(ai)*log(max(ai)),but this could also be solved using multiset in n log n.which is better than mine solution.
for further queries,
follow this codeforces blog
For the 1st Problem I was getting TLE, Can anyone help me to understand why
import java.util.;
import java.lang.Math.;
import java.io.*;
public class Solution{
public static void main(String[] args){
Scanner sc=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int T=sc.nextInt();
int count=1;
while(T>=count){
System.out.print("Case #"+count+": ");
count++;
int N=sc.nextInt();
int[] a=new int[N];
for(int i=0;i<N;i++){
a[i]=sc.nextInt();
}
//int a[] ={1,3,3,2,2,15};
int b[] = new int[100001];
int h=-1;
for(int i=0;i<a.length;i++){
for(int j=1;j<=a[i];j++){
if(b[j]==-1) b[j]=0;
b[j]++;
if(j==b[j])
h=Math.max(h,j);
}
System.out.print(h+" ");
}
System.out.println("");
}
sc.close();
System.exit(0);
}
}
I have observed many people has used BIT , but I find it very complex.How come people coming with that much complex approach in first 3-5 minutes (I wonder) , The Priority Q approach which is given in analysis is elegant
Yeah , your approach is right but time complexity is high O(n^2) . you can discard the elements which does not increase the the H value. For this you can go with priority queue that is simple and also elegant and time complexity reduces to O(nlogn).
1 Like