Loser_'s blog

By Loser_, history, 7 weeks ago, In English

hello I am stuck in this problem Digit Queries.I think I need to use recursion here although not quite sure how? Which algo or technique I need to study to solve this problem? Also please share similar types of problems from other ojs.Please help me with that.

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By Loser_, history, 3 months ago, In English

Need help with this digit dp problem Almost Everywhere Zero from Atcoder. Here,I increase the $$$cnt$$$ value if the $$$i$$$ th digit is non zero.Base case is if cnt==k return 1 or 0 otherwise.My submission works for smaller values but fails larger inputs or maybe I am missing some cases.I also see others solutions but couldn't find one using reccursion in my approach. Need help here. Thank you

My submission

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By Loser_, history, 3 months ago, In English

Hello, in this problem 1011 — Marriage Ceremoniesthe priority index is not clear to me. I used bottom up manner and calculate the max adjacent values.

5
5 10 10 2 3
2 11 3 10 10
16 12 1 5 2
4 2 11 5 2
1 8 14 4 13

Ans:60.Which for me 14 11 12 11 10 total 58.What am I missing here? Need help with that.

My code

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e6+5,mod=1e9+7; int mat[20][20],dp[20][20]; int main() { int t,cnt=1;cin>>t; while(t--) { int n;cin>>n; for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { cin>>mat[i][j]; } } memset(dp,0,sizeof(dp)); for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { if(n&1) { if(j==(n+1)/2) { int temp=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]); dp[i][j]=max(dp[i][j],temp)+mat[i][j]; } else if(j<(n+1)/2) { dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j]; } else { dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j]; } } else { if(j<=n/2) { dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j]; } else { dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j]; } } } } //cout<<endl; int ma=0; for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { //cout<<dp[i][j]<<" "; ma=max(ma,dp[i][j]); } //cout<<endl; } cout<<"Case "<<cnt++<<": "<<ma<<endl; } return 0; }

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By Loser_, 5 months ago, In English

I just completed CSES Sorting and Searching section problems. And I didn't find any editorials for this. So I am writing my own approach for the problems.Please do correct me if I made any mistakes and do share your approach for the problems.

My solutions are here

complete editorial for CSES coding platform of all 27 problems in Sorting and Searching section.

1.Distinct Numbers

Editorial
idea

2.Apartments

Editorial
idea

3.Ferris Wheel

Editorial
idea

4.Concert Tickets

Editorial
idea

5.Restaurant Customers

Editorial
idea

6.Movie Festival

Editorial
idea

7.Sum of Two Values

Editorial
idea

8.Maximum Subarray Sum

Editorial
idea

9.Stick Lengths

Editorial
idea

10.Playlist

Editorial
idea

11.Towers

Editorial
idea

12.Traffic Lights

Editorial
idea

13.Room Allocation

Editorial
idea

14.Factory Machines

Editorial
idea

15.Tasks and Deadlines

Editorial
idea

16.Reading Books

Editorial
idea

17.Sum of Three Values

Editorial
idea

18.Sum of Four Values

Editorial
idea

19.Nearest Smaller Values

Editorial
idea

20.Subarray Sums I

Editorial
idea

21.Subarray Sums II

Editorial
idea

22.Subarray Divisibility

Editorial
idea

23.Array Division

Editorial
idea

24.Sliding Median

Editorial
idea

25.Sliding Cost

Editorial
idea

26.Movie Festival II

Editorial
idea

27.Maximum Subarray Sum II

Editorial
idea

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By Loser_, 5 months ago, In English

I was doing a problem from codechef Multiples of 3 but could not figure out why it's getting TLE? My submission. Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Loser_, history, 5 months ago, In English

Hello.I was going through the problem Coin Combinations I which is similar to the next question Coin Combinations II.In Coin Combination II problem I used 2d array to store the dp values and used bottom up approach to solve it.The submission is here.Now I was wondering if Coin Combination I has the similar solution like II using 2d array ? I have gone through many solutions but none of these have used 2d array.So I could not come up with any idea.Please help me with this.

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,sum;
    cin>>n>>sum;
    vector<int>v(n);
    for(int i=0;i<n;++i)
    {
        cin>>v[i];
    }
    int dp[n+1][sum+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=sum;++j)
        {
        	if(j>=v[i-1])
        	{
        		//Condition
        		dp[i][j]%=mod;
		}
        }
    }
    cout<<dp[n][sum]<<endl;
    return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By Loser_, history, 10 months ago, In English

In this problem Kuriyama Mirai's Stones I used segment tree for the sum of range of queries.Firstly I created two segment tree (1st for unsorted array)(2nd for sorted array).For every t=1 I used query in unsorted seg_tree and t=2 I used query in sorted seg_tree.Which I know that creating segment tree is in O(n) and query is O(log(n)).But I have TLE for this approach.How can I upgrade this approach? My submission is here.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Loser_, history, 10 months ago, In English

In this problem , I take the input and I store every value in ith index to a map.If my map[i] has a value than I push both map[i] and i to a vector pair. Here in worst case the code may run in 2*n times which is so to say O(n)times.But how I am getting here TLE with O(n) times? My submission is here.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Loser_, history, 10 months ago, In English

Hello I have been trying to solve this problem using basic star pattern logic. My approach is — first create the upper half of the pyramid and then add the next portion of the pyramid.For that I first initialize all the elements of the 2d array in null value**('\0')**.And my compiler shows the exact same result as in the description.But somehow codeforces compiler showing weird symbols for ('\0') .I have also tried char(0) which also give me weird symbols.My submissions here and here.How can I get ac from this submission?

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By Loser_, history, 13 months ago, In English

1111A - Superhero Transformation I have tried map for tracking either a char is vowel or consonant.And then comparing both the map's element, I may have my expected solution.But implementing map it came to my mind that map is a sorted container.So I google it and from stackoverflow I found this articlefifo_map which actually acts according to plan.But using above mentioned way I have a compilation error(No such directory).Is there any way to include external headers? My submission is here

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it