Codeforces Round #859 (Div. 4) Editorial

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Thank you for participating!

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b == c) {cout << "+\n";}
	else {cout << "-\n";}	
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1807B - Grab the Candies

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    int x, odd = 0, even = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        if(x%2 == 0)
        {
            even+=x;
        }
        else
        {
            odd+=x;
        }
    }
    if(even > odd)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1807C - Find and Replace

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int mp[26];
	for (int i = 0; i < 26; i++) {
		mp[i] = -1;
	}
	for (int i = 0; i < n; i++) {
		int curr = (s[i] - 'a');
		if (mp[curr] == -1) {
			mp[curr] = (i % 2);
		}
		else {
			if (mp[curr] != (i % 2)) {cout << "NO\n"; return;}
		}
	}
	cout << "YES\n";
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1807D - Odd Queries

Idea: SlavicG

Tutorial

Solution

#include <iostream>
 
using namespace std;
long long n,a[200005],q,sum=0,pref[200005],t;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--)
    {
        sum = 0;
        cin >> n >> q;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            sum+=a[i];
            pref[i]=pref[i-1];
            pref[i]+=a[i];
        }
        for(int i = 0; i < q; i++){
            long long l,r,k;
            cin >> l >> r >> k;
            long long ans = pref[n]-(pref[r]-pref[l-1])+k*(r-l+1);
            if(ans%2==1){
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
    }
}

1807E - Interview

Idea: SlavicG

Tutorial

Solution

#include <bits/stdc++.h>
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll t,n,a[2000005],pref[2000005];
int32_t main(){
//CODE_START;
#ifdef LOCAL
//ifstream cin("input.txt");
#endif
cin>>t;
while(t--){
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
    }
    ll l=1,r=n,ans=0;
    while(l<=r){
            ll mid=(l+r)/2;
        cout<<"? "<<(mid-l+1)<<' ';
        for(ll i=l;i<=mid;i++)
        {
            cout<<i<<' ';
        }
        cout<<endl<<flush;
        ll x=0;
        cin>>x;
        if(x==pref[mid]-pref[l-1]){
            l=mid+1;
        }else {
            r=mid-1;
            ans=mid;
        }
    }
    cout<<"! "<<ans<<endl<<flush;
}
}

1807F - Bouncy Ball

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n, m, x1, y1, x2, y2;
    string d_string;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    x1--;x2--;y1--;y2--;
    cin >> d_string;
    int d = (d_string[0] == 'U' ? 1+(d_string[1] == 'R' ? 2 : 0) : 0+(d_string[1] == 'R' ? 2 : 0));
    bool vis[n][m][4];
    memset(vis, false, sizeof(vis));
    int i = x1, j = y1;
    int bounces = 0;
    while(!vis[i][j][d])
    {
        if(i == x2 && j == y2){cout << bounces << endl; return;}
        int na = 0;
        if(d%2 == 1 && i == 0){d-=1;na++;}
        if(d%2 == 0 && i == n-1){d+=1;na++;}
        if(d >= 2 && j == m-1){d-=2;na++;}
        if(d < 2 && j == 0){d+=2;na++;}
        bounces+=min(1, na);
        if(vis[i][j][d])
        {
            break;
        }
        vis[i][j][d] = true;
        if(d%2 == 1){i--;}else{i++;}
        if(d >= 2){j++;}else{j--;}
    }
    cout << -1 << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1807G1 - Subsequence Addition (Easy Version)

Idea: flamestorm

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    if(a[0] != 1) {
        cout << "NO\n";
        return;
    }
    vector<int> dp(5005, 0);
    dp[1] = 1;
    for(int i = 1; i < n; ++i) {
        if(!dp[a[i]]) {
            cout << "NO\n";
            return;
        }
        for(int j = 5000; j >= a[i]; --j) {
            dp[j] |= dp[j - a[i]];
        }
    }
    cout << "YES\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1807G2 - Subsequence Addition (Hard Version)

Idea: flamestorm

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    if(a[0] != 1) {
        cout << "NO\n";
        return;
    }
    long long sum = a[0];
    for(int i = 1; i < n; ++i) {
        if(sum < a[i]) {
            cout << "NO\n";
            return;
        }
        sum += a[i];
    }
    cout << "YES\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

bool flag = true; sort(arr.begin(), arr.end()); vector<int> dp(5001, 0); dp[1] = 1; if(arr[0] != 1) { flag = false; } if(flag) { for(int i = 1; i < n; i++) { if(dp[arr[i]] != 1) { flag = false; break; } //If arr[i] is possible, then all dp[j] which is true, then dp[j + arr[i]] //should also be possible ryt? for(int j = 0; j <= 5000; j++) { if(dp[j]) { if(j + arr[i] <= 5000) dp[j + arr[i]] = 1; } } } }

for _ in range(int(input())): n, q = map(int, input().split()) a = [int(x) for x in input().split()] sum_of_a = sum(a) for _ in range(q): l, r, k = map(int, input().split()) ans = sum_of_a - sum(a[l-1:r]) + ((r - l + 1) * k) print("NO" if (ans % 2 == 0) else "YES")

Comments (43)

Show archived | Write comment?

bit-trie

13 months ago, # |

← Rev. 2 →

It will be good if there exists some more explanation of F. Bouncy Ball Problem.

I am still not able to simulate the movement of ball.

Can anybody else explain it to me?

→ Reply

Miyano_Shiho

13 months ago, # ^ |

← Rev. 4 →

For changing the direction, you just have to make sure that if the ball continues going in this certain direction on the x axis or y axis, it WILL go out of the boundaries (for example the column index is m and the second character is 'R'). In this case you just flip 'R' to 'L' or vice versa as needed, same for 'D' and 'U'. This automatically handles the corner case too.

Then you make the ball go in the updated direction until it either reaches the desired cell, or starts the loop all over again (in which case the answer will be -1).

Submission: 198207442

Abito

because you're only a specialist

Shouldn't be 4*n*m states cause tle according to constraints?

Shady_Mo

If you hit the right wall, Definitely you will change direction R to L but to know you will move U or D you must know where you are coming from if you coming from U you will change it to D and vice versa.

And do this if you hit the left, up, or down wall.

If you hit any vertex you will change both of two directions.

I hope you understand xD.

No, read the input again and you will notice that he is write (It is guaranteed that the sum of n * m over all test cases does not exceed 5 * 10 ^ 4).

So, 4 * n * m = 20 * 10 ^ 4 (in the worst case).

tareqrahaman565

7 months ago, # ^ |

Great

Hasan__Zia

-9

How did the next direction calculated in the problem F?

sahaun

For each direction, think about how you can transition to other directions.

Let's say the ball is at $$$(r,c)$$$ with direction $$$DR$$$. There are 3 possibilities:

It hits the corner, $$$r=n$$$ and $$$c=m$$$: Change direction to $$$UL$$$.
It hits the bottom first, $$$r=n$$$ and $$$c<m$$$: Change direction to $$$UR$$$.
It hits the side first, $$$r<n$$$ and $$$c=m$$$: Change direction to $$$DL$$$.

Try this for each direction.

Submission: 198396729

OmarAnalog

Yes Or No Forces

ayush002024

Another opportunity to feel ashamed....!!!

knoothopian

What is the proof for $$$\text{states} \leq 2mn$$$ in problem F?

gardengnome

Think of the grid as a chessboard — you always stay on squares of the same colour.

kolmogorov

How do you come up with the solution of G2? Can some experienced people tell me? I tried a lot to solve that problem but was not able to. I read the codes of some AC solutions after the contest but was not able to understand why that worked. Only after reading the editorial, I understood the solution. The people who solved it, did you prove the solution using induction during the contest? How do I develop this skill?

par4dox

Spoiler

But did you prove the solution using induction? Or did you rely on intuition?

yes after submitting the solution but its bad practice to rely on just intuition I would recommend you to prove it as well it improves accuracy and build foundation.

Wow man, I could not prove the solution even after seeing the AC solutions. I really need to practice!

NekoYellow

G2 is simply a greedy problem, and you will be able to detect it after working on enough similar problems. It's a matter of familiarity, while some describe it as intuition. (After all, G is a relatively basic problem.)

Man, yesterday the whole night and even today morning I was still thinking about the solution of this problem. It's marvelous that people find it basic. I need to buckle up and practice.

Yeah I understand you. We (most of us) all came from that phase. Just keep practicing and you will find yourself improved.

Jack_sparrow_06

11 months ago, # ^ |

Could you explain the solution for the problem 1807G1 - Subsequence Addition (Easy Version). I tried nearly for half a day and not able to solve it. Could you please tell the step by step solution from the recursion to dp?

My code :

I am getting wrong answer :(

I just worked on your method. The problem lies in the j loop: the bound should be the prefix sum instead of 5000. Check this out: https://codeforces.com/contest/1807/submission/209104779 Feel free to ask me if you have further questions!

Could you explain why you are using that presum variable??

Let's say you got a=[1,1,2,5]. In your implementation, when visiting a[1], when j=1, dp[2] is set to 1; when j=2, dp[3] is set to 1, and so on. Finally, dp[2..5000] is all set to 1, so when you visit a[3] then, you will get dp[a[3]] = 1, but actually you cannot get 5 from the subarray [1,1,2], resulting in wa.

So instead of iterating j from 1 to 5000, you should iterate it from 1 to the prefix sum, so that it will not set values you cannot achieve to 1.

P.S. Whenever your feel confusing, you can print some variables in the process to check if your code acts as you expected.

Thankyou so much for you time and explanation, it helped me to understand the problem that I had doing.

copyPasteCoder

4 weeks ago, # ^ |

from cses problemset

smokebellew

I came up to the solution remembering almost the same problem from CSES problem set. So practice indeed helps.

LongMystic

problem F why they set vis[n][m][4], i think the ball only vis a pair (x, y) at most 2 times

Easier implementation.

012199

Can any one tell me why my solution 198576200 got tle on test 23. Why not this submission got tle 198142369. I just wanted to know the reason. Thanks in Advance.

aopo

I solved F in O(n+m) xD!

MR.JO

I am very excited for the next div4 contest to be unrated for me.

WORTH

This might be a dumb doubt, but shouldn't the time complexity of E be $$$O(n*log(n))$$$? I mean we are also printing numbers in each query.

Dominater069

replying to a 9 days old comment, but here is your answer.

Its actually O(n) because you are printing n numbers at first, then n/2, then n/4 and so on....

and we know n + n/2 + n/4 + .... (infinite sum) = 2 * n

so the finite sum is between n operations and 2 * n operations, hence its O(n)

hipereg

For problem F, I didn't consider the approach of creating a matrix, such as bool vis[n][m][4] from solution, because I thought it would go over 1GB of memory (25000x25000x4 x 1 byte).

Since this wasn't the case, can someone point me out why?

gabriel88766

"It is guaranteed that the sum of $$$n*m$$$ over all test cases does not exceed $$$5*10^4$$$"

So you can conclude that $$$n*m$$$ is at most $$$5*10^4$$$. You can create that matrix accordingly with the input, vector<vector<vector<bool>>> v(n, vector<vector<bool>> (m, vector<bool>(4, false)));

I don't know if this code above is the best way to do it, but It seems to work good

oddd

1807D - Odd Queries Getting TLE

passwordisa

You are summing the values in the specified range for each query, so your runtime is $$$O(nq)$$$. You can instead use a prefix sum to get the sum of values in any range of the array in $$$O(1)$$$.

Naruto_Datttebayo

10 months ago, # |

In the problem E Why we are subtracted pref[mid]-pref[l-1]

Instead of this why we can't use only pref[mid] ??? Can anybody explain to me ??

Tagl

10 months ago, # ^ |

Because as you binary search, the value of $$$l$$$ changes, so you are not always summing from the start of the array. You want to compute the sum from index $$$l$$$ to index $$$r$$$ quickly so you can use the prefix sum array since $$$\sum_{i=l}^{r} A_i = \sum_{i=0}^{r} A_i - \sum_{i=0}^{l-1} A_i$$$.

Md-Merazul-Islam

4 months ago, # |

count odd and even num and check it

mesanu's blog