Разбор Educational Codeforces Round 48

№	Пользователь	Рейтинг
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	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Разбор

Код решения (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;
	
	int r = 0;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		
		r += x;
		cout << r / m << ' ';
		r %= m;
	}
	cout << '\n';
	
	return 0;
}

1016B - Segment Occurrences

Разбор

Код решения (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

const int N = 1000 + 7;

int pr[N];
bool ok[N];

int main() {
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	string s, t;
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	scanf("%s", buf);
	t = buf;
	
	pr[0] = 0;
	forn(i, n - m + 1){
		bool fl = true;
		forn(j, m)
			if (s[i + j] != t[j])
				fl = false;
		ok[i] = fl;
		pr[i + 1] = pr[i] + ok[i];
	}
	for (int i = max(0, n - m + 1); i < n; ++i){
		pr[i + 1] = pr[i];
	}
	
	forn(i, q){
		int l, r;
		scanf("%d%d", &l, &r);
		--l, r -= m - 1;
		printf("%d\n", r >= l ? pr[r] - pr[l] : 0);
	}
	return 0;
}

1016C - Vasya And The Mushrooms

Разбор

Код решения (Ajosteen)

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;

int n;
int a[2][N];
long long sum123[2][N];
long long sum321[2][N];
long long sum111[2][N];

int main() {
	//freopen("input.txt", "r", stdin);
	
	scanf("%d", &n);
	for(int i = 0; i < 2; ++i)
		for(int j = 0; j < n; ++j)
			scanf("%d", &a[i][j]);
	
	for(int i = 0; i < 2; ++i)
		for(int j = n - 1; j >= 0; --j){
			sum123[i][j] = sum123[i][j + 1] + (j + 1) * 1LL * a[i][j];
			sum321[i][j] = sum321[i][j + 1] + (n - j) * 1LL * a[i][j];
			sum111[i][j] = sum111[i][j + 1] + a[i][j];
		}
		
/*	for(int i = 0; i < 2; ++i)
		for(int j = n - 1; j >= 0; --j){
			cout << i << ' ' << j << " : ";
			cout << sum123[i][j] << "  " << sum321[i][j] << "  " << sum111[i][j] << endl;
		}			*/
		
	long long res = 0, sum = 0;
	for(int i = 0, j = 0; j < n; ++j, i ^= 1){
		long long nres = sum;
		nres += sum123[i][j] + j * 1LL * sum111[i][j];
		nres += sum321[i ^ 1][j] + (j + n) * 1LL * sum111[i ^ 1][j];
		res = max(res, nres);
		
		sum += a[i][j] * 1ll * (j + j + 1);
		sum += a[i ^ 1][j] * 1ll * (j + j + 2);
	}
	
	for(int j = 0; j < n; ++j) res -= a[0][j] + a[1][j];
	printf("%I64d\n", res);
	
    return 0;
}

1016D - Vasya And The Matrix

Разбор

Код решения (Ajosteen)

#include <bits/stdc++.h>
#include "testlib.h"

using namespace std;

const int N = 109;

int n, m;
int a[N], b[N];
int res[N][N];

int main() {
	int cur = 0;
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		cin >> a[i], cur ^= a[i];
	for(int i = 0; i < m; ++i)
		cin >> b[i], cur ^= b[i];
	
	if(cur != 0){
		puts("NO");
		return 0;
	}
	
	puts("YES");
	for(int i = 1; i < m; ++i) 
		cur ^= b[i];
	cur ^= a[0];
	
	cout << cur << ' ';
	for(int i = 1; i < m; ++i)
		cout << b[i] << ' ';
	cout << endl;
	for(int i = 1; i < n; ++i){
		cout << a[i] << ' ';
		for(int j = 1; j < m; ++j)
			cout << 0 << ' ';
		cout << endl;
	}
    return 0;
}

1016E - Rest In The Shades

Разбор

Код решения (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const double EPS = 1e-9;

const int N = 200 * 1000 + 555;

li sy, a, b;
int n, q;
pt s[N], p[N];

inline bool read() {
	if(!(cin >> sy >> a >> b))
		return false;
	assert(cin >> n);
	fore(i, 0, n)
		assert(scanf("%lld%lld", &s[i].x, &s[i].y) == 2);
	assert(cin >> q);
	fore(i, 0, q)
		assert(scanf("%lld%lld", &p[i].x, &p[i].y) == 2);
	return true;
}

int getGE(ld x) {
	for(int pos = max(int(lower_bound(s, s + n, pt(li(x), -1)) - s) - 2, 0); pos < n; pos++)
		if(x <= s[pos].x)
			return pos;
	return n;
}

li ps[N];

li getSum(int l, int r) {
	li ans = r > 0 ? ps[r - 1] : 0;
	ans -= l > 0 ? ps[l - 1] : 0;
	return ans;
}

inline void solve() {
	fore(i, 0, n) {
		ps[i] = s[i].y - s[i].x;
		if(i > 0)
			ps[i] += ps[i - 1];
	}
	
	fore(i, 0, q) {
		ld lx = p[i].x + (a - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
		ld rx = p[i].x + (b - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
		
		int posL = getGE(lx);
		int posR = getGE(rx) - 1;
		
		ld sum = getSum(posL, posR);
		if(posL > 0)
			sum += max(ld(0.0), s[posL - 1].y - max((ld)s[posL - 1].x, lx));
		if(posR >= 0)
			sum += max(ld(0.0), min((ld)s[posR].y, rx) - s[posR].x);
		
		sum *= ld(p[i].y - sy) / p[i].y;
		printf("%.15f\n", double(sum));
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1016F - Road Projects

Разбор

Код первого решения (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

const long long INF64 = (long long)(1e18);
const int N = 1000 * 1000 + 13;

int n, m;
vector<pair<int, int>> g[N];
long long d[N];
int siz[N];
int tin[N], tout[N], T;
int pr[N];

void calc(int v, int p){
	pr[v] = p;
	tin[v] = T++;
	siz[v] = 1;
	for (auto it : g[v]){
		int u = it.first;
		int w = it.second;
		if (u == p) continue;
		d[u] = d[v] + w;
		calc(u, v);
		siz[v] += siz[u];
	}
	tout[v] = T++;
}

inline int isp(int v, int u){
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

long long dif;
long long mn;

void dfs(int v, int p){
	dif = min(dif, max(0ll, -(mn - d[v])));
	if (p != -1 && pr[p] != -1)
		dif = min(dif, max(0ll, -(d[pr[p]] - d[v])));
	
	for (auto it : g[v]){
		int u = it.first;
		int w = it.second;
		if (u == p) continue;
		if (!isp(u, n - 1)){
			dif = min(dif, max(0ll, -(mn + w - d[v])));
			mn = max(mn, w + d[v]);
			if (p != -1)
				dif = min(dif, max(0ll, -(w - d[v] + d[p])));
		}
	}
	
	for (auto it : g[v]){
		int u = it.first;
		if (u == p) continue;
		if (isp(u, n - 1))
			dfs(u, v);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, n - 1){
		int v, u, w;
		scanf("%d%d%d", &v, &u, &w);
		--v, --u;
		g[v].push_back(make_pair(u, w));
		g[u].push_back(make_pair(v, w));
	}
	
	T = 0;
	calc(0, -1);
	
	long long cur = d[n - 1];
	dif = INF64;
	mn = -INF64;
	
	forn(i, n)
		if (!isp(i, n - 1) && siz[i] > 1)
			dif = 0;
	
	if (dif > 0)
		dfs(0, -1);
	
	forn(i, m){
		int x;
		scanf("%d", &x);
		printf("%lld\n", min(cur, cur - dif + x));
	}
	
	return 0;
}

Код второго решения (BledDest)

#include<bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int> > > g;
vector<long long> d;
vector<long long> d1;
vector<long long> dn;

int n, q;

bool read()
{
	scanf("%d %d", &n, &q);
	g.resize(n);
	d.resize(n);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		--x;
		--y;
		g[x].push_back(make_pair(y, w));
		g[y].push_back(make_pair(x, w));
	}
	return true;
}

void dfs(int x, int p = -1, long long dist = 0)
{
	d[x] = dist;
	for (auto e : g[x])
		if (p != e.first)
			dfs(e.first, x, e.second + dist);
}

void solve()
{
	dfs(0);
	d1 = d;
	dfs(n - 1);
	dn = d;
	set<pair<long long, int> > dists_n;
	vector<pair<long long, int> > order;
	for(int i = 0; i < n; i++)
	    order.push_back(make_pair(d1[i] - dn[i], i));
	sort(order.begin(), order.end());
	for(int i = 0; i < n; i++)
	    dists_n.insert(make_pair(dn[i], i));
	vector<int> pos(n);
	for(int i = 0; i < n; i++)
		pos[order[i].second] = i;
	long long T = (long long)(1e18);
	for(int i = 0; i < n; i++)
	{
		int v = order[i].second;
		dists_n.erase(make_pair(dn[v], v));
		for (auto e : g[v])
			if (pos[e.first] > pos[v])
				dists_n.erase(make_pair(dn[e.first], e.first));
		if (!dists_n.empty())
			T = min(T, d1[n - 1] - d1[v] - dists_n.rbegin()->first);
		for (auto e : g[v])
			if (pos[e.first] > pos[v])
				dists_n.insert(make_pair(dn[e.first], e.first));
	}
	for(int i = 0; i < q; i++)
	{
		int x;
		scanf("%d", &x);
		printf("%lld\n", d1[n - 1] - max(0ll, T - x));
	}
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	if (read())
	{
		solve();
	}
}

1016G - Appropriate Team

Разбор

Код решения (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);

const int N = 200 * 1000 + 555;
int n; li x, y;
li a[N];

inline bool read() {
	if(!(cin >> n >> x >> y))
		return false;
	fore(i, 0, n)
		assert(scanf("%lld", &a[i]) == 1);
	return true;
}

li gcd(li a, li b) {
	while(a > 0) {
		b %= a;
		swap(a, b);
	}
	return b;
}

vector<pt> factorize(li v) {
	vector<pt> f;
	for(li x = 2; x <= 1'000'000 && x * x <= v; x++) {
		int cnt = 0;
		while(v % x == 0)
			v /= x, cnt++;
		if(cnt > 0)
			f.emplace_back(x, cnt);
	}
	if(v > 1) {
		for(li s = max(1ll, (li)sqrtl(v) - 2); s * s <= v; s++)
			if(s * s == v) {
				f.emplace_back(s, 2);
				v = 1;
				break;
			}
		if(v > 1) {
			vector<li> cnd(a, a + n);
			cnd.push_back(x);
			cnd.push_back(y);
			
			for(li c : cnd) {
				li g = gcd(v, c);
				if(g != 1 && g != v) {
					li a = g, b = v / g;
					if(a > b)
						swap(a, b);
						
					f.emplace_back(a, 1);
					f.emplace_back(b, 1);
					v = 1;
					break;
				}
			}
			if(v > 1)
				f.emplace_back(v, 1), v = 1;
		}
	}
	return f;
}

int d[(1 << 18) + 3];

inline void solve() {
	if(y % x != 0) {
		puts("0");
		return;
	}
	
	vector<pt> fy = factorize(y);
	vector<pt> fx;
	li cx = x;
	for(auto p : fy) {
		int cnt = 0;
		while(cx % p.x == 0)
			cx /= p.x, cnt++;
		fx.emplace_back(p.x, cnt);
	}
	
	vector<li> ps;
	vector<pt> bb;
	
	fore(i, 0, sz(fy)) {
		if(fx[i].y < fy[i].y) {
			ps.push_back(fy[i].x);
			bb.emplace_back(fx[i].y, fy[i].y);
		}
	}
	
	fore(i, 0, n) {
		if(a[i] % x != 0)
			continue;
		
		int mask = 0;
		li ca = a[i];
		fore(j, 0, sz(ps)) {
			int cnt = 0;
			while(ca % ps[j] == 0)
				ca /= ps[j], cnt++;
			assert(cnt >= bb[j].x);
			
			mask |= (cnt > bb[j].x) << j;
		}
		d[mask]++;
	}
	
	for(int i = 0; i < sz(ps); i++) {
		fore(mask, 0, 1 << sz(ps))
			if((mask >> i) & 1)
				d[mask] += d[mask ^ (1 << i)];
	}
	
	li ans = 0;
	fore(i, 0, n) {
		if(y % a[i] != 0)
			continue;
		
		int mask = 0;
		li ca = a[i];
		fore(j, 0, sz(ps)) {
			int cnt = 0;
			while(ca % ps[j] == 0)
				ca /= ps[j], cnt++;
			assert(cnt <= bb[j].y);
			
			mask |= (cnt < bb[j].y) << j;
		}
		ans += d[mask ^ ((1 << sz(ps)) - 1)];
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

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

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

dorijanlendvaj

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

Can someone prove/find a countercase for my solution for D? 41174052

→ Ответить

panipuri8

I upsolved D in the same manner. Will try to explain the logic behind it [Since the editorial simply left it to the reader to find its proof]

Let r,c be the dimensions of the matrix, row[1..r] be the row wise xor value array, col[1..c] be the column-wise xor value array.

Temporarily, forget a[1][1]. Fill a[1][2] with col[2], a[1][3] with col[3] and so on.. So everything except col[1] is satisfied right now. (We are filling the first row, except the first element, with values from col array)

Similarly, fill a[2][1] with row[2], a[2][3] with row[3] and so on.. Everything except row[1] is satisfied right now (We are filling the first column, except the first element, with values from row array)

Now we have a[1][1] left. Based on the values we filled right now, the current xor value of the first row in our matrix is col[2]^col[3]^..col[c]. This value, can also be represented as C^col[1], where C = total xor of the col array (col[1]^col[2]^..col[c]).. We know that the xor value of elements in first row should be row[1]. Hence, if a[1][1] is equal to C^col[1]^row[1], our answer satisfies all the stipulated properties.

What if we had done it the other way round? Lets check that out. Based on the values we filled right now, the current xor value of the first column in our matrix is row[2]^row[3]^..row[r]. This value, can also be represented as R^row[1], where R = total xor of the row array (row[1]^row[2]^..row[r]).. We know that the xor value of elements in first column should be col[1]. Hence, if a[1][1] is equal to R^row[1]^col[1], our answer satisfies all the stipulated properties.

If we had chosen either of the above options, it would still be the same value. Its because R=C!

brdy

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

← Rev. 2 →

How can we be sure this always identifies an impossible case? E.g what if using some other strategy you can make a matrix when this method returns "NO"?

The initial check, about R not being equal to C (refer my first comment for notations), is enough for the impossible condition.

R will have each element represented once, while C will have each elemented represented once. Xor-ing these two values should give zero.

Hence, checking for this condition and then proceeding with this algorithm of filling the first row and first column alone, and leaving the other elements as zero is a good enough solution.

Forgive me if I misunderstood your question.

What if there is some case where you can fill some of the 0's such that an input you deemed "impossible" is possible. My question is how can you prove this case does not exist, because of course it works when there is a valid matrix, but how can we be sure it always identifies impossible case.

I waited for this to be explained in editorial, and I'm a bit disappointed they didn't even mention it.

Fighter.human

You haven't given the proof rather you have explained the obvious thing. If you know the thing what @burdy said then please share otherwise the above thing of yours is just like some irrevelant stuff which I think everybody knows already :xD.

shazly555

In problem D... Why if xor of a1 a2 ...an != to xor of b1 b2 ...bm the answer is no??

devid

+16

Because $\text{[math]}$ is xor of all elements in matrix, and $\text{[math]}$ is xor of all elements in matrix. So they must be equal.

Haunted_Cpp

Could someone explain to me the logic behind exercise — C? I can't seem to understand it,even after reading the editorial.

amityadav

Let first you have to move in a zigzag pattern then go right to end and then left where you stop zigzag pattern.(it's cover all case) Key point is if you start moving in straight line you can't allow to move in zigzag pattern again only one 'U' turn at end.(think why?)

So you can stop zigzag pattern at 1,2,3,...,N-1.For each value where you stop zigzag pattern (1<=i<=N-1) . You can find total weight of the collected mushrooms in O(1) by help of sum123, sum321 and sum111.

Thanks for the help, but one more thing, what values does Sum123,Sum321,Sum111 contain ?

For that see Editorial.

Ok, thanks for the tips :-))

that 3 arrays is like suffix sum array. ex: a[1,2,3,4] ss[10,9,7,4] at 1<='i'<=n we save sum of i to n;

but in this case we make suffix weight.

I_love_Kuroni

-23

Problem D can be solved with Gaussian Elimination. This way the solution is more straightforward.

KAISER17

can you elaborate?

Since a[i], b[i] <= 10E9, for each number in the table, there are at most 30 bits, and each bit is independent from others. I mean, the k-th bit of c[i][j] has nothing to do with (k + 1)-th bit, etc.

Consider k-th bits of all c[i][j]. Let denote that b[k][i][j] = 1/0.

Now you can see that we have a system of n + m linear equations such that:

(b[k][1][1] + b[k][1][2] + ... b[k][1][m]) % 2 = k-th bit of a1

...

(b[k][n][1] + b[k][n][2] + ... b[k][n][m]) % 2 = k-th bit of a[n]

(b[k][1][1] + b[k][2][1] + ... b[k][n][1]) % 2 = k-th bit of b[1]

(b[k][1][m] + b[k][2][m] + ... b[k][n][m]) % 2 = k-th bit of b[m]

This way, it makes sense that a solution of this system of equations is also a solution for all k-th bits of c[i][j]. In order to find a solution, use Gaussian Elimination. Since there are 30 bits, do this 30 times :)

Here is my AC code 41183870

In my code, in order to implement easily, I assume that every equation has n + m variables. However, if the variable is unnecessary for the equation (for instance, b[k][2][1] is unnecessary for (*)), let the coefficient 0, otherwise 1.

In addition, since the eliminating process is the same for all bits, I list all bits at once and do the eliminating process once only.

tech_mint0013

-8

In problem C what if we were not allowed to fill 0 as an entry i.e. if 1<=c<=2*10^9 ??

rr459595

Can someone please explain how to implement problem C ?

Thanks.

61615601

← Rev. 5 →

There's a bug in test data in Problem F:

There is an Accepted Submission: 41232049

The test data:

correct answer should be : 100(link the vertex 1 and 3)

but its answer is: 3

awoo

That's called an incomplete testset, not bugged. Just a missed possibility for the hack.

Sorry for my poor English,⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

So will the test data be updated?or still incomplete ?

It has been added. Previous submissions are not retested, obviously, but this test will present for the further ones.

o_v_shake

Can someone explain me how sum111 is handling the growth of the mushrooms in Problem C.

BledDest

sum111[i] is the total speed of mushroom growth in the cells on segment [i .. n].

So, for example, if we start collecting mushrooms on segment [i .. n] in time moment 2i — 2, then we add to the answer the value of sum123[i] + sum111[i] * (2i — 2).

Someone, please correct me if I am wrong but can the top left element be also set as b1 ^ a2 ^ a3 ^ ... ^ an in problem D .

adedalic

Since a1 ^ a2 ^...^ an = b1 ^ b2 ^...^ bm, so, of course, a1 ^ b2 ^...^ bm = b1 ^ a2 ^...^ an.

chanchancl

← Rev. 3 →

There are two announcements and two tutorials link in problems page.

saketh

+14

It's interesting that the second solution for F works even without the restriction that the input graph is a tree. Have you used the same technique before for other problems?

+11

That's really interesting, I didn't even see that.

In fact, it will be better if I address this question to vovuh because he actually proposed this idea in problem F (and I just implemented the solution and handled the fact that the edges we add are bidirectional).

vovuh

Wow! Such an interesting fact. Well, I haven't used this idea earlier (I suppose). I came up with it while I thought about a shortest paths graph condition (for the edge (x, y) it is true that this edge is in the shortest paths graph iff d1_x + w(x, y) + dn_y = d1_n or d1_y + w(x, y) + dn_x = d1_n, it is well known equation). And I decided that it also can be true for the general case, but I haven't thought about it.

Mohinem

Why is Binary Search giving me TLE in Proble 1016E — Rest In The Shades ?

http://codeforces.net/contest/1016/submission/41256720

I think there's no better solution than O(log n) per query.

Please help !!!!

MZuenni

try using scanf and printf the timlimit is to hard for this one i believe... i only got AC with scanf and printf too

It was mentioned in the other thread that reading integers as doubles with cin slows down solution greatly.

The graph for problem F can be further restricted: its a path between 1 and n where every vertex on the path has at most one additional child wich is a leaf. (in every other case there would be 3 vertices connected by two edges which are not on the 1 to n path. Adding a third edge to this triangle would not change the shortest path as the added edge cant even lie on any simple path between 1 and n)

roll_no_1

There's a typo in the tutorial for problem C. Instead of the a_i s, we have a_k s. I'm mentioning this because I initially got confused while reading the expressions in the tutorial.

pe4kin

Someone can explain to me why we do exactly this pr[i + 1] = pr[i] + ok[i]; and this --l, r -= m - 1; in problem B? This is not clear to me

The first one is prefix sums. https://www.hackerrank.com/topics/prefix-sum

For the second one: Since t is of length m, within the segment [l, r], the last position where it can start from is r-(m-1), So, we only count the occurences of t between [l, r-(m-1)]

relinquisheddragon

Can someone explain the statement for(int i = 0, j = 0; j < n; ++j, i ^= 1) in problem1016C

rotavirus

it is equivalent to

int i=0,j=0;
while(j<n)
{
   ...
   ++j;
   i=1-i;
}

manish_joshi

In Problem C's editorial,

"Let's iterate on the number of columns Vasya will pass in a zigzag pattern and maintain the weight of mushrooms he will collect while doing so."

How exactly we know which zigzag path we have to take and upto where ?

retired.old.cake

Firstly, we can observe that there are exactly (n + 1) ways to go through the grid

Ill express the coordinate using the format (row_num, col_num)
The first scenario is to from (1,1) to (1,n) then to(2,n) then to (2, 1) (Sample Input 1)
The second scenario is a zig-zag pattern (Sample Input 2)
The rest is by combining the two.

Any other scenario will block the previous cell and disconnects the grid

Example:
n = 3
(1,1) -> (1,2) -> (2,2) -> (2,3) -> (1,3)

Obviously, all path to (2,1) is blocked

With the above conclusion, we can use Dynamic Programming to precompute the prefix sum and calculate the answer

Many thanks! That helped clear the cloud of ignorance in my thinking pattern. "Any other scenario will block the previous cell and disconnects the grid" — this line hit me so hard, i realized where i was stuck.

Thelam

Maybe there's an easier solution for D. The matrix could be

b[1] b[2] …… b[m-1] (a[1] xor b[1] xor b[2]……b[m-1])

0 0 …… 0 a[2]

0 0 …… 0 a[3]

....

0 0 …… 0 a[n]

Because (a[1] xor b[1] ...b[m-1]) xor a[2]...a[n] = b[m], so it is a possible solution

basically it is the same solution

Ehsan_sShuvo

Could you please provide any proof or explain the problem why such arrangement will provide a correct answer ?

it is written in editorial

nothing10

1016A - Тетрадь Смерти

[Problem:B] - Segment Occurrences

Can someone please explain to me why 'l' is decremented in the last for loop?

And also it would be much appreciated if you explain for any value x, what does pr[x] stand for? From the above code, I guess pr[x] represents the number of times string 't' appears in s[1, x+|m|-1].

Bekh

First, see prefix sum : https://www.hackerrank.com/topics/prefix-sum

And decrementing of l because the input is given 1 based while we work zero based in our arrays.

Second, hope looking at it from the other side clears it up. So here's my approach. You'll find prefix sum of occurrences of string t in s but instead of marking the start positions of the string, you'll mark the end positions.

For example, in the first test case looking for for in codeforces the prefix array will look like this

c o d e f o r c e s

0 0 0 0 0 0 1 1 1 1

now pre[i] means number of occurrences of string t in string s in [0, i]. This is consistent with given r but we need to push l (m-1) positions. now you have pre[r] and pre[l+m-1]. To get what's in between them you substract pre[r] — pre[(l+m-1) — 1].

Hopefully this clears it up also see my code 41592407 for further understanding

I've gone through your solution thoroughly and understood how you actually stored number of occurrences of string t in prefix sum array using the end index, that way it makes the range clearer! Thanks a lot for your help Bekh :)

Glad it helped :). Keep coding!

ivan100sic

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

There's no need to do prime factorization in problem G, it can be solved in true polynomial time. Just factor $$$Y$$$ relative to numbers $$$a_1, \ldots, a_n, X$$$. By relative factorization I mean, represent $$$Y = f_1^{b_1} \cdots f_k^{b_k}$$$, where $$$f_i$$$ are pairwise coprime and for each $$$r \in a \cup X$$$, $$$GCD(r, f_i)$$$ is either $$$1$$$ or $$$f_i$$$. This factorization can be easily found by starting with $$$[Y]$$$ and refining it with each element of $$$a \cup X$$$. Finally you can safely use this factorization instead of the true prime factorization of $$$Y$$$ in the same way as in the editorial.

Sample code: 82648734

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