Input: a sequence <A_1, A_2, ..., A_n> of integers and an integer X.

Output: true if there is a strictly increasing subsequence of length X in sequence A, false otherwise.

Is there an O(n) algorithm for this problem ?

I was solving the problem: coin combination II from CSES. https://cses.fi/problemset/task/1636/

My solution leads to TLE.

#include <bits/stdc++.h> 
using namespace std; 
 
 
int 
main() {
 
    int mod = 1e9+7;
	int n, x; 
    cin>>n>>x; 
    vector<int> c(n);
    for (int &a : c) cin >> a;
 
    vector<vector<int>> dp(x+1,vector<int>(n+1,0));
    dp[0][0] = 1;
    for (int i = 0; i <= x; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i][j-1]; 
            int up = i - c[j-1]; 
            if (up >= 0)
            {
                (dp[i][j] += dp[up][j]) %= mod; 
            }
        }
    }
    cout << dp[x][n] << endl;
}

But solution in this editorial leads to AC..

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

int main() {
  int mod = 1e9+7;
  int n, target;
  cin >> n >> target;
  vector<int> x(n);
  for (int&v : x) cin >> v;

  vector<vector<int>> dp(n+1,vector<int>(target+1,0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= target; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-x[i-1];
      if (left >= 0) {
	(dp[i][j] += dp[i][left]) %= mod;
      }
    }
  }
  cout << dp[n][target] << endl;
}

The only difference I see is the why the DP table is set.. and consequently the way in which we compute it.

in my solution, dp[i][j] => number of ways to make sum i using first j coins.

in editorial solution, dp[i][j] => number of ways to make sum j using first i coins.

but, the number of iterations is exactly the same..

any explanations ?

thanks

Hi Codeforces,

The issue is that , in my opinion, Codeforces editorials are often not-beginner-friendly and sometimes very disappointing.

Please don't misunderstand me. I appreciate all the effort made by all the amazing people who make contests but

I think people can enjoy and benefit from Codeforces rounds much more if some changes are made.

My suggestion is to impose a specific format/template/rules on editorials that guarantees a min quality.

Given the effort needed to conduct contests, making small additions to editorials are almost effortless but they will yield a huge benefit for a big group of contestants, I think.

My assumption is that a good editorial should help people improve their problem-solving skills and related-knowledge. not just some annoying final task of contest making that we should do it ASAP.

So consider the following format:

For each problem,

• State prerequisites, I know about tags and that a problem may have a lot of solutions but this will still be useful in a lot of cases since tags are not really specific.

• Provide hints, this is incredibly useful for me and I assume for most of people same my level

• DON'T DESCRIBE IT FROM YOUR PERSPECTIVE. a lot of problem setters are just very good for the very majority of contestants. so please, EXPLAIN the solution, not describe it. This criteria can be test by cyan or green volunteers.

• The description of a solution should be like a story. the story of finding the solution. So, describe the process, at least one path, to the solution. This helps people learn how to think about the problem. Mention names of any problem-solving techniques used.

• Provide clear code with comments when needed.

• Optional: put a good comic after each problem.

As you can see, all these changes do not really require considerable time or effort. and with volunteers, no extra time is needed at all.

What do you think about all this? How does your ideal editorial looks like ? Also you can mention examples of Codeforces editorial your like!

Thanks for reading

Hi Codeforces,

A lot of posts have an interesting comment section. I usually need to revisit the post and its comment section several times. The issue is I just hate reading though all not-useful not-funny comments over and over again. If there is a way to hide comments you don't like, I think a lot of people will like it.

I don't know the effort needed for this change but idea is simple, Just an extra option for each comment to hide it when needed.

Thank you

I know how to solve the following variation;

Given list of coins c[1], c[2], ..., c[n], no 2 coins are same, and a target sum. Count number of ways to make the sum using the given coins ?

When

• There is 1 unit of each coin

• There is infinite supply of each coin.

I wonder what if there is a specific amount for each type of coin. so I am given the list of types of coins and the list a[1]...a[n] such that a[i] is the number of coins allowed of type c[i].

Can we solve it using DP ?

If yes, is the solution similar to the solution of the classical problem ? appreciate if you describe the whole solution.

If no, how to solve it? at least, what topics or techniques required?

Also, I would like to know generally how one prove that DP cannot solve some problem, if possible ?

Thanks for reading

Given integers n and k such that

0 < n <= 10^6

0 < k <= 10^3

and a string S of length n.

Find any substring of length k in S with maximum number of occurrences. I don't care about the obvious complete search solution. Also, no need for complete solution. just some hints. what topic to look for ?etc.

example

n=13 k=3

abcabcabcabcd

ans is "abc" repeated 4 times.

Recently, I use the following code a lot while solving graph problems with multiple test cases.

#include <bits/stdc++.h>
using namespace std; 
struct problem {
    // ... 
    void init() {}
    void solve() {}
};
int main () {
    int tc; 
    cin >> tc; 
    while (tc--) {
        problem p; 
        p.init(); 
        p.solve(); 
    }
}

I also use struct to represent graphs for example. It helps me organize my thoughts while coding. also I don't have to worry about what data to initialize before each test case. The problem is:

1- I don't know exactly what the code does. For example, will memory allocated at the beginning of a test case be automatically deallocated at the end of the test case? if not, can it cause TLE ?

2- In what situations may this way of coding cause problems ? and generally should I keep doing this?

Thanks

Given n and k where

0 <= n <= 10^5 and

1 <= k <= min(n, 10^5) and k is even

A nice string of length n is a binary string such that for all substrings of length k, number of 1s equal number of 0s.

let c_i equal number of 1s in the i_th valid string — (k/2)

Compute summation ( 2 ^ c_i ) for all nice strings, modulo 1000000007.

example n=6, k=4

one nice string is 001100 -> c_i = 2 — 2 = 0 -> 2^c_i = 1

another nice string is 101010 -> c_i = number of 1s — k/2 = 3 — 2 = 1 -> 2^c_i = 2

yet another example is 110011 -> c_i = number of 1s — k/2 = 4 — 2 = 2 -> 2^c_i = 4

010101-> 1

101010 -> 1

011001-> 1

100110 > 1

ans = (1+2+4+1+1+1+1) % 1000000007 = 11

https://mirror.codeforces.com/contest/234/problem/G

This problem is the type of problem where I know everything needed but I still can't solve it. I always learn a lot from such problems

I am not interested in a solution, I know it, but how to approach the problem and reach a solution. How to think about it? What should have hinted me to consider using what was needed to solve it ?

I have two solutions first, second for this problem You probably don't have to read all of this. The two solutions are identical except for the following:

I got wrong answer in one case: when I invoke function PLAY() and use cout like this

cout << "Impossible.\n";

but when I use cout but not call PLAY() or use printf(), answer is accepted.

void PLAY()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
}

Any explanations ?