Thank you for participating! We hope you enjoyed our problems
Author and developer is yunetive29
2059A - Milya and Two Arrays
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
int a[55],b[55];
void solve(){
int n;cin>>n;
set<int> sa,sb;
for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);
for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);
if(sa.size()+sb.size()<4){
cout<<"NO\n";
}else{
cout<<"YES\n";
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
2059B - Cost of the Array
Author and developer is yunetive29
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
k /= 2;
vector<int> a(n);
for (auto &it: a) cin >> it;
if (2 * k == n) {
for (int i = 1; i < n; i += 2) {
if (a[i] != (i + 1) / 2) {
cout << (i + 1) / 2 << '\n';
return;
}
}
cout << k + 1 << '\n';
} else {
for (int i = 1; i <= n - 2 * k + 1; i++) {
if (a[i] != 1) {
cout << "1\n";
return;
}
}
cout << "2\n";
}
}
int main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
2059C - Customer Service
Author and developer is yunetive29
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
const int N=305;
int a[N][N],suff[N];
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++){
suff[i]=0;
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
if(a[i][j]!=1)break;
suff[i]++;
}
}
multiset<int> s;
for(int i=1;i<=n;i++){
s.insert(suff[i]);
}
int ans=1;
while(!s.empty()){
int cur=*s.begin();
if(cur>=ans){
ans++;
}
s.extract(cur);
}
cout<<min(ans,n)<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
2059D - Graph and Graph
Author and developer is yunetive29
Solution
Tutorial is loading...
Implementation
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define eb emplace_back
const int INF = 1e18;
void solve() {
int n, s1, s2;
cin >> n >> s1 >> s2;
s1--, s2--;
vector<vector<int>> g1(n), g2(n);
vector<bool> good(n);
set<pair<int, int>> edges;
int m1;
cin >> m1;
for (int i = 0; i < m1; i++) {
int v, u;
cin >> v >> u;
v--, u--;
if (v > u)
swap(v, u);
edges.insert({v, u});
g1[v].eb(u);
g1[u].eb(v);
}
int m2;
cin >> m2;
for (int i = 0; i < m2; i++) {
int v, u;
cin >> v >> u;
v--, u--;
if (v > u)
swap(v, u);
if (edges.find({v, u}) != edges.end())
good[v] = true, good[u] = true;
g2[v].eb(u);
g2[u].eb(v);
}
vector<vector<int>> d(n, vector<int> (n, INF));
d[s1][s2] = 0;
set<pair<int, pair<int, int>>> st;
st.insert({0, {s1, s2}});
while (!st.empty()) {
auto [v, u] = st.begin()->second;
st.erase(st.begin());
for (auto to1 : g1[v]) {
for (auto to2 : g2[u]) {
int w = abs(to1 - to2);
if (d[to1][to2] > d[v][u] + w) {
st.erase({d[to1][to2], {to1, to2}});
d[to1][to2] = d[v][u] + w;
st.insert({d[to1][to2], {to1, to2}});
}
}
}
}
int ans = INF;
for (int i = 0; i < n; i++) {
if (!good[i])
continue;
ans = min(ans, d[i][i]);
}
if (ans == INF)
ans = -1;
cout << ans << '\n';
}
signed main() {
//cout << fixed << setprecision(5);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
//cin >> G;
while (T--)
solve();
return 0;
}
2059E1 - Stop Gaming (Easy Version)
Author shfs and developer is yunetive29
Hint 1
To minimize the number of operations, it is necessary to leave as many elements as possible in the original array. What are these elements?
Hint 2
These elements must form the initial array prefix and the final array subsequence.
Hint 3
What other condition needs to be imposed on the prefix so that additions can be used to obtain the final array?
Solution
Tutorial is loading...
Implementation
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n * m + 1), b(n * m + 1);
vector<deque<int>> mat(n + 1, deque<int> (m));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int ind = j + 1 + (i - 1) * m;
mat[i][j] = ind;
cin >> a[ind];
}
}
for (int i = 1; i <= n * m; i++)
cin >> b[i];
map<int, int> mp;
for (int i = 1; i <= n * m; i++)
mp[b[i]] = i;
vector<int> s(n * m + 1), pos(n * m + 1, -1);
for (int i = 1; i <= n * m; i++) {
if (mp.find(a[i]) != mp.end())
pos[i] = mp[a[i]];
else
break;
}
pos[0] = 0;
int skipped = 0, pref = 0;
bool prev = true;
for (int i = 1; i <= n * m; i++) {
if (pos[i - 1] > pos[i])
break;
int d = pos[i] - pos[i - 1] - 1;
if (prev)
skipped += d;
else if (d > 0)
break;
if (skipped >= m - 1)
prev = true;
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
prev = true;
else
prev = false;
if (prev)
pref = i;
}
cout << n * m - pref << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
2059E2 - Stop Gaming (Hard Version)
Author shfs and developer is yunetive29
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define int long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int INF = 1e9 + 1000;
struct segtree {
vector<pair<int, int>> tree;
vector<int> ass;
int size = 1;
void init(vector<int> &a) {
while (a.size() >= size) {
size <<= 1;
}
tree.assign(2 * size, {});
ass.assign(2 * size, 0);
build(0, 0, size, a);
}
void build(int x, int lx, int rx, vector<int> &a) {
if (rx - lx == 1) {
tree[x].se = lx;
if (lx < a.size()) {
tree[x].fi = a[lx];
} else {
tree[x].fi = INF;
}
return;
}
int m = (lx + rx) / 2;
build(2 * x + 1, lx, m, a);
build(2 * x + 2, m, rx, a);
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
}
void push(int x, int lx, int rx) {
tree[x].fi += ass[x];
if (rx - lx == 1) {
ass[x] = 0;
return;
}
ass[2 * x + 1] += ass[x];
ass[2 * x + 2] += ass[x];
ass[x] = 0;
}
void update(int l, int r, int val, int x, int lx, int rx) {
push(x, lx, rx);
if (l <= lx && rx <= r) {
ass[x] += val;
push(x, lx, rx);
return;
}
if (rx <= l || r <= lx) {
return;
}
int m = (lx + rx) / 2;
update(l, r, val, 2 * x + 1, lx, m);
update(l, r, val, 2 * x + 2, m, rx);
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
}
void update(int l, int r, int val) {
update(l, r + 1, val, 0, 0, size);
}
int req(int x, int lx, int rx) {
push(x, lx, rx);
if (rx - lx == 1) {
return tree[x].se;
}
int m = (lx + rx) / 2;
push(2 * x + 1, lx, m);
push(2 * x + 2, m, rx);
if (tree[2 * x + 2].fi == 0) {
return req(2 * x + 2, m, rx);
} else {
return req(2 * x + 1, lx, m);
}
}
int req() {
return req(0, 0, size);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n * m + 1), b(n * m + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int ind = j + 1 + (i - 1) * m;
cin >> a[ind];
}
}
for (int i = 1; i <= n * m; i++)
cin >> b[i];
map<int, int> mp;
for (int i = 1; i <= n * m; i++)
mp[b[i]] = i;
vector<int> s(n * m + 1), pos(n * m + 1, -1);
for (int i = 1; i <= n * m; i++) {
if (mp.find(a[i]) != mp.end())
pos[i] = mp[a[i]];
else
break;
}
pos[0] = 0;
int skipped = 0, pref = 0;
bool prev = true;
for (int i = 1; i <= n * m; i++) {
if (pos[i - 1] > pos[i])
break;
int d = pos[i] - pos[i - 1] - 1;
if (prev)
skipped += d;
else if (d > 0)
break;
if (skipped >= m - 1)
prev = true;
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
prev = true;
else
prev = false;
if (prev)
pref = i;
}
for (int i = 1; i <= pref; i++) {
s[i - 1] = pos[i] - pos[i - 1] - 1;
}
s[pref] = n * m - pos[pref];
vector<pair<int, int>> ans;
int res = 0;
for (int i = 0; i <= n * m; i++) {
res += s[i];
}
vector<int> ost(pref + 1);
for (int i = 1; i <= pref; i++) {
ost[i] = (m - i % m) % m;
}
for (int i = 0; i <= pref; i++) {
if (s[i] == 0) {
ost[i] = INF;
}
}
vector<int> gol(pref + 1);
gol[0] = 1;
for (int i = 1; i <= pref; i++) {
gol[i] = (i + m - 1) / m + 1;
}
segtree tree;
tree.init(ost);
for (int step = 0; step < res; step++) {
int chel = tree.req();
ans.eb(gol[chel], b[pos[chel] + s[chel]]);
tree.update(chel + 1, pref, -1);
s[chel]--;
if (s[chel] == 0) {
tree.update(chel, chel, INF);
}
}
cout << ans.size() << '\n';
for (auto [i, col] : ans) {
cout << i << " " << col << '\n';
}
}
signed main() {
//cout << fixed << setprecision(5);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
//cin >> G;
while (T--)
solve();
return 0;
}
Auto comment: topic has been updated by yunetive29 (previous revision, new revision, compare).
Wait your released the editorial with code 30 minutes before round ended? That's absurd!?
EDIT: My apologies. I had a gap in my knowledge.
No, that was the time when he started drafting or copy pasted the draft into CF blog.
That's the time the post was created, not posted
Skill Issue. I only solved AD lmao
creative issue? Codeforces usually have some creative problem.
First time i joined Codeforces also struggled with these "creative problem"s
If you mean that I'm creative to solve AD then no because D is standard asf
I mean B,C require some creativity or just familiarity with codeforces problem.
Yeah D is standard, just scary at first read.
Hey can you tell me how is it standard?
Are there any similar problems or blogs on this approach?
Cause it uses djikstra algorithm as the main solution.
Just because a solution uses an algorithm doesn't mean the problem is standard. With that said problem D is pretty standard.
I am not sure but I mean it's just a no brainer I guess I can't use the right words
Any suggestions on how to solve or atleast approach those creative problems?
Try solving easier cases first, usually starts with n=1 after you're comfortable then generalize the solution. If you check my submission you can see how i worked from easier case, though it's not a beautiful submission. 304090629
Try learning some quirks of certain problem, like "n is even", bitwise XOR/AND/OR, MEX. They usually share some similarity in approach.
Practice alot of codeforces problem, if you plan to stay.
Thanks for your suggestions. I cannot understand your quirks point. Do you mean to say that if "n is even", then we can use bitwise XOR/AND/OR, MEX somehow or anything else?
no, many of the creative problem usually have some constraint that may contain hint to solving it.
if n is even:
usually i try to divide the array into 2 parts
or maybe in different question, divide the array into n/2 2-sized sub-array
Spend 1 hours to find a case of ans 3 in B :(
how did you manage to go from 2100 to 1600! concerning.. any advice?
I used to cheat and I can't anymore
I personally felt problem B and C were nice! (even though problem B ruined my contest lol) Simple ideas, yet tricky!
304115975，304141983，304098763 Can someone hack them
I am quite shocked how my B passed the system tests. I was checking for min max in a range but forgot to sort the vector d. I realised this mid contest and was pretty sure it would fail the system tests because I myself can think of countless test cases to hack it. Or is it because of some mathematical property I am missing? Could someone explain?
Is it just me or B is unexpectedly hard today?
good contest , bad contest
Why do people think it was a bad contest? Because D was GPT-able? That is not the problemsetters' fault...
Why do you think it was a good contest? because you performed well?
I didn't perform well. A was acceptable, B was also acceptable, C was good, and D was a bit standard but I enjoyed arriving at the conclusion. E1 was solved by a hundred people and E2 was unsolvable for Div. 2. What exactly is bad about this round?
I think it's because b is harder than c to many people.
And also too few question? (makes my hand sweaty)
Was stuck in reading B for a long time, Couldnt understand what
""such that each element of the array a belongs to exactly one subarray.""
meant Back to Pupil :(
my E1 Solution is much simpler than Tutorial : 304156702
just track the numbers you must push in next array by using queue
I like your template.
Unlike some other template that has 1000 lines just for unused code.
Also smart solution.
For B, I spent 1hour to find a case of which the ans is 3 to hack my wa submisson then I reallized it's impossible :( (I have no enough time to finish C)
Just found out my mistake in E1 :(
I wanna become an expert. I have come close quite a few times but missed the mark by inches. Please suggest some resources so that I'll be able to do Codeforces Div 2 Problem D in upcoming contests.
Thanks in advance!!