Hi, I have written a simple dp solution for this problem ==> https://mirror.codeforces.com/contest/383/problem/D.

But its something strange that it gets accepted without memory optimizes ==> https://mirror.codeforces.com/contest/383/submission/68460051

and it doesnt get accepted with memory optimize ( Every state gets update only from before (i-1) So we can only have 2 rows). https://mirror.codeforces.com/contest/383/submission/68460038

The only thing that different is in these two solutions is simple memory optimizing.

UPD: solved

Hi, I solved this problem with a very simple dp and it was an editorial idea too but at the end of the editorial, it mentioned that we can optimize it but I can't get how we can do this? problem link ==> https://mirror.codeforces.com/contest/711/problem/C

We compute the following array : dp[i][j][k] denoting the minimum amount of paint needed to color the first i trees such that it has beauty j and the i-th tree is colored by color k, and initialize all these values to ∞. We can compute this dp array easily by considering two cases :

1. When the last color used is equal to the current color, then we should compare it with dp[i - 1][j][k] + cost[i][k] if it was originally uncolored or dp[i - 1][j][k] otherwise, since the beauty of the coloring is the same.

2. When the last color used is different from the current color, then we should compare it with dp[i - 1][j - 1][l] + cost[i][k] or dp[i - 1][j - 1][l] for all 1 ≤ l ≤ m except when l is equal to the current color, by similar reasoning.

If the current tree is uncolored, we loop through all the m possible colors to color it.

Starts from here ==> Naively implementing this dp will give an O(nkm2), which is sufficient to pass for this problem. However, it is possible to optimize it into O(nkm) by avoiding iterating through all colors when considering the last color used and store two global minimums. See the code for more the details.

Thanks in advance :(

Hi,

There is no editorial for problem 734C ==> http://mirror.codeforces.com/problemset/problem/734/C

Please give me some hint.

Thanks in advance :(

Hi can anyone tell any dp approach to this?

Problem link==> http://mirror.codeforces.com/contest/1151/problem/B

I can think of a O(n*m*2^10) dp But it will not pass.

Thanks in advance.

Hi I wrote top-down dp for this problem but my code gets TLE for test case 6 I must change it to bottom-up or there is a trick to don't get TLE?

My code ==> https://mirror.codeforces.com/contest/366/submission/56265597

Problem Link ==> https://mirror.codeforces.com/contest/366/problem/C

Any type of help is appreciated. Thanks in advance.

Hi, I cant get this problem from editorial.

Please Help ==> https://mirror.codeforces.com/problemset/problem/687/C

Thanks in advance.

Hi,

I get WA on test case 23

Problem Link ==> https://mirror.codeforces.com/problemset/problem/73/C

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e2+5;

string s;
long long k,change;
long long dp[MAXN][27][MAXN];

map<char,map<char,long long> > adjList;

long long Max(long long i,long long prev,long long left){
    if(i==s.size()) return 0;

    if(dp[i][prev][left]!=-1) return dp[i][prev][left];

    long long res=Max(i+1,(int)s[i],left) + adjList[prev][s[i]];

    if(left!=0){
        for(int j=97;j<=122;++j){
            char now = (char)(j);

            if(now==s[i]) continue;

            long long ind = Max(i+1,j,left-1) + adjList[prev][now];

            res = max(res,ind);

        }

    }
    dp[i][prev][left] = res;

    return dp[i][prev][left];
}

int main()
{
    for(long long i=0;i<=100;++i){
        for(long long j=0;j<=26;++j){
            for(long long f=0;f<=100;++f) dp[i][j][f] = -1;
        }
    }
    cin >> s;
    cin >> k >> change;
    for(long long i=0;i<change;++i){
        char a,b;long long c;cin >> a >> b >> c;
        adjList[a][b]=c;
    }
    cout << 1ll * Max(0,'?',k);
}

Thanks in advance:)

Hi,

Problem ==> http://mirror.codeforces.com/problemset/problem/1084/C

My solution gets WA in test case 10 and I think it because overflow but I can't see any overflow problem.

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9+7;

int MOD(int x){
    return ((x%INF)+INF)%INF;
}

int main()
{
    string n;cin >> n;
    string s;
    for(int i=0;i<n.size();++i){
        if(n[i]=='a' || n[i]=='b') s+=n[i];
    }
    //Get number of all of the contigiuos 'a's
    vector<int> ans;
    int cnt = 0;
    for(int i=0;i<s.size();++i){
        if(s[i]=='a') ++cnt;
        else{
            ans.push_back(cnt);cnt=0;
        }
    }ans.push_back(cnt);
    //Calculate the answer
    long long res=1;
    for(auto &i : ans){
        res = MOD(MOD(res) * MOD(i+1));
    }cout << res-1;
}

Hi,

I have seen this solution but I don't know how this works?

Question Link ==> https://mirror.codeforces.com/problemset/problem/859/C

Solution Link ==> 30390934

Thanks in Advance!

Hi, I just wanted to know what is wrong with my recurrence for this question?

problem link ==> https://mirror.codeforces.com/contest/678/problem/E

my recurrence==>

dp[mask] ==> The probability that the sith number one will win if anyone that is marked in the mask zero is dead and anyone that is alive are marked 1.

so we only go through the mask and if the i-th one is 1 then res+= dp[mask&(1<<j)] and at the end we do res/(Count of the soldiers that are not dead).

I know its completely wrong but I don't know why?

and also please give me a correct recurrence and idea.

Thanks in advance :(

Hi, I have used the same logic as editorial in problem 5C but my code gets the wrong answer. https://mirror.codeforces.com/contest/5/problem/C

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;
int dp[MAXN];

int main()
{
    string str;cin >> str;
    stack<int> s;int maxs=0,su0;
    for(int i=0;i<str.size();++i){
        if(str[i]=='('){
            s.push(i);dp[i]=-1;
        }else{
            if(s.empty()) dp[i]=-1;
            else{
                int top = s.top();int res = i-top+1;
                if(top!=0 && str[top-1]==')' && dp[top-1]!=-1) res += dp[top-1];
                dp[i]=res;maxs=max(maxs,dp[i]);
            }
        }
    }cout << maxs;
}

Hi, I have written this code and i am using dp for problem 553 A.What is wrong with my idea and code?

Question Link==>https://mirror.codeforces.com/contest/553/problem/A

My Submission==>55667272

Hi, In this question I posted my code by it seems that it gets overflow at some point of my code.

But I'm getting %MOD every time I want to subtract or sum things.

Problem link ==> https://mirror.codeforces.com/problemset/problem/474/D.

My Submission==> 55651145

This is my code for 611C problem on code forces

And this is my code but i dont know why it is wrong?

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3;
char graph[MAXN][MAXN];
int vertic[MAXN][MAXN],hort[MAXN][MAXN];

int main()
{
    int row,col;cin >> row >> col;
    for(int i=0;i<row;++i){
        for(int j=0;j<col;++j){
            cin >> graph[i][j];
        }
    }
    // Now we precompute all of them
    vertic[0][0]=0;
    for(int i=1;i<row;++i){
        vertic[0][i] = vertic[0][i-1];
        if(graph[0][i] == graph[0][i-1] && graph[0][i]=='.') ++vertic[0][i];
    }
    for(int i=1;i<col;++i){
        hort[i][0] = hort[i-1][0];
        if(graph[i][0] == graph[i-1][0] && graph[i][0]=='.') ++hort[i][0];
    }
    for(int i=1;i<row;++i){
        for(int j=1;j<col;++j){
            vertic[i][j] = vertic[i-1][j] + vertic[i][j-1] - vertic[i-1][j-1] + (graph[i][j-1]=='.' && graph[i][j]=='.');
            hort[i][j] = hort[i-1][j] + hort[i][j-1] - hort[i-1][j-1] + (graph[i-1][j] =='.' && graph[i][j]=='.');
        }
    }
    int q;cin >> q;
    for(int i=0;i<q;++i){
        int r1,c1,r2,c2;cin >> r1 >> c1 >> r2 >> c2;--r1;--c1;--r2;--c2;
        int vecOne = vertic[r2][c2] - vertic[r2][c1] - vertic[r1][c2] + vertic[r1][c1];
        int horOne = hort[r2][c2] - hort[r2][c1] - hort[r1][c2] + hort[r1][c1];
        cout << vecOne + horOne << endl;
    }
}

Hi, I didn't get this problem from editorial. http://mirror.codeforces.com/contest/1172/problem/A Thanks in advance.

Hi, What is the best way to get the shortest path from vertex a to b in a weighted undirected graph?

I have done this but can we do better than O(|V|)?

map<int,list<pair<int,int> > > adjList;

void addEdge(int u,int v,int weight){
    adjList[u].pb(mp(v,weight));
    adjList[v].pb(mp(u,weight));
}

void FindShortestPath(int u,int v){
    int dp[n];
    dp[u]=0;
    map<int,bool> visited;
    queue<int> q;q.push(u);visited[u]=true;
    while(!q.empty()){
        int now = q.front();q.pop();
        for(auto neight : adjList[now]){
            dp[neight.first] = min(dp[neight.first],dp[now]+neight.second);
            if(!visited[neight.first]){
                q.push(neight.first);visited[neight.first]=true;
            }
        }
    }cout << dp[v];
}

I have written this code for problem 494A Div 1 Treasure Link==>https://mirror.codeforces.com/problemset/problem/494/A code==>55202990 My idea is that start from left and always have the differences between '(' and ')' (How many '(' with no ')' match we have ==> name this variable l)

and then every time we get to an '#' we get the numbers of continuous ')' after that '#' until we face a '('. then the answer for that '#' is cnt(number of continuous ')' from '#') — l .

But my code gets WA for test case 10 what is the problem with my observation?

Hi guys, This is the code for binary search on real and float numbers

#include<bits/stdc++.h>
using namespace std;

//We want to find an element which a<0.0000001

const float target = 0.0000001;

int main()
{
    float l=0.00000000,r=100000.00000000;
    cout << l << " " << r;
    while((r-l)>0.0000000001){
        float mid = (float)((l+r)/2);
        cout << mid << endl;
        if(mid>target) r=mid;
        else l=mid;
    }cout << l;
}

But it will stop when it reaches 10 to power -5 what can I do to make it go until 10 to power -18?

Hi this is my submission https://mirror.codeforces.com/contest/538/submission/55094041 code for 538C but it gets WA for test case 22. Are there any points that I have not mentioned in my code? Thanks in advance.

Hi In test case 22 of problem 538 1000000 1 1000000 1000000 In my opinion, the answer is 1000000 but the system says 1900000. I think we can go every day 1 and at the 1000000 we get to the top but we have finished and the maximum is 1000000. I think I have not got some part of the question. https://mirror.codeforces.com/problemset/problem/538/C

my submission:55076191

Hi I have a predictor function and I want to find the last false element in my array that is not true for that element And I think the correct invariant for this one is my p(a[l]) is always false and p(a[r]) is always true so at the end l is my result index.

And this is my code==>

int l=-1,r=n-1; // First index in my array is 0 and last is n-1

while((r-l)>1){

int mid= l+(r-l)/2;

  if(p(a[mid]){

      r=m; // R now is true and invariation holds


  else l=m; // L is now false and invariation holds

}

cout << l; // Now l is the last false element because r is true and r-l==1

But my code doesn't return the true result in a lot of questions that I have solved in binary search but In the first, I have set an invariant and I think it must be true because I have proved it by invariant.