Codeforces Round #620 (Div. 2) Editorial

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Tutorial

Solution

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

int main()
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		cout << ((y - x) % (a + b) == 0 ? (y - x) / (a + b) : -1) << endl;
	}
}

1304B — Longest Palindrome

Tutorial

Solution

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

const int MAX_N = 100;
string s[MAX_N];

int main()
{
	set<string> dict;
	int n, m, i;
	cin >> n >> m;
	for (i = 0; i < n; i++)
	{
		cin >> s[i];
		dict.insert(s[i]);
	}
	vector<string> left, right;
	string mid;
	for (i = 0; i < n; i++)
	{
		string t = s[i];
		reverse(t.begin(), t.end());
		if (t == s[i])
			mid = t;
		else if (dict.find(t) != dict.end())
		{
			left.push_back(s[i]);
			right.push_back(t);
			dict.erase(s[i]);
			dict.erase(t);
		}
	}
	cout << left.size() * m * 2 + mid.size() << endl;
	for (string x : left)
		cout << x;
	cout << mid;
	reverse(right.begin(), right.end());
	for (string x : right)
		cout << x;
	cout << endl;
}

1304C — Air Conditioner

Tutorial

Solution

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

const int MAX_N = 100;

int t[MAX_N], lo[MAX_N], hi[MAX_N];

int main()
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n, m, i;
		cin >> n >> m;
		for (i = 0; i < n; i++)
			cin >> t[i] >> lo[i] >> hi[i];
		int prev = 0;
		int mn = m, mx = m;
		bool flag = true;
		for (i = 0; i < n; i++)
		{
			mx += t[i] - prev;
			mn -= t[i] - prev;
			if (mx < lo[i] || mn > hi[i])
			{
				flag = false;
				break;
			}
			mx = min(mx, hi[i]);
			mn = max(mn, lo[i]);
			prev = t[i];
		}
		if (flag)
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}

1304D — Shortest and Longest LIS

Tutorial

Solution

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

const int MAX_N = 200000;
int ans[MAX_N + 5];

int main()
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n, i, j;
		string s;
		cin >> n >> s;

		int num = n, last = 0;
		for (i = 0; i < n; i++)
		{
			if (i == n - 1 || s[i] == '>')
			{
				for (j = i; j >= last; j--)
					ans[j] = num--;
				last = i + 1;
			}
		}
		for (i = 0; i < n; i++)
			cout << ans[i] << (i == n - 1 ? '\n' : ' ');

		num = 1, last = 0;
		for (i = 0; i < n; i++)
		{
			if (i == n - 1 || s[i] == '<')
			{
				for (j = i; j >= last; j--)
					ans[j] = num++;
				last = i + 1;
			}
		}
		for (i = 0; i < n; i++)
			cout << ans[i] << (i == n - 1 ? '\n' : ' ');
	}
}

1304E — 1-Trees and Queries

Tutorial

Solution

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

const int MAX_N = 100000;
const int LIM = 17;
const int INF = (int)1e9 + 7;

vector<int> adj[MAX_N + 5];
int depth[MAX_N + 5];
int par[MAX_N + 5][LIM + 1];

void build(int cur, int p)
{
	int i;

	depth[cur] = depth[p] + 1;
	par[cur][0] = p;
	for (i = 1; i <= LIM; i++)
		par[cur][i] = par[par[cur][i - 1]][i - 1];

	for (int x : adj[cur])
		if (x != p)
			build(x, cur);
}

int lca_len(int a, int b)
{
	int i, len = 0;

	if (depth[a] > depth[b])
		swap(a, b);
	for (i = LIM; i >= 0; i--)
	{
		if (depth[par[b][i]] >= depth[a])
		{
			b = par[b][i];
			len += (1 << i);
		}
	}
	
	if (a == b)
		return len;
	for (i = LIM; i >= 0; i--)
	{
		if (par[a][i] != par[b][i])
		{
			a = par[a][i];
			b = par[b][i];
			len += (1 << (i + 1));
		}
	}
	return len + 2;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, q, i;
	cin >> n;
	
	for (i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	build(1, 0);

	cin >> q;
	while (q--)
	{
		int x, y, a, b, k;
		cin >> x >> y >> a >> b >> k;
		int without = lca_len(a, b);
		int with = min(lca_len(a, x) + lca_len(y, b), lca_len(a, y) + lca_len(x, b)) + 1;
		int ans = INF;
		if (without % 2 == k % 2)
			ans = without;
		if (with % 2 == k % 2)
			ans = min(ans, with);
		cout << (ans <= k ? "YES" : "NO") << '\n';
	}
}

1304F1 — Animal Observation (easy version)

Tutorial

Solution

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

const int MAX_N = 50;
const int MAX_M = 20000;
const int MAX_K = 20;

int animal[MAX_N + 5][MAX_M + 5];
int psum[MAX_N + 5][MAX_M + 5];
int lmax[MAX_N + 5][MAX_M + 5];
int rmax[MAX_N + 5][MAX_M + 5];
int dp[MAX_N + 5][MAX_M + 5];

inline int ps(int i, int j, int k)
{
	return psum[i][k] - psum[i][j - 1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j;

	int n, m, k;
	cin >> n >> m >> k;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			cin >> animal[i][j];
			psum[i][j] = psum[i][j - 1] + animal[i][j];
		}
	}

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m - k + 1; j++)
		{
			int p = ps(i, j, j + k - 1) + ps(i + 1, j, j + k - 1);
			if (i == 1)
			{
				dp[i][j] = p;
				continue;
			}
			int mx = 0;
			for (int x = max(1, j - k + 1); x <= min(m - k + 1, j + k - 1); x++)
				mx = max(mx, dp[i - 1][x] + p - ps(i, max(x, j), min(x + k - 1, j + k - 1)));
			dp[i][j] = mx;
			if (j > k)
				dp[i][j] = max(dp[i][j], lmax[i - 1][j - k] + p);
			if (j + k - 1 <= m - k)
				dp[i][j] = max(dp[i][j], rmax[i - 1][j + k] + p);
		}
		for (j = 1; j <= m - k + 1; j++)
			lmax[i][j] = max(lmax[i][j - 1], dp[i][j]);
		for (j = m - k + 1; j >= 1; j--)
			rmax[i][j] = max(rmax[i][j + 1], dp[i][j]);
	}

	cout << *max_element(dp[n] + 1, dp[n] + m + 1) << '\n';
}

1304F2 — Animal Observation (hard version)

Tutorial

Solution: O(nmlogm)

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

const int MAX_N = 50;
const int MAX_M = 20000;
const int MAX_K = 20;

int animal[MAX_N + 5][MAX_M + 5];
int psum[MAX_N + 5][MAX_M + 5];
int dp[MAX_N + 5][MAX_M + 5];
int t[MAX_M * 4], lazy[MAX_M * 4];

void update_lazy(int i, int lo, int hi)
{
	if (lazy[i])
	{
		t[i] += lazy[i];
		if (lo != hi)
		{
			lazy[i * 2] += lazy[i];
			lazy[i * 2 + 1] += lazy[i];
		}
		lazy[i] = 0;
	}
}

int update(int i, int lo, int hi, int l, int r, int val)
{
	update_lazy(i, lo, hi);
	if (lo > r || hi < l)
		return t[i];
	if (l <= lo && hi <= r)
	{
		t[i] += val;
		if (lo != hi)
		{
			lazy[i * 2] += val;
			lazy[i * 2 + 1] += val;
		}
		return t[i];
	}
	int mid = (lo + hi) / 2;
	return t[i] = max(update(i * 2, lo, mid, l, r, val), update(i * 2 + 1, mid + 1, hi, l, r, val));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j;

	int n, m, k;
	cin >> n >> m >> k;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			cin >> animal[i][j];
			psum[i][j] = psum[i][j - 1] + animal[i][j];
		}
	}

	int mm = m - k + 1;

	for (i = 1; i <= mm; i++)
		dp[1][i] = psum[1][i + k - 1] - psum[1][i - 1] + psum[2][i + k - 1] - psum[2][i - 1];
	for (i = 2; i <= n; i++)
	{
		memset(t, 0, sizeof t);
		memset(lazy, 0, sizeof lazy);
		for (j = 1; j <= mm; j++)
			update(1, 1, mm, j, j, dp[i - 1][j]);
		for (j = 1; j <= k; j++)
			update(1, 1, mm, 1, j, -animal[i][j]);
		for (j = 1; j <= mm; j++)
		{
			dp[i][j] = t[1] + psum[i][j + k - 1] - psum[i][j - 1] + psum[i + 1][j + k - 1] - psum[i + 1][j - 1];
			if (j != mm)
			{
				update(1, 1, mm, max(1, j - k + 1), j, animal[i][j]);
				update(1, 1, mm, j + 1, j + k, -animal[i][j + k]);
			}
		}
	}

	cout << *max_element(dp[n] + 1, dp[n] + mm + 1) << endl;
}

Solution: O(nm)

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

const int MAX_N = 50;
const int MAX_M = 20000;
const int MAX_K = 20;

int n, m, k;

inline int ps(vvi &p, int i, int s, int e)
{
	if (s < 1)
		return p[i][e];
	return p[i][e] - p[i][s - 1];
}

void calc_overlapped(vvi &ar, vvi &p, vvi &dp, int i)
{
	int j;
	deque<pii> dq;
	for (j = 1; j <= m - k + 1; j++)
	{
		int num = dp[i - 1][j] - ps(p, i, j, j + k - 1);
		if (dq.size() && dq.front().second <= j - k)
			dq.pop_front();
		while (dq.size() && dq.back().first + ps(p, i, dq.back().second, j - 1) <= num)
			dq.pop_back();
		dq.push_back({ num, j });
		dp[i][j] = dq.front().first + ps(p, i, dq.front().second, j - 1) + ps(p, i, j, j + k - 1) + ps(p, i + 1, j, j + k - 1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j;

	cin >> n >> m >> k;

	vvi init(n + 5, vi(m + 5, 0));
	vvi animal, animal_rev, psum, psum_rev, lmax, rmax, dp, dpl, dpr;
	animal = animal_rev = psum = psum_rev = lmax = rmax = dp = dpl = dpr = init;	

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			cin >> animal[i][j];
			psum[i][j] = psum[i][j - 1] + animal[i][j];
			animal_rev[i][m - j + 1] = animal[i][j];
		}
		for (j = 1; j <= m; j++)
			psum_rev[i][j] = psum_rev[i][j - 1] + animal_rev[i][j];
	}

	deque<pii> dq;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m - k + 1; j++)
		{
			if (j > k)
				dp[i][j] = lmax[i - 1][j - k];
			if (j <= m - k * 2 + 1)
				dp[i][j] = max(dp[i][j], rmax[i - 1][j + k]);
			dp[i][j] += ps(psum, i, j, j + k - 1) + ps(psum, i + 1, j, j + k - 1);
		}

		calc_overlapped(animal, psum, dpl, i);
		calc_overlapped(animal_rev, psum_rev, dpr, i);

		for (j = 1; j <= m - k + 1; j++)
		{
			dp[i][j] = max({ dp[i][j], dpl[i][j], dpr[i][m - j - k + 2] });
			dpl[i][j] = dpr[i][m - j - k + 2] = dp[i][j];
		}
			
		for (j = 1; j <= m - k + 1; j++)
			lmax[i][j] = max(lmax[i][j - 1], dp[i][j]);
		for (j = m - k + 1; j >= 1; j--)
			rmax[i][j] = max(rmax[i][j + 1], dp[i][j]);
	}

	cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
}

for(i=store.size()-1; i>=0; i--){ if(i<0 || i>=store.size()) { cout<<"OOH!: "<<i<<'\n'; break; } string temp1 = inp[store[i]]; reverse(temp1.begin(), temp1.end()); out.append(temp1); }

Comments (79)

Show archived | Write comment?

Kognition

5 years ago, # |

+19

Interesting, I was just talking to a friend a few days ago about how I've never seen max-queue used in a Codeforces problem. The solution for F2 is nice.

→ Reply

beacon_cwk

5 years ago, # ^ |

← Rev. 2 →

In fact,max-queue or min-queue is used in 372C.

dantrag

+283

✓ Nice problems

✓ Clear statements

✓ Fast editorial

Great effort mate, very nice contest!

blobugh

+21

✓ Strong pretests (Although some pretest passed code of B failed system test)

Yeah, I think it is generally true for many last contests where each test has many test cases.

MagicSpark

+14

In F,I accidently type int suf[51][20005] to suf[21][20005] and I got pretests passed...... So maybe pretests in F is not that strong.

djm03178

I assume it didn't cause problems in most cases because pre came right after suf generally, and when it was about to read something like suf[50][0] it usually pointed at one of the earlier indices of pre, which isn't used anymore.

SPyofgame

Thanks for the quick tutorial <3 Thanks for the contest <3 Have some good days problem setters <3

rupav

Editorial of B: Instead of "pick any one of them and put it in the middle.", pick the longest one.

+11

The length of the strings are equal, so you can just pick any of them.

ohh, I totally forgot that, my bad :)

ChinmaySama

I too did the thing for longest string XD

DomiKo

So I guess, that I found the best way to have good score in contest.

You should test the round, and the Power From MikeMirzayanov will come to you.

Thanks MikeMirzayanov

And thank you for the great contest. I really enjoyed problems.

cjj490168650

Can someone explain why this greedy method for problem D is correct? 71148664

(topological sort with heap/priority_queue)

xyf007

← Rev. 4 →

In fact, you even don't need a heap. Each string like "<>>" "<>>>" can only provide one in the LIS.

I_will_not_quit

You can prove the correctness of topo-sort method by observing that the output (order of numbers) you get is the same as the output of editorialist's algo.

EMEJ

← Rev. 3 →

I think i have an easier to code solution to D using two pointers and reverse() function in C++.

Here's my submission.

I can explain it if you want but it's easy to understand I guess.

Trinethra

Hey, Can you please explain your approach?

+22

OK.

It can be shown that the minimum LIS cant be less than the length of the longest segments containing only '<'.

Now consider the array n,n-1,n-2,...,2,1. Now for every segment of '<' reverse the numbers in that segments for example

">><<<>>>"

9 8 4 5 6 7 3 2 1

You can see that it acquires the minimum LIS.

For the maximum LIS it can be shown that the LIS can't be longer than the number of '<' + 1.

Now consider the array 1,2,3,...,n-1,n. Now for each segment of '>' reverse the numbers of that segment. For example

">><<>><"

3 2 1 4 7 6 5 8

and this approach requires the maximum LIS.

I hope mt explanations were clear.

pritishn

LCA?? Did you mean LIS?

YES!!

SORRY after thinking on problem E LCA was stuck in my head XD

Sorry it was a mistake. I fixed it now.

Thanks !! Nice Approach.

kadam

Shouldn't the answer in example for maximum (<<>><) be 1 2 5 4 3 6 7 8. By the way your approach is really good.

Fixed it.I should have put "<" and ">" string between "" to make it look correct in comment.

Thank you.

hpp

It's really a nice solution!Thx

Its_Easy

Can you please share the intuition behind this method?

imsidduroy

Tanx very much.its lot clear.

rr459595

Nice approach.

rahuliitkgp

4 years ago, # ^ |

EMEJ Thanks bro really great solution

e.m.blagov

For D to make LIS exactly k I think, the k must be possible to be represented by sum of length of increasing consecutive groups + 1 and be more than length of max group Example:

>>><<>>><>>><><<

we have 4 groups << < < <<

so k can be 3 (our minimum, because it is maximal length of single increasing group +1) k, can also be 4 and 5 and 6,7 for 3: I first fill rightmost group of size two, and others should be filled up from right to left (to avoid random LIS):


 << < < <<
        12

then I do

 << < < <<
 56 4 3 12

and then on not filled space I follow in increasing order from right to left

>  >  >  < < >  >  >  < >  >  > < > < <
17 16 15 5 6 14 13 12 4 11 10 9 3 8 1 2 7

so we have 5, 6, 14, or 1, 2, 7

for k=4: I would do:


>  >  >  < < >  >  >  < >  >  > < > < <
         5 6          4         1   2 3

then fill up again:

>  >  >  < < >  >  >  < >  >  > < > < <
17 16 15 5 6 14 13 12 4 11 10 9 1 8 2 3 7

and we have 1,2,3,7

need more detailed analysis for how we can combine different groups, but for problem that was given in editorial, I was putting all together by filling up groups from left to right for longest LIS, and from right to left to shortest LIS. So I by offsetting start point we can get different k

Apolodor

Question on A

On 71161349 I got WA on test 3 and after I had changed long long into int I got accepted. I wasted 6 resubmissions and a lot of time during the contest thinking my Idea was wrong. This is the good one 71163490.

Anyone know what's going on here?

You can read the checker's comment: "wrong output format Expected integer, but "1.73633e+006" found"

You used double so it can be printed in a different way other than pure integer, even if the value can be represented as an integer.

Thanks for the answer

Does this have to do with the fact that the statement asks for the output as an integer or is it something from the compiler/the way codeforces evaluates submissions?

The checker used in this problem only accepts integers in integer form, and I think in most (if not all) cases when the problem says 'integer', you must print it in integer form.

galen_colin

It's not that you changed long long to int, it's that you changed double to int as well. Your wrong answer shows you printed 1.73633e+006, which it doesn't think is an integer. Changing it to int makes it print correctly. Adding cout << setprecision(0) << fixed; should also do the trick (although you'd also have to add #include <iomanip>).

edit: this was already answered, but I didn't refresh it

Does this mean there is some default setprecision value even when the value of the double has no decimals?

Yes, the default is 6 (source), and fixed-point notation will always print values with that many decimals, even integral values. However, this doesn't apply to 'normal' double output when you're working specifically with integral values.

If it does not apply to double that has an integral value then why did my program print 1.73633e+006, as the value of t can only be integral? (I check if the % is 0 and only then do the division)

Fair, seems like it is limiting itself to 6 digits of precision, as it would rather print 1e6 than 1000000.

person123

In problem div 2 C how are we updating the value of mx and mn? Can anyone explain it please?

kk_ban

Whats wrong with this code failing test 3 3rd token :
https://codeforces.me/contest/1304/submission/71185623

In case of "NO" ;you are not taking all t,l,h values. You have set ans=0 and came out of loop using break. Just remove the break statement.

if ans is zero that means there is some customer who can't be satisfied so why not to break .

BurnedChicken

Even though you know that there is some customer who can't be satisfied, you should take the all the values, otherwise when your program proceeds on the next test case, instead of taking the correct inputs, your program will take the customers that can't be satisfied from the previous test case (because you didn't take it before) and fail.

There is another solution for F(maybe only a bit different).

We don't need to calculate sum(animal[i][j…j+k−1]) for each j.

First let us solve max(1,j-k+1)<=x<=j,then the other part can be solved using the same idea.

we define P[i][j] as dp[i][j]-sum(animal[i+1][1....j-k+1])

then dp[i][j] is updated by max(P[i-1][max(1,j-k+1).....j]+sum(animal[i…i+1][j…j+k−1])+sum[i-1][1...j-1]).

Since sum(animal[i…i+1][j…j+k−1])+sum[i-1][1...j-1] is a constant for each <i,j>

We can find out the max value by simple RMQ algorithms on array P[i-1]

Ramprosad

Nice Problemset and editorial. I really Enjoy the contest. Thanks to problem setter.djm03178

skglt

I believe there's something wrong with the second question's answer as if it wants the longest palindromic string then for the case like

5 2 oo ox xo xx xx

The answer can be "10 , xoxxooxxox" but the answer given by the above code is "6 , oxxxxo" which I don't believe is longest one . Even for the test case like

3 2 xx xx xx

The output from the code is "2 , xx" and not "6 , xxxxxx" . If I'm wrong anywhere please let me know .

aspiriner

What's the problem wtih my code?

https://codeforces.me/contest/1304/submission/71196899

My method as similar sa the editorial.

Just he use the arrays.Please tell me where my code is wrong.

HungTeen

your t1 is not the time between two adj people, a data like 3 0 1 1 1 4 4 4 6 7 7 your ans is YES ,but NO is right .

Thanks fo you.You're pretty good.

tanishqg5325

Can somebody please tell me why I am getting Runtime Error on pretest 3 on this submission for problem C?

There is an assert statement which verifies whether the visit time of customers are in non decreasing order. Runtime error seems to suggest that there is a test case in which visit time of customers are not in non decreasing order.

When I removed the assert statement, I got WA. See this.

And, when I myself sorted the customers according to their visit time, I got "Accepted" verdict. See this.

if you output NO and return ,the function is over,but your input didn't finish. i think its the problem.why not finish the read and then deal with the problem

Thanks for the response. I understood your point. My bad !

Tavern

← Rev. 5 →

In problem E,

The simple path from $$$a$$$ to $$$b$$$ without using the added edge.

The simple path from $$$a$$$ to $$$x$$$ without using the added edge, plus the added edge, plus the simple path from $$$y$$$ to $$$b$$$ without using the added edge.

The simple path from $$$a$$$ to $$$y$$$ without using the added edge, plus the added edge, plus the simple path from $$$x$$$ to $$$b$$$ without using the added edge.

What is the difference between the second and the third case? For example, in the case below:

We can see that the three paths are as follow: $$$2 \to 1 \to 4$$$ $$$2 \to 3 \to 5 \to 4$$$ $$$2 \to 1 \to 4 \to 5 \to 3 \to 2 \to 1 \to 4$$$ But in this path, noticing that the edge (1, 2) and (1, 4) are used twice, we can ignore the influence they bring to the parity of the total length, thus the path becomes： $$$2 \to 3 \to 5 \to 4$$$ And the second and the third path become the same. So what's the meaning of considering the third case? Or did I forget to consider some other situation?

The third path became useless because you 'noticed' that they have duplicated edges. You don't need to check if they have such edges if you just calculate both the second and the third path.

[deleted]

mridul_bhatt

Can anyone please look into My code for Problem C. My logic is similar to the editorial but it shows WA for the 32nd token of test 3.

jarvis307

71201513 Could someone please debug the run-time error I'm getting on this solution? Apparently the error happens in the last loop, where the assert condition fails.

for(i=store.size()-1; i>=0; i--){
        assert(i>=0 && i<store.size());
        string temp1 = inp[store[i]];
        reverse(temp1.begin(), temp1.end());
        out.append(temp1);
    }

I tried printing i, and it printed out a large value.

OUTPUT:

OOH!: 4294967295

It's really puzzling and I would appreciate any help. Thanks!

i is declared to be long long

size() returns an unsigned integer, so if the value is 0u then subtracting 1 from it will make it overflow.

Thanks a lot!

AMIT9019

for problem D. How to find a sequence for fixed length k LIS?

tdkbdbpvn

My solution to the problem E is the same as author's, even my implementation is quite similar to his but I have repeatedly got TLE on test 2. I've generated lots of huge testcase to check but it runs all the way fine, no probs. And test 2 is a small test, so I tried to generate as similar to the testcase as possible but no issues found so I desperately ask for your help on my case: https://codeforces.me/contest/1304/submission/71262563 I'd be very thankful.

evenharder

__builtin_clz(0) returns an undefined value (it is well-defined for non-zero arguments). Thus, when H[u] equals to 0 (in this case, u == 1) something unpredictable might happen under the hood.

roslinmahmud

I'm not understanding why I'm getting WA in Problem C My Submission. Can anyone help?

nweeks

You break out of for loop where input is read. So you don't read the entire input for a test case!

shadaBhai

In problem E, we need to determine the root to use LCA. But as there is no info about that and all the edges are bidirectional, how are we going to determine the root? Sorry to bother you.

The LCA is just a way to find distances easily, the root you choose does not change the distance, so you can pick any root you want.

dante_part_2

In problem C, can someone explain how the condition mn-k <= R and mx+k >= L is working?? Thanks in advance :)

That condition in other words is "there is at least one intersected temperature between the range of their preferred temperature and the range of available temperature."

Kaab

can you please explain about updating mn and mx

You want to maximize the range. In other words, you want to minimize mn and maximize mx, respectively. So, you want to set mn as mn — K and mx as mx + K, but L and R might not be in this range. This means that mn cannot be smaller than L and mx cannot be larger than R. Conclusively, mn should become max(mn — K, L) and mx should become min(mx + K, R).

single_block

-27

for solution of (B) — Longest Palindrome:

input:
3 3
aba
aba
aba

given output:
3
aba

but, it should be

9
abaabaaba

It says all strings are distinct, so it's not a valid case.

md_akash1

-21

Hi, your tutorial is very good but i have one doubt with the solution of B(Longest palindrome). for example if my input is : input: 3 3 tat cat tat output: tat i think right answer is : tattat

+24

Please, read my comment right above yours.

Hd7

Please anyone can help me to figure out what wrong with my submission. I struggle in many hours on test case 8, problem E.

SarthakBansal

4 years ago, # |

Honestly, for Problem D

is comment ne bacha liye, Editorial me to chutiya kaat diya.

English Translation:

For Problem D, this comment saved my ass. Editorial is really messy and not clear.

P.S.: If anyone got Editorial's explanation for Problem D, Please Explain.

(Also what is perm[] array in editorial ?! :/)

I don't know which part you think is messy. The comment you linked is identical to the editorial, even the explanation's logic and the solution's outputs are the same. Maybe the comment's implementation is a little easier.

Anyways, perm means permutation sequence the problem is asking you to find. perm[i] is the i-th number of the answer.

djm03178's blog