Thanks 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;
cout << ((a + b == c || c + a == b || b + c == a) ? "YES\n" : "NO\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[n];
set<int> a;
for(int i = 0; i < n; i++)
{
cin >> x[i];
}
for(int i = 0; i < n; i++)
{
if(a.find(x[i]) != a.end())
{
cout << "NO" << endl;
return;
}
a.insert(x[i]);
}
cout << "YES" << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Bonus
How do you write a validator for this problem? (Given a grid, check if it is a valid input.)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
char g[8][8];
vector<int> r;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
cin >> g[i][j];
if (g[i][j] == 'R') {r.push_back(i);}
}
}
for (int i : r) {
bool ok = true;
for (int j = 0; j < 8; j++) {
if (g[i][j] != 'R') {ok = false; break;}
}
if (ok) {cout << "R\n"; return;}
}
cout << "B\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
vector<int> pairs[1001];
void solve() {
int n; cin >> n;
vector<int> id[1001];
for(int i = 1; i <= n; ++i) {
int x; cin >> x;
id[x].push_back(i);
}
int ans = -1;
for(int i = 1; i <= 1000; ++i) {
for(int j: pairs[i]) {
if(!id[i].empty() && !id[j].empty()) {
ans = max(ans, id[i].back() + id[j].back());
}
}
}
cout << ans << "\n";
}
int32_t main() {
for(int i = 1; i <= 1000; ++i) {
for(int j = 1; j <= 1000; ++j) {
if(__gcd(i, j) == 1) {
pairs[i].push_back(j);
}
}
}
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, q;
cin >> n >> q;
vector<long long> pref;
pref.push_back(0);
vector<int> prefmax;
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
pref.push_back(pref.back()+x);
if(i == 0)
{
prefmax.push_back(x);
}
else
{
prefmax.push_back(max(prefmax.back(), x));
}
}
for(int i = 0; i < q; i++)
{
int k;
cin >> k;
int ind = upper_bound(prefmax.begin(), prefmax.end(), k)-prefmax.begin();
cout << pref[ind] << " ";
}
cout << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}
}
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#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 q; cin >> q;
bool otherA = false, otherB = false;
ll cntA = 0, cntB = 0;
while(q--) {
ll d, k; string x; cin >> d >> k >> x;
for(auto c: x) {
if(d == 1) {
if(c != 'a') otherA = 1;
else cntA += k;
} else {
if(c != 'a') otherB = 1;
else cntB += k;
}
}
if(otherB) {
cout << "YES\n";
} else if(!otherA && cntA < cntB) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#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);
forn(i, n) cin >> a[i];
//we care at most about first log2(a) values
int cur_or = 0;
vector<bool> vis(n, false);
for(int i = 0; i < min(31, n); ++i) {
int mx = 0, idx = -1;
for(int j = 0; j < n; ++j) {
if(vis[j]) continue;
if((cur_or | a[j]) > mx) {
mx = (cur_or | a[j]);
idx = j;
}
}
vis[idx] = true;
cout << a[idx] << " ";
cur_or |= a[idx];
}
forn(i, n) if(!vis[i]) cout << a[i] << " ";
cout << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
B was just a few lines with the help of STL :D (Submission: 176051852)
Nice!
Or
which I find even simpler.
Or directly taking the elements into set and checking if set.size() == n
Problem C,When I judge the horizontal and vertical directions of a color,my submission-->175928516, I can't pass the test. But when I only judge the corresponding direction of a color, it passed,my submission-->176020169 Can someone tell me why
Look at the title,some horizontal rows have been painted red, and some vertical columns have been painted blue.
I also didn't read it properly costed me more than an hour to cause it took more than 15 mins to run on pretests :'(
Consider this case
BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR
Answer : 'R' Output : 'B'
for problem C, many of us missed this case :(
BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR
Answer : 'R' Output : 'B'
I think the answer should be R, as it has the occurrence 8 consecutive times in a row. Please tell, why are there so many messages related to this?????
Because many of us just checked whether the entire row is same color rather than checking entire row is Red Or Not. This also follow for column also.
why is my 176088793 getting WA on 11 (problem D)
when the input array is 2 6 10 15 your output is 0 because when you reach 6 the gcd will be 1 but actually there is no coprime number between 6 , 10 , 15 but it is true that their gcd is 1 The correct output should be 5 by taking 2 and 15
I got TLE in problem E. My submission is 176039360 . How can I improve this?
As per your solution I suggest you to have a read on Time Complexity Analysis It would be helpful for you to understand why your code is getting TLE
I got TLE on Problem D. Not sure why. How can I improve this solution
Instead of keeping track of every index , you can consider the values of the array elements , that can go up to only 10^3 . Now , if you run two for loops , then time taken O(10^3*10^3) and for T=10 test cases , O(10*10^3*10^3) = O(10^7) [neglecting time complexity for __gcd(a,b) stl ].
Video Editorial for Chinese:
Bilibili
Is that Chinese youtube?
YES,and better than YouTube
I think there is an easier way to implement the algorithm in G's tutorial. 176054281
Weak pretest in problem F.
I am getting the Wrong answer for F on test case 2 .. my submission- here
plz someone help me out ::) I got my mistake
sadly, i misread the "OR" as "XOR" and failed to ak
oh bad luck
it's more like oh bad concentration
flamestorm is the solution of bonus of problem C like this :
we go through each row except the ones with full red then check whether if a column is painted blue whether it is painted red in any of the previous rows and if a column is painted red whether it is painted blue in any of the previous rows and if a column is white whether it is painted blue in any of the previous rows; If any of these three happens then input grid is invalid otherwise valid
Is it correct ?
Hey flamestorm,
In problem C, the valid input must contain exactly one of theses situations:
1- Have one or more rows full of R's
2- Have one or more columns full of B's
otherwise, the input is invalid
Is it correct ?
Well, those are a part of the conditions, but there seems to be more invalid cases to consider. The following is one example.
I don't see any reason of downvoting him , he made a correct point.Maybe he has bad record in past in terms of commenting & posting but that doesn't have any relation with this,And why am I saying this? I am saying this because we all make mistakes in life ,doesn't mean we can't move forward
I got TLE in F question for Test Case #2, any ideas/hints how can I improve the code? submission
You need to save the count of every character, as k can be 10^5 every time and there are 10^5 queries the size of the string can exceed 10^10. You can check out my submission : https://codeforces.net/contest/1742/submission/175994173
In problem D I have gotten wrong answer on test 24 on an invalid test int the statement they said that n must be greater than 2 but I have had wrong answer on a test with n=1 so please rejudge the problem SlavicG , mesanu , flamestorm please do something 175973439 .
Help him pleez
Help him, he deserves achieving pupil :(
Agree
Help_Rida
that is not fair, please help him .
it is unfair not to rejudge his submission
totaly agreeee
hiz frendz need mental aid
In $$$C$$$, why didn't they put $$$n$$$ and $$$m$$$ $$$(1$$$ $$$\le$$$ $$$n,m$$$ $$$\le$$$ $$$1000)$$$ or something like that?
I think when $$$n=m=8$$$ problem is more like Div.4 $$$B$$$ problem, this could make problem $$$C$$$ little harder, just as hard as a Div.4 $$$C$$$ should be.
I don't think constraints matter at all in C ,n,m<=1000 doesn't make any difference in solution
In some solutions it actually does matter.
Example: 175929785 from ltunjic
how does it matter? you can just create RRRRR....RRRR string just by appending R m times
Right, but I still think problem would be little harder for beginners.
In Problem B, the checker log is telling me that I gave a wrong answer in test case #2 while my answer is the same as the output. As you can see in the submission, the 25th token is correct. Am I missing something? 176210112
Your code is dereferencing the value of $$$a[n]$$$. This is undefined behaviour, and may have caused a WA any moment.
Have a problem with G
176665365
but the test is really huge and I can catch the problem/
Maybe someone has the idea?
Buddy just ChatGPTed and asked us to rectify it lmao
I guess I didn't understand F correctly...
The is the 10th test:
Official answer is:
YES
YES
YES
YES
YES.
Why it isn't:
YES
NO
YES
NO
YES?
UPD: solved it
251250861 whats wrong with my code it gives the correct output in the editor
For Solution D
We just have to store the value of index to the key of the vector as the for loop is progressing it generally stores the largest index value.
for(int i = 1; i <= n; ++i) { int x; cin >> x; id[x].push_back(i); // we can actually store id[x]=i+1; }