Спасибо за участие в раунде! Надеемся, что задачи вам понравились!
Автор и разработчик yunetive29
2059A - Миля и два массива
Решение
Tutorial is loading...
Реализация
#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 - Стоимость массива
Автор и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#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 - Обслуживание клиентов
Автор и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#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 - Граф и граф
Автор и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#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 - Хватит гамать (простая версия)
Автор shfs и разработчик yunetive29
Хинт 1
Для минимизации количества операций нужно оставить как можно больше элементов в исходном массиве. Что это за элементы?
Хинт 2
Эти элементы должны формировать префикс массива элементов изначально и подпоследовательность конечного массива.
Хинт 3
Какое ещё условие нужно наложить на префикс элементов, чтобы добавлениями можно было получить конечный массив?
Решение
Tutorial is loading...
Реализация
#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 - Хватит гамать (сложная версия)
Автор shfs и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#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;
}
Автокомментарий: текст был обновлен пользователем yunetive29 (предыдущая версия, новая версия, сравнить).
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.
My argument would be djikstra appear frequently in many contests.
I'll also add the solution only differs a little bit from a well known algorithm. bonus points if it doesn't require modification.
I am not sure but I mean it's just a no brainer I guess I can't use the right words
I guess I got it, it's easy.
the Djikstra with a 2D state was just a bit confusing to visualize to me.
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
as honest as bro could get
huge respect for honesty!
Автокомментарий: текст был обновлен пользователем yunetive29 (предыдущая версия, новая версия, сравнить).
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?
I found it very tricky to find an error in my solution. The problem isn't hard, but you need to carefully check your output.
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.
Check out Dominater069 , he also writes with minimal code.
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.
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!!
Solve a lot of 1700-2000 problems, it's the only way. Use the filter in codeforces.
Everyone enjoyed the contest, but i am not. My contest was very bad. I have been feeling very bad for two days. :((
When I saw D and thought about Dijkstra with $$$V = E = 1000000$$$, I thought about doing some kind of "BFS0/1" instead. Then I guessed the distance couldn't be greater than $$$n\times n$$$ (guessed any reachable vertex can be reached in less than n steps, now I think it's actually 2n steps.) and did a BFS with $$$(n+1)\times (n+1) + 1$$$ queues. Hack here if it's wrong -> 304106582
Anyway, $$$O(n\ log\ n)$$$ for $$$n = 1000000$$$ and TL = 2s is the new standard?
A much simpler implementation of E1 304178286
Would you mind explaining your solution?
Explain please
can anyone explain the last sample testcase of E1.
can someone explain how the answer can be 3 for this test (for c problem):
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1
i was thinking of trying e1 before D because of the score distribution,, glad i looked at the number of submissions ,,
In D. Graph and Graph
tutorial: "the number of edges in the new state graph will not exceed m1.m2"
I must be stupid, but please correct me.
The number of edges (E) in the new state graph will be of order 10^3(m1)*10^3(m2) i.e 10^6
The number of vertices (V) will be order n^2((10^3)^2) i.e 10^6.... though we may not visit all vertices here.
But the time complexity of Dijkstra with binary heap is
O(V*(Extract_Min) + E*Decrease_Key) = O(V logV + E log(V))
which here results to (10^6 * log2(10^6) + 10^6 * log2(10^6)) = 2*(10^6 * 20) = 4*10^7
Questions ?
- What am I missing here ?
- How many operations are allowed in 1sec ? if am not wrong is 10^6 simple operations(not %, /)
- How do we calculate time complexity here?
- How many operations are performed here ?
for the first problem, a = [2,2,3] => set of a has {2,3}, size=2; b= [2,2,3] => set of b has {2,3}, size=2; so total size >=4. But the answer is 'NO' only 2+2,2+3 or 2+2, 3+3 are possible. Am I wrong or the solution is wrong