Tutorial
Tutorial is loading...
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;
}
Tutorial
Tutorial is loading...
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;
}
Tutorial
Tutorial is loading...
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;
}
Tutorial
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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;
}
What is the proof for problem E?
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
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
2
2
1
It is given that we have to go from left to right in sequence.
You cannot change sequence.
nbmnb
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?
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.
Can't solution for problem C be hacked which used linear search for answering 3rd query. A lot of such solutions passed it.
Could anybody help me why I am getting wrong answer for Problem C? Submission
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
In the tutorial for problem F, I think it should be py > qy.
You are right, thank you, fixed
why p < q in case px = py, if py > qy?
sorry, I understand)
Could anyone help me solve the problem that my code at the test 10 of problem B get a TLE??? ignore the chinese please!
last_warmed_pos do not increase test: 2 1 1 0
Can anyone tell me why my FFT gets Wrong Answer on test 3 in problem E? Thanks in advance...
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?
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)
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?
Clean implementations, really loved it <3
Can anyone please find a bug in my problem B code.....
44389702
Its giving runtime error on test case 5
I am getting wrong on 4rth test case of F problem Please help if anyone knows the problem here is my code for the same
http://codeforces.net/contest/1066/submission/44486589
Thanks in advance
I've solved B using DP 55118824
I solved A using DP
(Necroposting). But, is the note for the 2nd test case correct? The distribution in the cases should be [4], [2], [3] and [4], not just [4].