forget_it's blog

By forget_it, history, 4 years ago,

Please help me to figure out why i am getting Runtime in this problem — This was my first time implementing trie

And i got Runtime for larger sub tasks in google kickstart A 2020 , problem D

My Code
• -2

By forget_it, history, 4 years ago,

Round #633 div2 C (yesterday round):

While Practicing ,I got AC in it ,but i am still not convinced that my solution is correct.

I looked for editorial they said to approach d/f approach as 1 +2 +4 +.... to reach a number . But ,i just simply found the minimum power of 2 which is greater than or equal to our maximum difference. And output that power.

Also to note that in question it was said 2^(x-1) is added to x cost only , but i didn't consider that , i added x for 2^x but still passed TC.

Please Someone tell me ,why i am correct Or give some test case where my solution fails.

76475571

• -3

By forget_it, history, 4 years ago,

Can anyone please ,provide links or material (video lectures) ,from where you prepare for your non — cp topics :

1. Computer Architecture and Organisation (mips 8085, pipelining,etc.)

2. Operating System

I searched few videos on youtube ,but many of them were confusing (too long) and missing some topics.

• -4

By forget_it, history, 4 years ago,

Please suggest me ,which one is better for College exam Practice (Leetcode vs Interview Bit) .

Currently i do Codeforces , Codechef and atcoder for CP . And now want to add One more platform (Career centred) to my list . Which one is better choice ? , suggest me from your past experience.

• -15

By forget_it, history, 4 years ago,

Please tell me how to approach grid based problems ,especially regarding counting of possible ways to do something.

Is there any algos related to it, please list them.. Any Study material related to these type of problems will help .

for eg. problems like (from codejam):

Problem 1

Problem 2

• 0

By forget_it, history, 4 years ago,

Can anyone please tell me why my solution is not working for larger subtask,(while smaller is correct)

I made a dp to (i,j), where i denote number of stack inclused , while j represent number of plates need to choose.

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.flush();
ll t=1;
ll CaseN=1;
cin>>t;
while(t--)
{
ll ans=0;
ll n,k,A[100][100],p;
cin>>n>>k>>p;
ll c=0;
memset(A,0,sizeof(A));
for(ll i=1;i<=n;i++)
{
c=0;
for(ll j=1;j<=k;j++)
{
ll z;
cin>>z;
c+=z;
A[i][j]=c;
}
}
ll dp[101][101];
dp[0][0]=0;
for(ll i=1;i<=n;i++)
{
dp[i][0]=0;
}
for(ll i=1;i<=p;i++)
{
dp[0][i]=0;
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=p;j++)
{
ll cc=0;
for(ll l=0;l<=(k,j);l++)
{
if(j-l>=0)
{cc=max(cc,dp[i-1][j-l]+A[i][l]);}
}
dp[i][j]=cc;
}
}

ans=dp[n][p];
cout<<"Case #"<<CaseN<<": ";
CaseN++;
cout<<ans<<endl;
}

return 0;
}


• -3

By forget_it, history, 4 years ago,

Why are we not able to access analysis and submissions of other users in google kickstart contests before 2018.

Is there any platform ,where i can find their editorials or any discussion pages for them. I looked for cf discussion pages for it ,but it contains nothing.

• -9

By forget_it, history, 4 years ago,

How to count number of squares posible in a m*n grid.

I know formula to count squares which are parallel to given grid. i.e. m*(m+1)*(2m+1)/6 + (n-m)*m*(m+1)/2;

but how to do it for squares which are not parallel to given grid. How to count them??

• -11

By forget_it, history, 4 years ago,

please help me in following problem , i tried to read its analysis ,but was unable to understand its optimised solution . I looked for various people solution ,they had used bfs, but i am unable to interpret that too.

Just give me the way ,through which i should approach this problem .

Google Kickstart 2019 round A . Problem 2

• 0

By forget_it, history, 4 years ago,

please help me in following problem , i tried to read its analysis ,but was unable to understand its optimised solution . I looked for various people solution ,they had used bfs, but i am unable to interpret that too.

Just give me the way ,through which i should approach this problem .

Problem

• 0

By forget_it, history, 4 years ago,

Recently ,in educational round 83. In question D , i deduced a formula

for(i=n-1;i<=m;i++) { ans=ans+((nCr(i-1,n-2,mod))%mod; } And after that ans=(ans*pow(2,n-3,mod)*(n-2))%mod;

After looking for correct solution i found correct ans was nCr(m,n-1)*(n-2)*pow(2,n-3).

But later observe that for smaller test case my formula was working ,but giving Tle ,at larger tc.

So it that means expression nCr(m,n-1,mod) is equal to summation of nCr(i-1,n-2,mod) ; i range[n-1,m] .

If it is so ,can anyone help me to prove it..

here is my solution link 72867206

• +2

By forget_it, history, 5 years ago,

thanks jef , for pointing my mistake ... i got confused as all my other test cases were correct . i confused myself in it. looks like ,i need to work on my code again .

• -12