How to solve A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, and Q?
(I'm only curious about N and O, but I might as well ask them all in case others are curious about other problems)
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | orzdevinwang | 3844 |
3 | jqdai0815 | 3682 |
4 | jiangly | 3618 |
5 | Benq | 3529 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3443 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | atcoder_official | 162 |
3 | maomao90 | 162 |
5 | adamant | 158 |
5 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
8 | djm03178 | 154 |
10 | Dominater069 | 153 |
How to solve A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, and Q?
(I'm only curious about N and O, but I might as well ask them all in case others are curious about other problems)
https://mirror.codeforces.com/gyms?searchByNameOrIdQuery=ICPC+World+Final&searchByProblem=false
(Totally relevant waifu pic)
Hello Codeforces! The 14th Stage of the 1st Universal Cup is coming. It will be held from Apr 29th to 30th.
The contest was used in the Osijek Competitive Programming Camp 2023 Winter. If you have solved any problems from the last day of the camp, please skip this round. Teams that participated in the camp can have their camp results included in the final standings.
All problems are authored and prepared by me.
I want to thank
As usual, we have three time windows for participating. You can participate in the contest in the following three time windows:
Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.
Contest link: https://domjudge.qoj.ac/
Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard
About Universal Cup:
Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 500 teams from all over the world registering for Universal Cup.
A more detailed introduction: https://mirror.codeforces.com/blog/entry/111672
Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)
Results of the past stages: https://ucup.ac/results
Terms: https://ucup.ac/terms
Ratings: https://ucup.ac/rating
How to add color to a polygon statement? \color seems to not work :(
I was reading mango_lassi's blog and in one of the paper referred in his blog, I found a $$$O(N^2)$$$ algorithm for constructing a longest k-increasing subsequence (a subsequence of maximum length which is a union of k increasing subsequences). While implementing it, ko_osaga told me about the problem E in "AMPPZ-2015 MIPT-2015 ACM-ICPC Workshop Round 1" (id #6275 in opentrain) where the problem asks to construct such subsequence with constraint $$$N \le 2 \cdot 10^5$$$ and $$$K \le 20$$$.
The official solution runs in $$$O(N \cdot K \cdot (K + \log(N)))$$$. The first half seems to be doing the RSK mapping, but I couldn't figure out why the second half works. It seems to be unrolling the mapping from the back, and maintaining $$$K$$$ intervals for each row in the tableau. And the editorial only explains the first half. Can someone please explain why it works?
#include <stdlib.h>
#include <string.h>
// maksymalna dlugosc jest liczona w czasie O(nklogn),
// pdciagi sa odtwarzane w czasie O(nk(k+logn)).
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cassert>
using namespace std;
const int MAX_N=1000001;
const int MAX_K=20;
int n,k,t[MAX_N],where[MAX_N];
vector<int> s[MAX_K],res[MAX_K];
int final_val[MAX_N],final_level[MAX_N],from[MAX_K][MAX_K],to[MAX_K][MAX_K];
bool taken[MAX_N];
int main(){
scanf("%d %d",&n,&k);
assert(1<=n&&n<=MAX_N);
assert(1<=k&&k<=MAX_K);
for(int i=1;i<=n;i++){
taken[i]=false;
}
for(int i=0;i<n;i++){
scanf("%d",&t[i]);
assert(1<=t[i]&&t[i]<=n);
assert(!taken[t[i]]);
taken[t[i]]=true;
where[t[i]]=i;
}
for(int i=0;i<n;i++){
int j=0,val=t[i];
while(j<k){
vector<int>::iterator it=lower_bound(s[j].begin(),s[j].end(),val);
if(it==s[j].end()){
final_level[i]=j;
final_val[i]=val;
s[j].push_back(val);
break;
}
swap(*it,val);
++j;
}
if(j==k){
final_level[i]=k;
final_val[i]=val;
}
}
int ans=0;
for(int i=0;i<k;i++){
ans+=s[i].size();
}
printf("%d\n",ans);
for(int i=0;i<k;i++){
for(int j=0;j<i;j++){
from[i][j]=0;
to[i][j]=0;
}
from[i][i]=0;
to[i][i]=s[i].size();
for(int j=i+1;j<k;j++){
from[i][j]=s[i].size();
to[i][j]=s[i].size();
}
}
for(int i=n-1;i>=0;i--){
int j=final_level[i],val=final_val[i],subsequence;
if(j<k){
subsequence=0;
while(subsequence<k&&(to[j][subsequence]<s[j].size()||from[j][subsequence]>=s[j].size())){
++subsequence;
}
s[j].pop_back();
for(int z=0;z<k;z++){
from[j][z]=min(from[j][z],(int)s[j].size());
to[j][z]=min(to[j][z],(int)s[j].size());
}
}else{
subsequence=k;
}
while(j>0){
--j;
int pos=lower_bound(s[j].begin(),s[j].end(),val)-s[j].begin()-1;
int val2=s[j][pos],subsequence2=0;
while(subsequence2<k&&(to[j][subsequence2]<=pos||from[j][subsequence2]>pos)){
++subsequence2;
}
if(subsequence<k&&subsequence2==k){
if(from[j][subsequence]==to[j][subsequence]){
from[j][subsequence]=pos;
to[j][subsequence]=pos+1;
}else{
assert(from[j][subsequence]>pos);
for(int z=0;z<k;z++)if(from[j][z]>pos&&to[j][z]<=from[j][subsequence]){
from[j][z]=pos;
to[j][z]=pos;
}
from[j][subsequence]=pos;
}
subsequence=k;
}else if(subsequence==k&&subsequence2<k){
if(to[j][subsequence2]>pos+1){
subsequence=k;
}else{
--to[j][subsequence2];
subsequence=subsequence2;
}
}else if(subsequence<k&&subsequence2<k){
if(from[j][subsequence]<to[j][subsequence]){
assert(from[j][subsequence]>=to[j][subsequence2]);
for(int z=0;z<k;z++)if(from[j][z]>=to[j][subsequence2]&&to[j][z]<=from[j][subsequence]){
from[j][z]=pos;
to[j][z]=pos;
}
from[j][subsequence]=pos;
to[j][subsequence2]=pos;
subsequence=subsequence2;
}else{
if(to[j][subsequence2]>pos+1){
from[j][subsequence]=pos;
to[j][subsequence]=to[j][subsequence2];
for(int z=j-1;z>=0;z--){
swap(from[z][subsequence],from[z][subsequence2]);
swap(to[z][subsequence],to[z][subsequence2]);
}
swap(res[subsequence],res[subsequence2]);
to[j][subsequence2]=pos;
subsequence=subsequence2;
}else{
from[j][subsequence]=pos;
to[j][subsequence]=pos+1;
--to[j][subsequence2];
subsequence=subsequence2;
}
}
}
s[j][pos]=val;
val=val2;
}
assert(val==t[i]);
if(subsequence<k){
if(!res[subsequence].empty())assert(val<res[subsequence].back());
res[subsequence].push_back(val);
}
}
for(int j=0;j<k;j++){
reverse(res[j].begin(),res[j].end());
printf("%d",(int)res[j].size());
for(int i=0;i<res[j].size();i++){
printf(" %d",res[j][i]);
if(i){
assert(res[j][i-1]<res[j][i]);
assert(where[res[j][i-1]]<where[res[j][i]]);
}
--ans;
}
printf("\n");
res[j].clear();
}
assert(!ans);
return 0;
}
All my recent round experiences are like "code -> code -> code -> ... -> code contest ends".
I think it won't hurt to increase the default contest duration to 3h so that we can have some time to think about harder problems.
Any thoughts?
(Mendatory Waifu Pic)
Not sure if this has been mentioned before, but the following code involving std::inclusive_scan doesn't compile on CF on both "GNU G++17 7.3.0" and "GNU G++17 9.2.0 (64bit, msys 2)". This function is part of the C++17 standard, according to the reference, so it should compile on both versions (and it does compile locally).
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> a{0, 1, 2, 3, 4, 5};
vector<long long> pref{0};
inclusive_scan(a.begin(), a.end(), back_inserter(pref), plus<>(), 0LL);
return 0;
}
std::exclusive_scan doesn't compile on CF as well.
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> a{0, 1, 2, 3, 4, 5};
vector<long long> pref{0};
exclusive_scan(a.begin(), a.end(), back_inserter(pref), 0LL, plus<>());
return 0;
}
I was solving the string section problems from Brazilian summer camp 2018, and there were following problems:
You are given z-function of some (unknown for you) string s, write prefix-function of the string s.
You are given prefix-function of some (unknown for you) string s, write z-function of the string s.
I thought that if these were solvable, just storing all the equality information would suffice on both problems, and they indeed got AC (Code below). But I have no clue how to prove either of these, and I couldn't find the editorial on google.
Can someone tell me how to prove these?
struct disjoint_set{
vector<int> p;
disjoint_set(int n): p(n, -1){ }
bool share(int a, int b){ return root(a) == root(b); }
int sz(int u){ return -p[root(u)]; }
int root(int u){ return p[u] < 0 ? u : p[u] = root(p[u]); } // O(alpha(n))
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(ios::badbit | ios::failbit);
int n;
cin >> n;
vector<int> z(n);
for(auto i = 0; i < n; ++ i) cin >> z[i];
disjoint_set dsu(n);
for(auto i = 1, j = 0; i < n; ++ i){
int zi = 0;
if(i < j + z[j]) zi = min(j + z[j] - i, z[i - j]);
while(zi < z[i]) dsu.merge(zi, i + zi), ++ zi;
if(i + z[i] > j + z[j]) j = i;
}
vector<int> pi(n);
for(auto i = 1; i < n; ++ i){
int len = pi[i - 1];
while(len && !dsu.share(i, len)) len = pi[len - 1];
if(dsu.share(i, len)) pi[i] = len + 1;
}
for(auto x: pi) cout << x << " ";
cout << "\n";
return 0;
}
struct disjoint_set{
vector<int> p;
disjoint_set(int n): p(n, -1){ }
bool share(int a, int b){ return root(a) == root(b); }
int sz(int u){ return -p[root(u)]; }
int root(int u){ return p[u] < 0 ? u : p[u] = root(p[u]); } // O(alpha(n))
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(ios::badbit | ios::failbit);
int n;
cin >> n;
vector<int> pi(n);
for(auto i = 0; i < n; ++ i) cin >> pi[i];
disjoint_set dsu(n);
for(auto i = 1; i < n; ++ i) if(pi[i]) dsu.merge(i, pi[i] - 1);
vector<int> z(n);
for(auto i = 1, j = 0; i < n; ++ i){
if(i < j + z[j]) z[i] = min(j + z[j] - i, z[i - j]);
while(i + z[i] < n && dsu.share(z[i], i + z[i])) ++ z[i];
if(i + z[i] > j + z[j]) j = i;
}
for(auto x: z) cout << x << " ";
cout << "\n";
return 0;
}
Name |
---|