Thank you for participating!
Idea: flamestorm
Tutorial
Tutorial is loading...
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();
}
Idea: mesanu
Tutorial
Tutorial is loading...
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();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
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();
}
Idea: SlavicG
Tutorial
Tutorial is loading...
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;
}
}
}
}
Idea: SlavicG
Tutorial
Tutorial is loading...
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;
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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();
}
}
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?
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
Hey.
Following is my code: https://codeforces.com/contest/1807/submission/198491679
Its failing for test case 2 token 391. Expected '3' found '4'.
What could be the reason for the same? I tried some random cases but my output is coming correct for all the cases. Can't figure out.
Thanks.
because you're only a specialist
How does that relate to my comment's content?
im upvoting you but it is not taking the vote
Shouldn't be 4*n*m states cause tle according to constraints?
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.
Shouldn't be 4*n*m states cause tle according to constraints?
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).
i just wrote a long one bfs https://codeforces.com/contest/1807/submission/198385698
How did the next direction calculated in the problem F?
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:
Try this for each direction.
Submission: 198396729
Yes Or No Forces
My first fully solved contest
Another opportunity to feel ashamed....!!!
What is the proof for $$$\text{states} \leq 2mn$$$ in problem F?
Think of the grid as a chessboard — you always stay on squares of the same colour.
What about points where two lines (or edges) intersect? Those points can have all 4 directions?
Edit: Okay it works out. We have $$$\frac{mn}{2}$$$ white/black squares. If we start at a colour we stay on it. Each cell at max can have 4 directions so it becomes $$$4 \cdot \frac{mn}{2}=2mn$$$
How to solve in 2 mn states
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?
Practice is the key
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!
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.
hey there are 2 solutions of this problem, the one given in tutorial is relatively tough to understand. u can see this solution [https://codeforces.com/contest/1807/submission/198847704]
Well, after practicing reasonably you will start to get the intuition to approach a problem, that intuition can be wrong or right. To check whether you are on right track you should think about the idea of intuition and prove it mathematically or intuitively. Coming back to your question. Yes, we rely on our intuition. But along with that, we prove our solution too.
true
I came up to the solution remembering almost the same problem from CSES problem set. So practice indeed helps.
i got it.
Prefix-Sum forces
I'd say this was harder than an average div 4
how can we do the G1 using the memoization technique in dp instead of tabulation
I am not able to write the memoization code
Can anyone help?
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.
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.
I solved F in O(n+m) xD!
In the D problem, can anybody explain to me what is the 'prefix sums technique' and how is it being implemented here?
The prefix sums allows you to build an array $$$\texttt{pre}$$$ where $$$\texttt{pre}[i] = \sum_{j=0}^{i} a[j]$$$. In the problem, you are given a segment $$$[l, k]$$$. We want to subtract out $$$\sum_{j=l}^{r} a[j]$$$ and add $$$(r - l + 1) \cdot k$$$. To find the amount we want to subtract, observe that it is simply $$$\texttt{pre}[r] - \texttt{pre}[l-1]$$$.
I am very excited for the next div4 contest to be unrated for me.
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.
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)
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?
"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
Can anyone tell me why I'm getting an idleness error in test 3? PROBLEM LINK: https://codeforces.com/contest/1807/problem/E
include <bits/stdc++.h>
using namespace std;
define ll long long
void solve() { int test; cin >> test; while (test--) { int n; cin >> n; vector v(n + 1); for (int i = 1; i <= n; i++) { cin >> v[i]; } int x = 30; int start = 1, end = (n + 1) / 2; if (n == 1) { cout << "! 1" << "\n" << flush; continue; } while (x--) {
} // solve end int main() {
}
Can anyone tell what's the mistake in my code.Problem G1 Test case 2 : wrong answer expected NO, found YES [265th token]
submission id: https://codeforces.com/problemset/submission/1807/199620687
1807D - Odd Queries Getting TLE
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)$$$.