Codeforces Round #515 (Div. 3) 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

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	
	for (int i = 0; i < t; ++i) {	
		int L, v, l, r;
		cin >> L >> v >> l >> r;
		cout << L / v - r / v + (l - 1) / v << endl;
	}
	
	return 0;
}

1066B - Heaters

Tutorial

Solution 1


#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, r;
	cin >> n >> r;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	int ans = 0;
	int last = -1;
	while (last < n - 1) {
		int pos = -1;
		for (int i = n - 1; i > max(-1, last - r + 1); --i) {
			if (a[i] == 1 && i - r <= last) {
				pos = i;
				break;
			}
		}
		if (pos == -1) {
			cout << -1 << "\n";
			return 0;
		}
		++ans;
		last = pos + r - 1;
	}
	
	cout << ans << "\n";
	
	return 0;
}

Solution 2

#include <vector>
#include <iostream>

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

using namespace std;

const int N = 2e5;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, r; cin >> n >> r;
	vector<int> a(n);
	vector<int> cnt(n);
	int ans = 0;
	forn(i, n)
        {
            cin >> a[i];
            if (a[i])ans++;
            if (a[i])
                for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
                    cnt[j]++;
        }
    forn(i, n)
        if (!cnt[i])
        {
            cout << -1;
            return 0;
        }
    forn(i, n)
    {
        bool fl = true;
        if (a[i])
            for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
                if (cnt[j] == 1)
                {
                    fl = false;
                    break;
                }
        if (fl && a[i])
        {
            ans--;
            for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
                cnt[j]--;
        }
    }
    cout << ans;

}

1066C - Books Queries

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int M = 200 * 1000 + 11;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	
	vector<int> pos(M);
	int curl = 0;
	int curr = 0;
	
	for (int i = 0; i < q; ++i) {
		string type;
		int id;
		cin >> type >> id;
		if (i == 0) {
			pos[id] = curl;
			--curl;
			++curr;
		} else {
			if (type == "L") {
				pos[id] = curl;
				--curl;
			} else if (type == "R") {
				pos[id] = curr;
				++curr;
			} else {
				cout << min(abs(pos[id] - curl), abs(pos[id] - curr)) - 1 << "\n";
			}
		}
	}
	
	return 0;
}

1066D - Boxes Packing

Tutorial

Solution 1

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

const int MAX = 2e5 + 10;

int ar[MAX];
int n, m, k;

int find(int pos){
    int ans = n - pos + 1;
    int used = 0;
    while(used < m && pos <= n){
        int t = k;
        while(pos <= n && ar[pos] <= t){
            t -= ar[pos++];
        }
        used++;
    }
    return pos == n + 1 ? ans : 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> ar[i];
    }
    int ans = 0;
    int l = 1, r = n;
    while(l <= r){
        int x = (l + r) >> 1;
        if(find(x)){
            ans = max(ans, n - x + 1);
            r = x - 1;
        }else{
            l = x + 1;
        }
    }
    cout << ans << endl;
}

Solution 2

#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];
	}
	
	reverse(a.begin(), a.end());
	int rem = 0;
	for (int i = 0; i < n; ++i) {
		if (rem - a[i] < 0) {
			if (m == 0) {
				cout << i << endl;
				return 0;
			} else {
				--m;
				rem = k - a[i];
			}
		} else {
			rem -= a[i];
		}
	}
	
	cout << n << endl;
	
	return 0;
}

1066E - Binary Numbers AND Sum

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	string s, t;
	cin >> s >> t;
	
	int pw = 1;
	int res = 0;
	int ans = 0;
	
	for (int i = 0; i < m; ++i) {
		if (i < n && s[n - i - 1] == '1') {
			res = add(res, pw);
		}
		if (t[m - i - 1] == '1') {
			ans = add(ans, res);
		}
		pw = add(pw, pw);
	}
	
	cout << ans << endl;
	
	return 0;
}

1066F - Yet another 2D Walking

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

long long dist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	map<int, vector<pair<int, int>>> pts;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		pts[max(x, y)].push_back(make_pair(x, y));
	}
	pts[0].push_back(make_pair(0, 0));
	
	for (auto &it : pts) {
		sort(it.second.begin(), it.second.end(), [&](pair<int, int> a, pair<int, int> &b) {
			if (a.first == b.first)
				return a.second > b.second;
			return a.first < b.first;
		});
	}
	
	vector<vector<long long>> dp(int(pts.size()) + 1, vector<long long>(2, INF64));
	dp[0][0] = dp[0][1] = 0;
	
	int lvl = 0;
	int prv = 0;
	for (auto &it : pts) {
		++lvl;
		
		pair<int, int> curl = it.second[0];
		pair<int, int> curr = it.second.back();
		
		pair<int, int> prvl = pts[prv][0];
		pair<int, int> prvr = pts[prv].back();
		
		dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][0] + dist(prvl, curr) + dist(curl, curr));
		dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][1] + dist(prvr, curr) + dist(curl, curr));
		dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][0] + dist(prvl, curl) + dist(curl, curr));
		dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][1] + dist(prvr, curl) + dist(curl, curr));
		
		prv = it.first;
	}
	
	cout << min(dp[lvl][0], dp[lvl][1]) << endl;
	
	return 0;
}

#include<iostream> #include<algorithm> using namespace std; #define N 1010 int n,r; int a[N]; int main() { cin>>n>>r; for(int i=1;i<=n;i++) { cin>>a[i]; } int ans=0; int last_warmed_pos=0;//初始最后加热点 while(last_warmed_pos<n) { int next_h_pos=-1; //这里这个条件用来限定h的范围//如果在最后加热点右侧没有合适的h 那就只能在其左侧找且不能为上一个所选h for(int i=n;i>=max(0,last_warmed_pos-r+1);i--) { if(a[i]==1&&i-r<=last_warmed_pos)//找到最右端的h使加热范围覆盖进入last_warmed_pos //注意这里的i-r<=last_warmed_pos 所找h的最左未加热部分要确保已加热 //等价于i-r+1<=last_warmed_pos+1 所找h的最左加热起点要小于等于下一个加热点 //而不是i-r+1<=last_warmed_pos 错误！！！ { next_h_pos=i; //cout<<"next h:"<<next_h_pos<<endl; break; } } if(next_h_pos==-1) { ans=-1; break;//找不到符合的h } ans++; last_warmed_pos=next_h_pos+r-1;//更新最后加热点 } cout<<ans<<endl; }

#include<bits/stdc++.h> using namespace std; typedef long long int LL; LL MOD = 998244353; const int N = 524288; double PI = acos(-1); struct comp { double re, im; comp operator*(const comp& a){ comp ret; ret.re = re * a.re - im * a.im; ret.im = re * a.im + im * a.re; return ret; } comp operator+(const comp& a){ comp ret; ret.re = re + a.re; ret.im = im + a.im; return ret; } comp operator-(const comp& a){ comp ret; ret.re = re - a.re; ret.im = im - a.im; return ret; } }; int getord(int x){ int ret = 0; while ((1 << ret) < x) { ret++; } return ret; } comp tmp[N]; comp A[N]; comp B[N]; void fft(comp* ar, int n, int mode) { if (n == 1) return; comp base; base.re = cos(2*PI/n); base.im = sin(2*PI/n); if (mode) base.im *= -1; comp cur; cur.re = 1; cur.im = 0; int dnc = n/2; for (int i = 0; i < dnc; i++) { tmp[i] = ar[i*2 + 1]; } for (int i = 0; i < dnc; i++) { ar[i] = ar[i*2]; } for (int i = 0; i < dnc; i++) { ar[i+dnc] = tmp[i]; } fft(ar, dnc, mode); fft(ar + dnc, dnc, mode); for (int i = 0; i < dnc; i++) { comp ta = ar[i]; comp tb = ar[i+dnc] * cur; ar[i] = ta + tb; ar[i+dnc] = ta - tb; cur = cur * base; } } char str1[200005]; char str2[200005]; int main(){ int n, m; scanf("%d%d", &n, &m); scanf("%s", str1); scanf("%s", str2); int L = (1 << getord(n+m+2)); for (int i = 0; i < L; i++) { A[i].re = A[i].im = 0; B[i].re = B[i].im = 0; } LL mul = 1; for (int i = 0; i < n; i++) { if (str1[n-i-1] == '1') { A[n-i-1 + 1].re = mul; } mul = (mul*2)%MOD; } for (int i = 0; i < m; i++) { if (str2[i] == '1') { B[m-i-1 + 1].re = 1; } } fft(A, L, 0); fft(B, L, 0); for (int i = 0; i < L; i++) { A[i] = A[i] * B[i]; } fft(A, L, 1); LL ans = 0; for (int i = n + 1; i < L; i++) { LL tmp = fmod((A[i].re + 0.5) / L, MOD); ans += tmp; ans %= MOD; } printf("%lld\n", ans); }

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define mem(dp,a) memset(dp,a,sizeof dp) #define rep(i,a,b) for(ll i=a;i<b;i++) #define repb(i,a,b) for(ll i=a;i>=b;i--) #define pb(x) push_back(x) #define sl(a) scanf("%lld",&a) #define si(a) scanf("%d",&a) ll INF=1ll<<60; ll MOD=1000000007; int main() { ll n,k;sl(n);sl(k); ll a[n]; rep(i,0,n) sl(a[i]); ll last=-1; rep(i,0,k) { if(a[i]==1) last=i; } ll c=0,cant=0; if(last!=-1) c=1; else cant=1; while(last+k<n) { ll start=last+1,end=last+2*k; rep(i,start,end) { if(a[i]==1) last=i; } if(last==start-1) { cant=1; break; } else c++; } cant==0 ? cout<<c<<endl : cout<<-1<<endl; }

Comments (30)

Show archived | Write comment?

askfarid

6 years ago, # |

What is the proof for problem E?

→ Reply

r57shell

6 years ago, # ^ |

← Rev. 2 →

First, some easy facts for you:

a = sum of pow(2,ai) where ai is array of unique indexes of 1 in binary representation of a

and b = sum of pow(2,bi) where bi is array of unique indexes of 1 in binary representation of b

pow(2,x) here is 2 raised to the power x

then a&b = sum for i,j of pow(2,ai)&pow(2,bj) where & is bitwise and.

now, imagine you've erased k last bits of b, and result will be sum of pow(2,bi-k), and all elements with bi-k < 0 will just vanish.

so, answer for the problem is: sum for k,i,j of pow(2,ai)&pow(2,bj-k)

ranges for k,i,j think yourself.

other fact, for integers x,y: pow(2,x)&pow(2,y) != 0 if and only if x == y and result is pow(2,x)

so, answer for the problem is: for k,i,j: if ai == bj-k then add to result pow(2,ai)

main observation: you can swap order of "for"s:

then answer for the problem is: for i,j,k: if ai == bj-k then add to result pow(2,ai)

now, ai, bj, k >= 0, then bj >= ai, so you can ignore all others. also, for any bj >= ai, there is k that ai == bj-k, more precisely k = bj-ai. k is basically how many bits you should erase so ai bit from a will match with bj bit from b.

so, answer for the problem is: for i: pow(2,ai)*(count how many bits is 1 at position ai or higher) because any bj >= ai will incorporate in the sum.

you can precalculate count of high bits.

Now all you have to do is calculate recurrently: ans_next = ans_prev*2+count, where count is how many bits is 1 at current position or higher.

This trick works because:

a*8+b*4+c*2+d*1 = (a*4+b*2+c*1)*2+d = ((a*4+b)*2+c)*2+d

You could also first precalculate counts of high bits (count of bits on all prefixes), and then go from backward, and in parallel raising 2 to power ai, but it is more nice to do it recurrently

Thank you! Nice explain

MeePwn

can someone explain why the answer of D's test 4 is 4?

5 4 2

1 2 1 2 1

why it isnt 5?

1 1

harshlunagaria

It is given that we have to go from left to right in sequence.
You cannot change sequence.

NeverGonnaGiveYouUp_

4 years ago, # ^ |

← Rev. 3 →

nbmnb

catforces

Hobody don't speaks, what him algorithm works good and puts maximum things in box.

I want real proof of D. What is in explanation is incomplete. For example fact: if you can fit some sequence in straight order, then you can fit in reverse order. Explanation says that you can go in reverse order in same certain box, and it will still fit. But it doesn't touch the fact that any box may change its content. Then what?

You can prove this fact by considering content after algorithm ran forward. Then, if last box still has space for previous item that is not in the box but next item is in the box, then you can move it to the box (closer to the end). And you can repeat this proccess until space in the box won't fit previous item. So, the box will have exactly same content as if you ran algorithm backward. Now you can do the same for all other boxes running backwards. In the end, you'll get the same result as if you ran algorithm backward. But you was starting from result of algorithm if it ran forward. Q.E.D.

In my opinion this proof is not enough. I don't know how to get proof of continuality from this. In other words: how do you know this: if you can fit starting from i, and you can't fit starting from i-1, then there is no possible j < i-1, that you can fit starting from j. Huh?

vovuh

Is it clear for you that if the last box in the best answer contains some set of objects then the first box in the best answer for the reversed array will contain at least this set of objects and possibly other objects? I think it is clear. So if the first box can contain the same objects let's put these objects in it and go to the next box. In such a way we can construct the same answer as in the straight order. Is it clear now?

Indeed, I'm dumb. I just need apply same fact to best answer. If you can fit best answer forward, then you can fit it backward, and for each step, you can make "forward version" of algorithm for each starting position using algorithm discussed above.

Very nice problem :)

Forget about the previous version of the tutorial. I fixed it and now, I hope, there is more clear proof of this solution.

dragonfire100

Can't solution for problem C be hacked which used linear search for answering 3rd query. A lot of such solutions passed it.

nik1996

Could anybody help me why I am getting wrong answer for Problem C? Submission

ashok123

you have to consider that very first placed book has nothing on left or right..so take that input separately and put 0 distance for it.....and everything else in your solution is right

Kvtubt

In the tutorial for problem F, I think it should be py > qy.

You are right, thank you, fixed

serreja

why p < q in case px = py, if py > qy?

sorry, I understand)

Hemengjie

Could anyone help me solve the problem that my code at the test 10 of problem B get a TLE??? ignore the chinese please!

xdu_lhz

last_warmed_pos do not increase test: 2 1 1 0

Kelly

Can anyone tell me why my FFT gets Wrong Answer on test 3 in problem E? Thanks in advance...

despotovski01

My guess is because of the roundoff error the use of floating-point values induces. Your FFT implementation uses doubles, which are imprecise for large numbers. The solution works on small inputs, but fails on larger ones, for example: https://ideone.com/cdIzUi

Would it be possible for NTT to pass large test cases then?

ramanujan22

How to solve D if those distribution in which there my be no empty space left for some last objects and they are not put in any box is also valid like some continuous subarray can also produce maximum answer no matter it reaches to end or not. Ex: n = 5, m = 1, k = 6, A[i] = (6 2 2 2 6) answer: 3 (from element 2 to 4)

hydra_cody

17 months ago, # ^ |

Anyone, please answer this question? "If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects." If we are able to pack all sets of objects then only it is considered as the answer. Do we have to find the max size set?