№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

Разбор

Решение (Vovuh, O(n + m))

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<int> cnt(m + 2);
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		++cnt[l];
		--cnt[r + 1];
	}
	for (int i = 1; i <= m; ++i)
		cnt[i] += cnt[i - 1];
	
	vector<int> ans;
	for (int i = 1; i <= m; ++i) {
		if (cnt[i] == 0)
			ans.push_back(i);
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it << " ";
	cout << endl;
	
	return 0;
}

Решение (Vovuh, O(n * m))

n, m = map(int, input().split())
seg = [list(map(int, input().split())) for i in range(n)]
def bad(x):
	for i in range(n):
		if (seg[i][0] <= x and x <= seg[i][1]): return False
	return True
ans = list(filter(bad, [i for i in range(1, m + 1)]))
print(len(ans))
print(' '.join([str(x) for x in ans]))

1015B - Obtaining the String

Разбор

Решение (Vovuh)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s, t;
	cin >> n >> s >> t;
	
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		if (s[i] == t[i]) continue;
		int pos = -1;
		for (int j = i + 1; j < n; ++j) {
			if (s[j] == t[i]) {
			        pos = j;
			        break;
			}
		}
		if (pos == -1) {
			cout << -1 << endl;
			return 0;
		}
		for (int j = pos - 1; j >= i; --j) {
			swap(s[j], s[j + 1]);
			ans.push_back(j);
		}
	}
	
	assert(s == t);
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

1015C - Songs Compression

Разбор

Решение (Vovuh)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a(n);
	long long sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].first >> a[i].second;
		sum += a[i].first;
	}
	
	sort(a.begin(), a.end(), [&](pair<int, int> a, pair<int, int> b) { return a.first - a.second > b.first - b.second; });
	
	for (int i = 0; i < n; ++i) {
		if (sum <= m) {
			cout << i << endl;
			return 0;
		}
		sum -= a[i].first - a[i].second;
	}
	
	if (sum <= m)
		cout << n << endl;
	else
		cout << -1 << endl;
	
	return 0;
}

1015D - Walking Between Houses

Разбор

Решение (BledDest)

def step(cur, x):
    if(cur - x > 0):
        return cur - x
    else:
        return cur + x



n, k, s = map(int, input().split())
cur = 1

if(k > s or k * (n - 1) < s):
    print('NO')
else:
    print('YES')
    while(k > 0):
        l = min(n - 1, s - (k - 1))
        cur = step(cur, l)
        print(cur, end = ' ')
        s -= l
        k -= 1

1015E1 - Stars Drawing (Easy Edition)

Разбор

Решение (MikeMirzayanov, O(n^3))

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

const int dx[] = {1, 0, -1,  0};
const int dy[] = {0, 1,  0, -1};
const int N = 1001;

int n, m;
vector<string> f;
int d[N][N][4];
int r[N][N], a[N][N], b[N][N];

int getd(int i, int j, int k) {
    int dxk = dx[k];
    int dyk = dy[k];
    int result = 0;
    while (i >= 0 && i < n && j >= 0 && j < m && f[i][j] == '*')
        result++, i += dxk, j += dyk;
    return result;
}

int main() {
    cin >> n >> m;
    f = vector<string>(n);
    forn(i, n)
        cin >> f[i];
    
    memset(d, -1, sizeof(d));
    int result = 0;
    for (int i = 1; i + 1 < n; i++)
        for (int j = 1; j + 1 < m; j++)
            if (f[i][j] == '*') {
                bool around = true;
                forn(k, 4)
                    around = around && (f[i + dx[k]][j + dy[k]] == '*');
                if (around) {
                    r[i][j] = INT_MAX;
                    forn(k, 4)
                        r[i][j] = min(r[i][j], getd(i, j, k) - 1);
                    result++;
                    a[i][j - r[i][j]] = max(a[i][j - r[i][j]], 2 * r[i][j] + 1);
                    b[i - r[i][j]][j] = max(b[i - r[i][j]][j], 2 * r[i][j] + 1);
                }
            }

    vector<string> g(n, string(m, '.'));
    forn(i, n) {
        int v = 0;
        forn(j, m) {
            v = max(v - 1, a[i][j]);
            if (v > 0)
                g[i][j] = '*';
        }
    }
    forn(j, m) {
        int v = 0;
        forn(i, n) {
            v = max(v - 1, b[i][j]);
            if (v > 0)
                g[i][j] = '*';
        }
    }
    
    if (f == g) {
        cout << result << endl;
        forn(i, n)
            forn(j, m)
                if (r[i][j] > 0)
                    cout << i + 1 << " " << j + 1 << " " << r[i][j] << endl;
    } else
        cout << -1 << endl;
}

1015E2 - Stars Drawing (Hard Edition)

Разбор

Решение (Vovuh, O(n^2))

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<string> s;

vector<string> draw(const vector<pair<pair<int, int>, int>> &r) {
	vector<string> f(n, string(m, '.'));
	vector<vector<int>> h(n, vector<int>(m));
	vector<vector<int>> v(n, vector<int>(m));
	for (auto it : r) {
		int x = it.first.first;
		int y = it.first.second;
		int len = it.second;
		++v[x - len][y];
		if (x + len + 1 < n)
			--v[x + len + 1][y];
		++h[x][y - len];
		if (y + len + 1 < m)
			--h[x][y + len + 1];	
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0) v[i][j] += v[i - 1][j];
			if (j > 0) h[i][j] += h[i][j - 1];
			if (v[i][j] > 0 || h[i][j] > 0)
				f[i][j] = '*';
		}
	}
	return f;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	s = vector<string>(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	
	vector<vector<int>> l(n, vector<int>(m));
	vector<vector<int>> r(n, vector<int>(m));
	vector<vector<int>> u(n, vector<int>(m));
	vector<vector<int>> d(n, vector<int>(m));
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0) {
				if (s[i][j] != '.')
					u[i][j] = u[i - 1][j] + 1;
			} else {
				u[i][j] = s[i][j] != '.';
			}
			if (j > 0) {
				if (s[i][j] != '.')
					l[i][j] = l[i][j - 1] + 1;
			} else {
				l[i][j] = s[i][j] != '.';
			}
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int j = m - 1; j >= 0; --j) {
			if (i < n - 1) {
				if (s[i][j] != '.')
					d[i][j] = d[i + 1][j] + 1;
			} else {
				d[i][j] = s[i][j] != '.';
			}
			if (j < m - 1) {
				if (s[i][j] != '.')
					r[i][j] = r[i][j + 1] + 1;
			} else {
				r[i][j] = s[i][j] != '.';
			}
		}
	}
	
	vector<pair<pair<int, int>, int>> ans;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (s[i][j] == '*') {
				int len = min(min(u[i][j], l[i][j]), min(d[i][j], r[i][j])) - 1;
				if (len != 0) {
					ans.push_back(make_pair(make_pair(i, j), len));
				}
			}
		}
	}
	
	if (draw(ans) != s) {
		cout << -1 << endl;
	} else {
		cout << ans.size() << endl;
		for (auto it : ans) {
			cout << it.first.first + 1 << " " << it.first.second + 1 << " " << it.second << endl; 
		}
	}
	
	return 0;
}

1015F - Bracket Substring

Разбор

Решение (Vovuh)

#include <bits/stdc++.h>

using namespace std;

const int N = 203;
const int MOD = 1e9 + 7;

int n, ssz;
string s;
int len[N][2];
int dp[N][N][N][2];

int calc(const string &t) {
	int tsz = t.size();
	for (int i = tsz; i > 0; --i) {
		if (s.substr(0, i) == t.substr(tsz - i, i))
			return i;
	}
	return 0;
}

void add(int &a, int b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> s;
	ssz = s.size();
	
	if (s[0] == '(')
		len[0][0] = 1;
	else
		len[0][1] = 1;
	
	string pref;
	for (int i = 0; i < ssz; ++i) {
		pref += s[i];
		pref += '(';
		len[i + 1][0] = calc(pref);
		pref.pop_back();
		pref += ')';
		len[i + 1][1] = calc(pref);
		pref.pop_back();
	}
	
	dp[0][0][0][0] = 1;
	for (int i = 0; i < 2 * n; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int pos = 0; pos <= ssz; ++pos) {
				for (int f = 0; f < 2; ++f) {
					if (dp[i][j][pos][f] == 0) continue;
					if (j + 1 <= n)
						add(dp[i + 1][j + 1][len[pos][0]][f | (len[pos][0] == ssz)], dp[i][j][pos][f]);
					if (j > 0)
						add(dp[i + 1][j - 1][len[pos][1]][f | (len[pos][1] == ssz)], dp[i][j][pos][f]);
				}
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i <= ssz; ++i)
		add(ans, dp[2 * n][0][i][1]);
		
	cout << ans << endl;
	
	return 0;
}

#include "bits/stdc++.h" using namespace std; typedef long long ll; int main() { int ans = 0; for(int i = 1 ; i <= 1000 ; ++ i) { for(int j = 1 ; j <= 1000 ; ++ j) { ans += min(min(i, j), min(1000 - i, 1000 - j)); } } printf("%d\n", ans); }

Комментарии (64)

Показать архивные | Написать комментарий?

brdy

6 лет назад, # |

← Rev. 2 →

Thanks for the editorial.

I have one question about problem F dp recurrence, would the recurrence stated above be able to differentiate

(seq)seqseq

from

seq(seq)seq

given seq is a valid bracket sequence, and the substring you are looking for.

obviously in the two solutions the position, balance, and boolean parameter will be the same. Also the prefix of length K should be the same too.

So I am asking, how will this dp handle situation such as this?

UPD:

Ok so after some thinking I realized that the dp state does not have to have a unique sequence, the only thing that has to be unique is the value it returns given a set of parameters. So seq(seq)seq and (seq)seqseq should be able to "reach the end" equal amount of ways, but I'm no so sure they can be made an equal amount of ways.

→ Ответить

peach

6 лет назад, # ^ |

In my DP I do something special the first time the full pattern is encountered: I call another DP that doesn't track the pattern at all and simply counts the number of valid bracket sequences with remaining characters and balance number.

ReallyNewBie

There is a problem that we can't hack the O(N^3) E2 solution. Because that our test cases is bigger than the limit->256 KB, but it can be a possible input.

Vshining

← Rev. 3 →

Use a generator instead.
P.S. My solution is plain simple O(N³), and with N = M = 1000 test (all stars), it passes with 2430 ms. Fairly wide gap (for 3000 ms constraint), so I don't expect a lot of hacks with that test.

I realized there is some people which use O(N^3) and can't pass the all star case. Thanks.

Mustang98

+10

You can submit the code that generates test case of any size you want. See "generated input" tab in a hack window.

Thanks.

nekko

maybe it's O(n^2 sigma{i,j} min(i,j,n-i,m-j))

i write a program like this

it print "cnt = 166666500, time = 1.666665"

and my program used 1.30s pass the all star without 4 corner stars data

I_hate_I_love_geom

Почему бы не хранить в 1015С вектор разностей a[i]-b[i] вместо вектора пар? Тогда будет легче сортировать

Fighter.human

IN question E2 if it would have asked to find the minimum possible stars too and if many multiple answers exist print any. Then how could we solve it any idea anyone?

god1048

When will the rating be published ?

maybe after system tests

nickk2002

why does is take so long? I mean there are only like 5 peoples in queue right now

but when after judge over some solutions, another solutions will add in the queue

gokhalesushant65

FOR problem 'F' , can anyone explain me in simple words(possibly with an example) the dp strategy? I mean dp(i,j,k,l)part. Not able to understand tutorial.

Also, not able to understand the recurrance part.

Naumtsev

Спасибо за простое решение Dшки, смотря чужие решения, осознаёшь что эта задача была "напишите кучу If'ов".

vikalp14

For the first problem

Can someone help with these:

How is the prefix sum calculation approach relevant to this problem (I fail to see) Why take size of cnt as m+2 Like why do --cnt[r+1] in the first for loop and why cnt[i]+=cnt[i-1] in the second for loop

Thanks!

Tosic

This is the so-called "event scheduling" process. Basically each segment has a beginning and an ending index (l and r). If you were to add all points from l to r manually, you would get an O(nm) solution. However, notice that you can only add one to position l, and when you traverse the array once again, and use prefix sums, pref[i] will >= 1 if there is a point on position i. However, since there is no point in r+1, nor is there in any indices to come, we put -1 at that position so the prefix sum would become 0.

Adding multiple segments allows the prefix sums to be equal to the number of segments covering point i at position pref[i]. Try some examples on paper for better understanding.
Here is an example (l=1, r=2, l=0, r=5):
The event schedule array looks like this:
{1, 1, 0, - 1, 0, 0, - 1}
And the pref array looks like this:
{1, 2, 2, 1, 1, 1, 0}
(the arrays are 0-indexed and pref[i] really shows the number of points on position i).

GrainOfSand

I found another way to do D which is also really simple 41070174

Did anyone else find another valid way?

lazyneuron

Actually, I did the same thing.

Mindjolt

Mine might be similar to yours, my distance was ceil(dist / k), and then I reduced my dist by that amount, and reduced k by 1. I can't prove why it's correct though.

For D, what I did was s = (s / k + 1) * (s % k) + (k — s % k) * (s / k) In other words took s / k + 1 steps back and forth s % k times and remaining steps were s / k long.

sonu628

problem E — dp+difference array, that was a nice problem (Y)

For E I have a shameful solution in O(nmlog(nm)). I keep prefix sums for how many stars I've seen after me, but I don't keep track of contiguous subsequences or anything. Instead, for each point (i, j) as middle of star, I binary search for the maximum length of the star centered there by using prefix sums and checking that sum in all four directions is at least my binary search value (it obviously cannot be more). Then I use segment trees to mark that a point is included in some star. I store all my stars in a vector, but before printing them out I query for each point on the grid that is * I check if it is involved in a star (either by row or column) using segment tree point max query (I am so eager to add log factors). If all the *'s belong to stars I print out all the stars I found in the binary searches. This passes the big data in 1715 ms.

its_ulure

Why does this soln gives a TLE https://codeforces.me/contest/1015/submission/41034740

test616.cpp

Because of Quicksort...

https://codeforces.me/blog/entry/7108

https://codeforces.me/contest/1015/submission/41093401

Ah thanks @test616.cpp, I understood . But my main concern is doing random shuffling during a online contest may take some extra time penalty and it's too often that most of the Java users use Arrays.sort() to sort an array and after getting a TLE verdict we may realise that we need to shuffle the array.

blue__legend

I am not able to understand the dp part in Problem F can anyone elaborate it more. I am also not able to understand the need of finding the first Len dp.

vovuh

The main idea is if you obtain some prefix of s and trying to add some character which is not equal to the next character of s, your target is to obtain the maximum prefix of s with the last character you add. For example, if s = ((()(())((), you obtained the first six characters ((()(( and you have to add the character (, you want to get the prefix of s of maximum length (because you want to obtain the string s as soon as possible, right?), your string will be looks like ((()((( and the maximum prefix of s corresponding to the suffix of this string will be (((. The first dp is needed to make transitions in the second dp faster.

And the second dp just calculates the number of prefixes of regular bracket sequences with the last k characters equals to the prefix of s of length k.

tatya_bichu

As it is given that s must be a substring, then we can calculate how many ')' or '(' are needed to make it a regular string. For example in '( ) ) ) ( )' , we need two '(' to the left of s ,hence now we have to place 2 (4-2=2) more brackets(after balancing s) , those two can be(bold brackets) : ( ) ( ( ( ) ) ) ( ) or ( ( ) ( ( ) ) ) ( )
or ( ( ( ) ( ) ) ) ( ) or ( ( ( ) ) ) ( ) ( ) or ( ( ( ( ) ) ) ( ) ) so there are five places to put one pair in the string, now we can do that for any number of pairs, which is the catlan number, and we can put these in any gaps (except in s). Is this a correct approach?

Well... I don't sure you can solve this problem this way, because it is too hard to consider all valid placements of brackets for a random bracket string exactly once. Because of this we do dynamic programming

for each gap we can have dp state such that if there are n gaps and x is the number of pairs that has been used then we can calculate dp[n][x] from dp[n-1][x],dp[n-1][x-1],dp[n-1][x-2]... and multiplying their respective catlan numbers . to speed up this.

kanishk779

4 года назад, # ^ |

tatya_bichu No it cannot be solved by this method, Initially i was also thinking on the same lines. But the problem is, we are trying to make the sequence before the given sequence regular and same for the sequence after the given sequence. I mean, if we create a sequence like seq1 given seq2 than seq1 will handle the closed brackets and be regular apart from this. and seq2 will handle open brackets and be regular apart from this. But It need not be the case.

Thanks Vovuh. I understood the concept except the factor 'j' in dp(i,j,k,l).

COuld you please explain what does 'balance' exactly mean?

In some sense the balance means the number of the opening brackets ( which are weren't closed on the current prefix. I.e. for empty prefix the balance is zero always. If you will add the opening bracket, the balance will increase by one. If you will add the closing bracket, the balance will decrease by 1. But there is one more thing. In any moment of time the balance should be greater than or equal to zero. It is because you should handle the case when the number of closing brackets is getting greater than the number of opening brackets. Btw you can try to understand it by yourself with this definition of balance. I hope it helps!

rotavirus

Что означает амперсанд в квадратных скобках?

Что все параметры в лямбда-функцию передаются по ссылке.

TouchMe

Problem E "If it is impossible to draw the given grid using stars only, print "-1"." So all dots case's answer is 0 instead of -1?

Yes

coffea

In problem E how the output is -1 for input 5 5 .*... **.. .... .*... .....

Someone, please explain.

Because you can't draw this grid with stars.

314rate

I also have posted this in the Announcement:

Hello, in problem F, why does this solution not work :

read n

read sring

get delta of string : delta"(("=2 ; delta")"=-1 like if you have "(" add 1 and if you have ")"

substract 1

get the minimum over all deltas :

code :

int del=0;

int mi=del;

for(int j=0;j<sz;j++)

{

if(a[j]=='(')

    del++;

else

    del--;

mi=min(mi,del);

}

than just fix where you want to fit it in

like [ poz, poz+sz-1 ]

I am giving you the code

http://codeforces.me/contest/1015/submission/41118240

thanks in advance

natofp

← Rev. 4 →

Hi wanna ask how this code gets TLE? It is E2 solution with about lets say 10 nested loops which do about 10^6 operations ( each at most) , so how does not it pass in 3 seconds? Pretty clear code below: http://codeforces.me/contest/1015/submission/41120679 I'd be very thankful for any help.

Edit: Fixed. Endl operation took super long.

Hd7

Why it 's wrong answer on test 26, i didn't know where is wrong? Please help me! Thanks! http://codeforces.me/contest/1015/submission/41127014

Jakube

It says it in the error message. You printed 1000000001, but there are only 1000000000 houses.

I printed the answer by using freopen and Ctrl+F (find) 1000000001 but not exist in my answer.

Thank you! I fixed my problem.

hat

In the F tutorial: which equals to the suffix of the prefix of s of length len

I think this len should be i?

Sorry for poor English.

Yes, you are right. Thank you, fixed

misaka27149

The std of E2 is TLE

tuananh2209

In Stars Drawing (Hard Edition) Please explain why? Let's increase h[i,j-len] by one and decrease h[i,j+len] by one. Thanks

sguu

I am not getting the editorial for F.can somone explain me What is len[i][j]

Plzz explain!!

Let leni,j will denote the maximum length of the prefix of s which equals to the suffix of the prefix of s of length i with the additional character '(' if j=0 and ')' otherwise. In other words, leni,j

rr_

Do you know how does Knuth-Morris-Pratt algorithm work (especially "Partial match" table) and why does it work? If not, start with that. It might not be easy, I know, but there are multiple resource on this in the Internet and I won't be able to explain it better than it was already done in some articles / videos. Afterwards this information should be pretty straightforward as it is the same concept.

ivan100sic

In problem F you can eliminate the flag l by simply not changing the value of k once k hits |s|, this is how you would construct a Deterministic Finite Automaton which checks whether some string s appears at least once in the input string — you simply make the outgoing edges at vertex |s| go back to |s|. The code is also somewhat simpler.

chinmay0906

Bad time limit of problem E2, my O(N^3) solution easily passed in TL.

oj-k

5 лет назад, # |

Why is this code giving tle? My approach is same as the one mentioned in the tutorial!! https://codeforces.me/contest/1015/submission/71619845

phantom654

5 лет назад, # ^ |

Mine also !! [https://codeforces.me/contest/1015/submission/74198722]

Did you find the error?

boogey_man

can anyone explain what this lines does in the code

ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout);

endif

It is for getting input from input.txt, which is a file that should be present in your current directory. You can paste the input there and your program will read input from this file. Same goes for the output.txt.

Legend_of_Azkaban

4 года назад, # |

Help... Why this F solution is wrong : https://codeforces.me/contest/1015/submission/95085826

Idea : Let's say our final string would be A where at least 1 substring of S is present. Fix the starting position of the substring S, X = current starting position of S, Y = current end of S. In our dp, if pos < X || pos > y, that means we can choose this position to be either "(" or ")", so we call function for both of them. When pos >= X && pos <= Y, we don't have a choice, we have fixed that length for S, so we call function according to what we have in S. For each possible X (starting position can be 0,1,2...) do a new dp, and increase our answer.

Mustafiz

2 года назад, # ^ |

idea is not correct. beacuse you count one string multiple time.

SyberCage

23 месяца назад, # |

@vovuh I am facing an issue with Problem F, my approach is quite same as in editorial. I made a dp[i[j][k][f]

where 'i' is the number of characters, I have placed till far and j shows the index of string s till which it is been place, k is the score of current bracket sequence "+1 for ( and -1 for )" and f shows whether string s is placed or not. So, my dp has following transitions: First I will put some ( and ) brackets and my j=0 and f=0 indicates that I haven't placed s till now. when f=1 it shows that currently I'm placing string s and my pointer j will increment in each step.

when j=len(s) f will become to 0 again

and i will not start placing s again if j=len(s)

in base case i will check whether j=len(s) and score=0

meanwhile if score<0 then i will return 0. Please look into it once. Thanks for your help. code for Problem_F

vcl

4 месяца назад, # |

problem F can be solved by kmp automaton

pinkkiuu

4 месяца назад, # ^ |

i am sure about that!!!! i confirm it ac

Блог пользователя vovuh

ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout);

endif