Educational Codeforces Round 60 Editorial

#	User	Rating
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

#	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	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (adedalic)

#include<iostream>
using namespace std;

int main() {
	int n; cin >> n;
	int mx = -1, lenMx = 0;
	
	int curEl = -1, curLen = 0;
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		
		if(curEl != a)
			curEl = a, curLen = 0;
		curLen++;
		
		if(mx < curEl)
			mx = curEl, lenMx = 0;
		if(mx == curEl)
			lenMx = max(lenMx, curLen);
	}
	cout << lenMx << endl;
	return 0;
}

1117B - Emotes

Tutorial

Solution (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, k;
	cin >> n >> m >> k;
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	
	cout << m / (k + 1) * 1ll * (a[0] * 1ll * k + a[1]) + m % (k + 1) * 1ll * a[0] << endl;
	
	return 0;
}

1117C - Magic Ship

Tutorial

Solution (Roms)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 100009;

pair<int, int> st, fi;
int n;
string s;

string mv = "UDLR";
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

pair<int, int> d[N];

int main(){
	cin >> st.x >> st.y >> fi.x >> fi.y;
	cin >> n >> s;		

	for(int i = 0; i < n; ++i){
		int id = -1;
		for(int j = 0; j < 4; ++j)
			if(mv[j] == s[i])
				id = j;
		assert(id != -1);
		d[i + 1] = make_pair(d[i].x + dx[id], d[i].y + dy[id]);
	}

	long long l = 0, r = 1e18;
	while(r - l > 1){
		long long mid = (l + r) / 2;
		long long cnt = mid / n, rem = mid % n;
		long long x = st.x + d[rem].x + cnt *  1LL * d[n].x;
		long long y = st.y + d[rem].y + cnt *  1LL * d[n].y;
		long long dist = abs(x - fi.x) + abs(y - fi.y);
		if(dist <= mid)
			r = mid;
		else
			l = mid;	
	} 

	if(r > 5e17) r = -1;
	cout << r << endl;

	return 0;
}

1117D - Magic Gems

Tutorial

Solution (Reziba)

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define bolt ios::sync_with_stdio(0)
#define light cin.tie(0);cout.tie(0)
#define forr(i,p,n) for(ll i=p;i<n;i++)
#define MAXN 1000003
typedef long long ll;
using namespace std;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}

ll bin[103][103];

void mult_mat(ll m, ll ans[][100], ll bin[][100]){
    ll mult[m][m];
    forr(i,0,m){
        forr(j,0,m){
            mult[i][j]=0;
            forr(k,0,m){
                mult[i][j]+=ans[i][k]*bin[k][j];
                if(mult[i][j]>=MOD){
                    mult[i][j]%=MOD;
                }
            }
        }
    }
    forr(i,0,m){
        forr(j,0,m){
            ans[i][j]=mult[i][j];
        }
    }
}

void pow_mat(ll n, ll fin[][100], ll m){
    ll ans[m][100];
    ll b[m][100];
    forr(i,0,m){
        forr(j,0,m){
            ans[i][j]=bin[i][j];
            b[i][j]=bin[i][j];
        }
    }
    n--;
    while(n>0){
        if(n%2==1){
            mult_mat(m,ans,b);
            n--;
        }else{
            n=n/2;
            mult_mat(m,b,b);
        }
    }
    forr(i,0,m){
        forr(j,0,m){
            fin[i][j]=ans[i][j];
        }
    }
}

int main(){
    bolt;
    ll n,m;
    cin>>n>>m;
    bin[0][0]=1;
    bin[0][m-1]=1;
    for(ll i=1;i<m;i++){
        bin[i][i-1]=1;
    }
    if(n<m){
        cout<<1<<"\n";
    }else{
        ll fin[m+1][100];
        pow_mat(n-m+1,fin,m);
        ll ans=0;
        forr(i,0,m){
            ans+=fin[0][i];
            if(ans>=MOD){
                ans-=MOD;
            }
        }
        cout<<ans<<"\n";
    }
}

1117E - Decypher the String

Tutorial

Solution (BledDest)

#include <bits/stdc++.h>

using namespace std;

int main()
{
	string t;
	cin >> t;
	int n = t.size();
	string s1(n, 'a'), s2(n, 'a'), s3(n, 'a');
	for(int i = 0; i < n; i++)
	{
		s1[i] = char('a' + (i % 26));
		s2[i] = char('a' + ((i / 26) % 26));
		s3[i] = char('a' + ((i / 26 / 26) % 26));
	}
	cout << "? " << s1 << endl;
	string t1;
	cin >> t1;
	cout << "? " << s2 << endl;
	string t2;
	cin >> t2;
	cout << "? " << s3 << endl;
	string t3;
	cin >> t3;
	vector<int> p(n);
	for(int i = 0; i < n; i++)
		p[i] = (t1[i] - 'a') + (t2[i] - 'a') * 26 + (t3[i] - 'a') * 26 * 26;
	string s(n, 'a');
	for(int i = 0; i < n; i++)
		s[p[i]] = t[i];
	cout << "! " << s << endl;
	return 0;
}

1117F - Crisp String

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

const int N = 100 * 1000 + 13;
const int P = 17;

int n, p;
string s;
int A[P][P];
vector<int> pos[P];
int pr[P][N];
bitset<(1 << P)> legal, cur, dp;
int cnt[P];

int main() {
	scanf("%d%d", &n, &p);
	char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, p) forn(j, p)
		scanf("%d", &A[i][j]);
	
	forn(i, n){
		pos[s[i] - 'a'].push_back(i);
		forn(j, p)
			pr[j][i + 1] = pr[j][i] + (s[i] == 'a' + j);
	}
	
	legal.reset();
	legal.flip();
	
	int fl = (1 << p) - 1;
	forn(c, p) forn(d, c + 1){
		if (A[c][d]) continue;
		cur.reset();
		cur.flip();
		int i = 0, j = 0;
		while (i < pos[c].size() && j < pos[d].size()){
			if (c == d && i == j){
				++j;
				continue;
			}
			int mask = 0;
			if (pos[c][i] < pos[d][j]){
				forn(e, p) if ((pr[e][pos[d][j]] - pr[e][pos[c][i] + 1]) != 0)
					mask |= (1 << e);
				++i;
			}
			else{
				forn(e, p) if ((pr[e][pos[c][i]] - pr[e][pos[d][j] + 1]) != 0)
					mask |= (1 << e);
				++j;
			}
			if ((mask >> c) & 1) continue;
			if ((mask >> d) & 1) continue;
			cur[mask ^ fl] = 0;
		}
		for (int mask = fl; mask > 0; --mask){
			if (cur[mask]) continue;
			forn(e, p) if (c != e && d != e && ((mask >> e) & 1))
				cur[mask ^ (1 << e)] = 0;
		}
		legal &= cur;
	}
	
	dp[fl] = 1;
	for (int mask = fl; mask > 0; --mask){
		if (!dp[mask]) continue;
		forn(i, p) if ((mask >> i) & 1){
			int nmask = mask ^ (1 << i);
			if (dp[nmask]) continue;
			dp[nmask] = legal[nmask];
		}
	}
	
	forn(i, n)
		++cnt[s[i] - 'a'];
	
	int ans = n;
	forn(mask, 1 << p) if (dp[mask]){
		int cur = 0;
		forn(i, p) if ((mask >> i) & 1)
			cur += cnt[i];
		ans = min(ans, cur);
	}
	
	printf("%d\n", ans);
	
	return 0;
}

1117G - Recursive Queries

Tutorial

Solution (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<int, int> pt;

int n, q;
vector<int> a;
vector< pair<pt, int> > qs;

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	a.resize(n);
	qs.resize(q);
	
	fore(i, 0, n)
		cin >> a[i];
	fore(i, 0, q) {
		cin >> qs[i].x.x;
		qs[i].x.x--;
	}
	fore(i, 0, q) {
		cin >> qs[i].x.y;
		qs[i].x.y--;
		qs[i].y = i;
	}
	return true;
}

bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) {
	if(a.x.y != b.x.y)
		return a.x.y < b.x.y;
	if(a.x.x != b.x.x)
		return a.x.x < b.x.x;
	return a.y < b.y;
}

typedef pair<li, li> func;
func operator +=(func &a, const func &b) {
	a.x += b.x, a.y += b.y;
	return a;
}

vector<func> t;
void add(int l, int r, const func &f) {
	for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if(l & 1) t[l++] += f;
		if(r & 1) t[--r] += f;
	}
}
func sum(int pos) {
	func ans(0, 0);
	for(pos += n; pos > 0; pos >>= 1)
		ans += t[pos];
	return ans;
}

inline void solve() {
	vector<li> ans(q, 0);
	fore(i, 0, q)
		ans[i] = qs[i].x.y - qs[i].x.x + 1;
	fore(_, 0, 2) {
		vector<int> st;
		vector<int> lf(n, -1);
		fore(i, 0, n) {
			while(!st.empty() && a[st.back()] < a[i])
				st.pop_back();
			if(!st.empty())
				lf[i] = st.back();
			st.push_back(i);
		}
		
		sort(qs.begin(), qs.end(), cmp);
		t.assign(2 * n, {0, 0});
		
		int uk = 0;
		fore(i, 0, n) {
			add(0, lf[i] + 1, {0, i - lf[i] - 1});
			add(lf[i] + 1, i, {-1, i});
			
			while(uk < q && qs[uk].x.y == i) {
				auto f = sum(qs[uk].x.x);
				ans[qs[uk].y] += f.x * qs[uk].x.x + f.y;
				uk++;
			}
		}
		
		reverse(a.begin(), a.end());
		for(auto &p : qs) {
			p.x.x = n - 1 - p.x.x;
			p.x.y = n - 1 - p.x.y;
			swap(p.x.x, p.x.y);
		}
	}
	for(auto v : ans)
		cout << v << ' ';
	cout << endl;
}

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

Comments (59)

Show archived | Write comment?

.anis.

6 years ago, # |

+82

I've solved problem E using Chinese Remainder Theorem (CRT), by asking:

s1 = 'abcd...wxyzabcd...' (string of length n with period 26)
s2 = 'abcd...wxyabcd...' (string of length n with period 25)
s3 = 'abcd...wabcd...' (string of length n with period 23)

you can see more details in 5012664

→ Reply

mohmahkho

6 years ago, # ^ |

such an impressive solution.

tisthepurple

.anis. Can u please explain ur solution? I don't get why u are doing CRT?

Suppose that r[i] be the answer of the testing system to string s[i], then for each position i in given string t, you are looking for its original position, say pos, and we know that from defintion of s[i],

pos = r[1][i] - 'a' (mod 26),
pos = r[2][i] - 'a' (mod 25) and
pos = r[3][i] - 'a' (mod 23).

note that gcd(23, 25) = gcd(25, 26) = gcd(26, 23) = 1.

Varun_Shah

← Rev. 2 →

Ok well I understand what you trying to do. But I don't understand why would just 3 equations be enough for a position?

I mean since, |s| can range upto 10000, each character's occurance can be upto ~400 times.

Can you please give the math behind it?

Thanks in advance :)

rr_

+16

Short answer:

26, 25, 23 are coprime, so there are 26 * 25 * 23 = 129950 possible remainder combinations. 129950 > 10^4, so it's enough.

Long answer:

Let's forget about strings for a moment. Say you have two numbers 2 and 3. What are remainders of dividing numer 0 by those? It's 0 % 2 = 0 and 0 % 3 = 0. We can write it as pair (0, 0). Ok, let's do that for numbers from 0 to 5 and write results:

(0, 0), (1, 1), (0, 2), (1, 0), (0, 1), (1, 2)

You may have already noticed that we have something nice here — all pairs are unique. Why? I will skip this, take this for granted now. If you are interested read more about CRT and ask me if you don't understand, but I think talking about this will diverge too much from the actual problem. What do that gives us? If somebody gives you only those remainders you will be able to determine a numer between 0 and 5 that gives those reminders.

Now it's all about asking string questions in such way that we will get this representation of a numer in remainders. Let's say that n = 5. Your question may look like this:

ababab (we have a cycle of length 2)

abcabc (we have a cycle of length 3)

Ok, so now let's look what you may get at position 0 from first qeustion. If you get an 'a' it had to came from either position 0, 2, or 4. All of those give 0 modulo 2. If you get 'b' then it's either from 1, 3 or 5 — so it's 1 modulo 2. Similar case for the second question, but now you get "second part" of the represantion — that is remainder modulo 3. Let's assume that at position 0 you got 'b' and 'c' respectively. That is (1, 2) in our representation. And that is equal to 5. So the letter had to come from position 5.

You can think of it as successively narrowing set of possible position where the letter came from. In the beginning you know nothing — i.e. possible "sources" of letter are positions {0, 1, 2, 3, 4, 5}. After first question for position 0 you get 'b' so now set becomes {1, 3, 5}. And now, after second question you can say it's 5.

Now to be able to cover strings of length 10^4 you need to pick numbers bigger than just 2 and 3 to be able to identify wheter someting came from position 0 or position 6. If you only ask for remainder modulo 2 and 3 you will get (0, 0) for both 0 and 6 :( But, thankfully 26, 25 and 23 are enough. 26 has, well, 26 possible reaminders, 25 has 25, 23 has 23 so you get 26 * 25 * 23 = 129950 possible triplets. So you can determine numbers from 0 to 129949.

What's also important here is that all those numbers are coprime. Had we used 2 and 4 instead of 2 and 3 we would get:

(0, 0), (1, 1), (0, 2), (1, 3), (0, 0)

So we have our first repetition not after 2 * 4 = 8, but actually after lcm(2, 4) = 4 numbers.

Wow, Thanks a lot.

Unfortunate it is for a user can only give a single upvote.

Don't worry. I like getting likes (oh well, who doesn't :) ), but way more important is that you understood and it turned out that I can be helpful :)

ahshafi

suppose there are more than 1 answer — x1,x2,x3 ... so x1=x2=x3=... (mod N) (as of Chinese Remainder theorem) here N=23*25*26 >10000 ; so only 1 of x1,x2,x3 will be less than N . others will be >N . But given string will never concede N . So an unique answer will be found.

leo7279

I do not understand why we cannot use 2,3 and 5 instead of 26,25 and 23? Is it because the lcm should be greater than size of the string so that we have unique solutions ?

"Is it because the lcm should be greater than size of the string so that we have unique solutions ?"

yes, exactly.

hb11

Can anyone help me with this solution for Problem D? It gives TLE, although I think the complexity should be O(m³ * logn).

Pi-nan

Dont use unnecessary modulo operations.

Thanks a lot!

I just noticed that too. Here is the solution that passed.

interestingLSY

I advise you to change c[r][j]%=mod; to if( c[r][j] >= mod ) c[r][j] -= mod;( in void mult(vvlli& a, vvlli& b) ), in order to run faster. 50233106

That's because mod is much more slower than minus.

sorry for my poor English...

pajenegod

The mult(ll, ll) function he calls in his matrix mult function is super slow, it got 3 modulo operations in it! Just some small modifications to his matrix multiplication function makes his solution go from 2823 ms to 327 ms. I did three changes to the matrix mult.

Used c+=a*b instead of c+=mult(a,b), this removes 3 modulo operations
Changed c%=mod to if (c>=mod*mod) c -= mod*mod, removing one more mod
Changed the order of the for loops, see here.

Thanks a lot. And I read your comment @pajenegod of changing the order of the loops, and the difference was about 200ms (keeping everything else the same), which is quite good. But bringing it down to 327ms is quite brilliant for a solution which started with around 3300ms, with clever modifications.

And I didn't know that mod was this slow than minus. Thanks @interestingLSY as well.

happy15

5 years ago, # ^ |

How is c%=mod equivalent to if (c>=mod*mod) c-=mod*mod?

Take c = mod+mod-1 for example.

4 years ago, # ^ |

The trick of changing loop order does help a little bit.

Good to know, thanks.

_stdout_

-8

About problem D，why we just split the last gem but not the other？Can anyone explain？

RDDCCD

If you want to split front gems , it has been done when calculating front dp values .

Yes,because the last gem has only two states，so it can be classified according to this. Thanks a lot.

denkora

Can anyone explain solution for D in more details? How does matrix exponentiation become solution?

Ahmed_Araby

https://www.youtube.com/watch?v=Tm0KGpoQ5JA&index=22&list=PLPt2dINI2MIY7l5zyFd1W28rei3b-AXaJ

in Arabic

gambler

Bro pls made a video in English

Reziba

+12

http://fusharblog.com/solving-linear-recurrence-for-programming-contest/
A good blog for matrix expo

+40

About matrix multiplication (Problem D).

A while back I found a great trick for speeding up matrix multiplication by a fair bit. When doing matrix multiplication, just change the order of the for-loops (from the usual i,j,k to i,k,j) and you will have much better cache locality. See this.

For example the editorial currently runs in 1014 ms but by just reordering the for loops in the matrix multiplication it takes 826 ms. The same trick also works in for example pypy. It changed the running time from 3.6 s to 2.9 s which made it pass the time limit.

vladalos

For me it just provided a slow down. 1466ms 1637ms Why did this happen?

+11

Great question, this is the first time I've seen a counter example. The reason why it is different for you seems to be because of the way you do the multiplication and addition. You are effectively using a += b*c%mod; if (a>=mod) a-=mod;, but if you change it to a += b*c; a%=mod; it runs quicker and the changed order runs significantly quicker.

Order (i,j,k) with your mult and add: 1466 ms

Order (i,k,j) with your mult and add: 1606 ms

Order (i,j,k) with new mult and add: 1404 ms

Order (i,k,j) with new mult and add: 780 ms

I have no clue why (i,k,j) with your mult and add is so slow (or rather why the other mult add is so much quicker). Maybe someone else knows why this is. There is probably more to this than just cache misses.

Note: One important thing. A 100*100 matrix is pretty small, much of it will probably fit in the L1 cache and all of it in L2. So the real gain will be much more apparent for larger matrix sizes. Take for example 230*230 with your mult/add, that takes around 9.5 s for (i,j,k) and 8.9 s for (i,k,j). Or take this improved version, for 300*300 (i,j,k) takes 5.9 s and (i,k,j) takes 4.5 s.

Thank you, this is an interesting topic. Do you know any other source on internet about this?

xtmosphere

Thank you !

I love this .

Glad you liked it

I've played around further with matrix multiplication mod 10⁹ + 7 in C++, and the best I've been able to get is around 109 ms. My conclusions are the following:

The for loop order is really important, and even more with larger sized matrices.

With unsigned long long you can do 18 additions of numbers of size (10⁹ + 7)² before having to take a modulo. This pretty much cuts down the modulo cost by a factor of 18.

Store matrices as unsigned int. (32 bit is better than 64 bit because of fewer cache misses. Unsigned because it's much quicker to cast unsigned int to unsigned long long than int to unsigned long long)

During multiplication you only temporarily need to store the result in an unsigned long long array, acting as a buffer. See my implementation for details.

These tricks will make a huge difference, especially for larger sized matrices. Try for example running my code with input "1000000000000000000 300" and compare it to other solutions. My code does it in 2.4 s on cf.

Just defer the mod of mul result to the end helps a lot, decreasing from 1200ms(81093813) to 800ms(81094265).

Thanks a again for the tip.

zarif_2002

If I learned matrix exponentiation!!! got stuck after finding dp[n] = dp[n — 1] + dp[n — m]

For D, I found a combinatorics equation which I am sure many of you might have arrived at.

The relation was (summation of (n-k(m-1))C(k)). We need to go about putting different values of k till k <= n-k(m-1). As k increases (n-k(m-1)) would decrease and k would increase. Thus, termination of this process is assured. Now the question is how to solve this summation? I don't know how to proceed further. Can someone please help me with it. Thanks in advance.

pranav.02

17 months ago, # ^ |

Define $$$f(n)= \sum_{r=0}^{\lfloor{n/(m-1)}\rfloor{}}\binom{n-(m-1)\cdot r}{r} $$$ . Using the identity: $$$\binom{n+1}{r+1}=\binom{n}{r}+\binom{n}{r+1}$$$, we can arrive at the recursion: $$$f(n+1)=f(n)+f(n-m+1)$$$ which is same as the dp relation given in the editorial. Submission

saumyadip

In problem C, how is the function on which we are applying binary search a increasing function.In this part |x2-x3| + |y2-y3| <= k , it cannot be a increasing function because it can increase or decrease for different values of x3 & y3. x2 and y2 are destination points. For eg: let x2 = 7 and y2=7 Now initially x3 is 0 and y3 is also 0. x3=0,y3=0; Suppose string is "RLRL" After 1st step, x3 = 1(because first character is R) and y3=0, function value is abs(x2-x3) + abs(y2-y3) = abs(7-1) + abs(7-0) = 6+7 = 13 After 2nd step, x3 = 0(because second character is L) and y3=0, function value is= abs(7-0)+abs(7-0)=14 After 3rd step, x3 = 1(L is third character) and y3=0. function value becomes = abs(7-1)+abs(7-0)=13. After 4th step, x4 = 0, function value will be abs(7-0) + abs(7-0) = 14.

The function is not increasing so how can we apply binary search for this. I have this doubt.

adedalic

The proper function we binary search on is not |x₂ - x₃| + |y₂ - y₃| but f(k) = |x₂ - x₃(k)| + |y₂ - y₃(k)| - k, and I propose that f is non increasing, since |x₂ - x₃(k)| + |y₂ - y₃(k)| will increase no more than by 1 when increasing k by 1. So f(k + 1) ≤ f(k) and we searching minimal k that f(k) ≤ 0.

rj25

I am confused by problem C statement and its editorial. It says we can move in the direction we want and transpoisition add up, but that fact is not used in editorial. What does it mean by if we dont move then only direction of wind counts? Also if all characters of wind direction are same then how can we reach all blocks within Manhattan distance?

mttb90

Let's consider the wind move is wind_mv and the ship move is ship_mv. After k step the ship will move to

(wind_mv_1 + ship_mv_1) + (wind_mv_2 + ship_mv_2) + ... + (wind_mv_k + ship_mv_k)

which is equivalent to

(wind_mv_1 + wind_mv_2 + ... + wind_mv_k) + (ship_mv_1 + ship_mv_2 + ... + ship_mv_k)

Therefore, the ship is moved by the wind to (wind_mv_1 + wind_mv_2 + ... + wind_mv_k), and it can reach to any points that is within k moves from this point (wind_mv_1 + wind_mv_2 + ... + wind_mv_k).

um_farouk

3 months ago, # ^ |

This might seem late but you don't know how greatly you have helped me! I was having a hard time understanding the solution. Orz!

XGptw

2 months ago, # ^ |

krishna_103

unable to understand how binary search is apply in problem C?

Araz.G

generally binary search is applied when you want to find the minimum or maximum of something in a problem, and for this to work you need to make a function called "bool can(int x)" which gets x and tells you if in x days this ship either is on (x2,y2) or not, you should understand that the moment the ship arrives at the destination it can stay there because if the wind is Up then the ship can go down..... so basically the function has a 'x' which all the days smaller than x are false and all the days greater than x are true, so this is a basic binary search problem in which you want to find the minimum x.

And in function "can(int x)" you can check after x days what position the ship will be in if it starts from (x1,y1) and how far it still is from (x2,y2) if using x more moves you could reach your destination then "can" should return true else false, I hope this helps :)

dra2421

well explained

In the author's solution for E, how can we assure that using 3 strings with the mentioned approach will lead to finding the solution?

Upgrading.....

Think when only n = 26, what's approach do you follow? Just sent dustinct characters. Here n> 26, so we sent n distinct pairs. 26² is not good enough to sent 10^4 distinct pairs. Think again.

What do you mean by n distinct pairs? We can send same character multiple times in a string unless the entire triplet for the 3 strings don't match. This is what author means. Please explain if you understand.

OmaeWaMouShenDeiru

Can someone please point the problem with MyCode

The solution to G seems very vague . Can someone give a simpler explanation or at least an insight?

Prakash11

deleted

dalt

5 years ago, # |

Why Problem G give 256mb memory limitation but million input. Is it meaning we can only solve it with such array implementated data structure. I see only one java solution passed test which consumed 240+mb memory, it was nearly failed.

ScarletS

Hi awoo, this link doesn't appear when you look at the contest or any of the problems in it. It would be useful for people using it in the future if you could attach it to the contest :)

4 years ago, # |

can someone please explain problem D

towrist

We can also solve Problem E by the following way:

First, we send a string $$$s1= abcdefgh...xyzabcd...xyz..$$$ of length $$$n$$$ and accept a string $$$t1$$$ from the judge.

For each position $$$j$$$, we get a character, which could have originated from at-most $$$n/26$$$ positions. For each j, we fill all positions cyclically in the same manner as we constructed $$$s1$$$ and send string $$$s2$$$.

Then we accept string $$$t2$$$.

Now, similarly, we have narrowed down the possibilites to $$$n/26^2$$$. We repeat this process again and get string $$$s3$$$, and finally $$$s$$$.

robinz62

Divide and conquer approach for D: Divide input N into two roughly equal halves L and R (L + R = N). Compute the answer recursively on L and R and multiply the numbers together. This accounts for ways of configuring where you don't have any splits that "cross the middle." For configurations that "cross the middle" (only happens when M >= 2) and you iterate over how many from the middle split are in the left half, say i (1 <= i <= M-1). Then there are j = M-i in the right half. For each split, compute recursively on (L-i) and (R-j) and add their product to the sum.

https://codeforces.me/contest/1117/submission/95704249

nichke

3 years ago, # |

I'm having trouble understanding matrix exponentiation transitions in the provided code of problem D. Could somebody explain why we take bin[0][0], bin[0][m — 1] and bin[i][i — 1] as transitions? Shouldn't it be bin[0][0], bin[0][m — 1] and bin[i][i + 1]? (I've watched Errichto's video on matrix exponentiation and perhaps I didn't get the idea right)

Also why do we sum up fin[0][i], for each i as a result? I'm new to matrix exponentiation and would appreciate the help, thanks.

-M1

5 months ago, # |

Can someone plz find anything wrong in my code for C Submission

saurabhGupta2

4 months ago, # ^ |

Check this solution once , not using the prefix sum , just counting each direction by the wind 274162931

awoo's blog