Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

physics0523's blog

How to blow up too weak hashing without thinking

By physics0523, history, 7 months ago, In English

Sadly, until today, many people use single $$$\rm{mod} = 10^9+7$$$ or so on for hashing, so why not write how to blow up them easily, with minimized thinking process?

The key idea is simple. Just use Birthday attack.

Write a function to calculate the hash value
Write a random generator of string
When there are $$$k$$$ possible distinct hash values, look up $$$O(\sqrt{k})$$$ random candidates
Now we get a pair of strings that has exactly the same hash value!

In this method, the only things we should consider are that $$$k$$$ is small enough (around $$$k \le 10^{12}$$$ ), and the number of possible candidates is large enough. We don't need to care about what the hashing function is!

Example Code(C++)

#include<bits/stdc++.h>

using namespace std;

unsigned long long xor128(){
  static unsigned long long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

long long mod=1000000007;
long long base=31;

long long calcHash(string &s){
  long long h=0;
  for(auto &nx : s){
    h*=base; h%=mod;
    h+=(nx-'a'); h%=mod;
  }
  return h;
}

string randGenStr(){
  long long len=20;
  string res;
  for(long long i=0;i<len;i++){
    res.push_back('a'+xor128()%26);
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  map<long long,string> mp;
  while(1){
    string cs=randGenStr();
    long long ch=calcHash(cs);
    if(mp.find(ch)==mp.end()){
      mp[ch]=cs;
    }
    else if(mp[ch]!=cs){
      cout << mp[ch] << "\n";
      cout << cs << "\n";
      break;
    }
  }
  return 0;
}

Exercise:
Find two $$$18$$$-digit integers $$$x,y$$$ such that:

Each digit of $$$x,y$$$ are $$$1,3,5,7,9$$$
$$$x \equiv y \mod 998244353$$$

Short Explanation

Example Code(C++)

#include<bits/stdc++.h>

using namespace std;

unsigned long long xor128(){
  static unsigned long long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

long long mod=998244353;
long long base=10;

long long calcHash(string &s){
  long long h=0;
  for(auto &nx : s){
    h*=base; h%=mod;
    h+=(nx-'0'); h%=mod;
  }
  return h;
}

string randGenStr(){
  long long len=18;
  string res;
  for(long long i=0;i<len;i++){
    res.push_back('1'+2*(xor128()%5));
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  map<long long,string> mp;
  while(1){
    string cs=randGenStr();
    long long ch=calcHash(cs);
    if(mp.find(ch)==mp.end()){
      mp[ch]=cs;
    }
    else if(mp[ch]!=cs){
      cout << mp[ch] << "\n";
      cout << cs << "\n";
      break;
    }
  }
  return 0;
}

... then how to avoid attacking?

Full text and comments »

+159

physics0523
7 months ago
42

TheForces Round #27 Editorial

By physics0523, history, 11 months ago, In English

104855A - GCD,LCM and AVG

Editorial

Rate the problem

104855B - Yugandhar's Letter for Diya

Editorial

Rate the problem

104855C - Hungry Shark

Editorial

Rate the problem

104855D - Colorful Paths

Editorial

Rate the problem

104855E - Perfect Permutation

Editorial

Rate the problem

104855F - Regular Covering

Editorial

For ease of discussion, let $$$P$$$ be the polygon and $$$s$$$ be the size of $$$P$$$. All angles and rotations are described using radian.

Let $$$d_i$$$ be the euclidean distance from $$$(0,0)$$$ to $$$a_i$$$ and $$$\theta_i$$$ be how far you have to rotate $$$a_i$$$ clockwise with the center being $$$(0,0)$$$ such that the point lies on the non-negative side of the $$$x$$$ axis.

Observation 1. Let the minimum value of $$$s$$$ such that $$$P$$$ covers all points be $$$k$$$. Notice that if $$$s \geq k$$$, we can just scale up $$$P$$$ in its optimal positioning by $$$\frac{s}{k}$$$ and it will still covers all points. And with the definition of $$$k$$$, for all values $$$s < k$$$, there must be at least one point such that it is not covered no matter how you arrange $$$P$$$. Thus, we can do BSTA (Binary Search The Answer) with $$$l = 1 - \epsilon$$$ and $$$r = 10^5 + \epsilon$$$ until $$$r - l < \epsilon$$$. (Don't worry, it is guaranteed that if $$$s = r$$$, $$$P$$$ can cover all points).

Notice that if we have a fixed value of $$$s = mid$$$, then we only need to know if there exist a rotational orientation of $$$P$$$ such that all points are covered by $$$P$$$.

Observation 2. Focus on one of the points. Notice that if we rotate the point clockwise or counter-clockwise by $$$\frac{2\pi}{m}$$$, it will not change how far you have to rotate the point such that it is inside $$$P$$$, since it is the same as rotating $$$P$$$ by $$$\frac{2\pi}{m}$$$ (which is the same as not rotating it). Thus, we can repeatedly decrease $$$\theta_i$$$ by $$$\frac{2\pi}{m}$$$ until $$$0 \leq \theta_i < \frac{2\pi}{m}$$$ for each $$$1 \leq i \leq n$$$. It is strongly advised to use math instead of repeated subtraction. This observation also leads us to the fact that the angle of counter-clockwise rotation needed for $$$P$$$ to cover all points is in the interval $$$[0,\frac{2\pi}{m})$$$.

Let's focus back to the binary search iteration. If $$$\max_{1 \leq i \leq n}(d_i) > s$$$, then we immediately know that $$$s < k$$$. Thus, we can set $$$l := mid - \epsilon$$$ and do the binary search again. Alternatively, we can set $$$l = \max_{1 \leq i \leq n}{d_i} - \epsilon$$$ instead before doing the binary search.

For each point $$$a_i$$$, define $$$0 \leq ang_{1,i} < ang_{2,i} < \frac{2\pi}{m}$$$ as the answer to "How far do we have to rotate $$$P$$$ such that the point $$$a_i$$$ lies on one of the sides of $$$P$$$?". This can be calculated using some triangle trigonometry (see the code for implementation). Now, there are two cases:

Rotating $$$P$$$ by $$$i \in [ang_{1,i},ang_{2,i}]$$$ results in point $$$a_i$$$ being inside $$$P$$$. Then, add the segment $$$[ang_{1,i},ang_{2,i}]$$$ for possible rotations of $$$P$$$.
Rotating $$$P$$$ by $$$i \in (ang_{1,i},ang_{2,i})$$$ results in point $$$a_i$$$ being outside $$$P$$$. Then, add the segment $$$[0,ang_{1,i}]$$$ and $$$[ang_{2,i},\frac{2\pi}{m})$$$ for possible rotations of $$$P$$$.

In case of no existing value of $$$ang_{1,i}$$$ and $$$ang_{2,i}$$$, just add the segment $$$[0,\frac{2\pi}{m})$$$ for possible rotations of $$$P$$$ since the point is guaranteed to be inside $$$P$$$ no matter what. Now the problem has been reduced to this problem: Given some segments, does there exist a value such that it is covered by $$$n$$$ segments? We can easily do this in $$$O(n \cdot log(n))$$$ using sweep line. If there is, set $$$r := mid + \epsilon$$$. Otherwise, $$$l := mid - \epsilon$$$.

Time complexity: $$$O(n \cdot log(n) \cdot log(1/\epsilon))$$$

Rate the problem

Appendix: Code for all problems

Problem A

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,t,tt;
 
int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
	    printf("? 1\n");
	    fflush(stdout);
	    scanf("%d",&t);
	    printf("? %d\n",t*2);
	    fflush(stdout);
	    scanf("%d",&tt);
	    printf("! %d\n",t*2-(tt!=t*2));
	    fflush(stdout);
	}
	
	//fclose(stdin);
	return 0;
}

Problem B

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
       ll n,m,x,y,k;
       cin>>n>>m>>x>>y>>k;
       ll a1=(n*m)-(n*y);
       ll a2=(n*m)-(m*x);
       ll a3=(n*m)-(n*(m-y+1));
       ll a4=(n*m)-(m*(n-x+1));
       if(k==0) cout<<0<<endl;
       else if(k==1) cout<<max({a1,a2,a3,a4})<<endl;
       else if(k==2){
           ll b1=a1+max((n-x)*y,(x-1)*y);
           ll b2=a2+max(x*(y-1),x*(m-y));
           ll b3=a3+max((m-y+1)*(x-1),(m-y+1)*(n-x));
           ll b4=a4+max((n-x+1)*(m-y),(n-x+1)*(y-1));
           ll b5=a1+a3;
           ll b6=a2+a4;
           cout<<max({b1,b2,b3,b4,b5,b6})<<endl;
       }
       else if(k==3){
           a1=n-x;
           a2=x-1;
           a3=m-y;
           a4=y-1;
           cout<<n*m-1-min({a1,a2,a3,a4})<<endl;
       }
       else cout<<(n*m-1)<<endl;
    }
}

Problem C

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
 
using namespace std;
 
int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
 
        int t;
        cin >> t;
 
        while (t --> 0) {
                int n;
                cin >> n;
 
                map<int, int> cnt;
                vector<pair<int, int>> a;
                for (int i = 1; i <= n; i++) {
                        int x;
                        cin >> x;
 
                        cnt[x] += 1;
                        a.push_back({x, i});
                }
                sort(a.begin(), a.end(), [&](pair<int, int> x, pair<int, int> y) {
                        if (x.fi != y.fi) return x.fi < y.fi;
                        return x.se > y.se;
                });
 
                vector<int> fen(n + 1);
 
                auto upd = [&](int x, int val) {
                        for (; x <= n; x += x & -x) fen[x] += val;
                };
 
                auto get = [&](int x) {
                        int res = 0;
                        for (; x > 0; x -= x & -x) res += fen[x];
                        return res;
                };
 
                for (int i = 1; i <= n; i++) upd(i, 1);
 
                int lst = 0, cur = 0;
                vector<int> ans(n + 1);
                for (int p = 0; p < n; p++) {
                        auto [x, i] = a[p];
                        if (p == 0) {
                                cur += (x - 1) * n;
                                lst = x - 1;
                        } else if (a[p - 1].fi != x) {
                                cur += (x - lst - 1) * get(n);
                                cur += cnt[lst + 1];
                                lst = x - 1;
                        }
                        
                        ans[i] = cur + get(i);
                        upd(i, -1);
                }
 
                for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
        }
        
        return 0;
}

Problem D

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u; --v; --c;
        g[u].push_back({v, c});
    }
    vector<int> ans(n);
    vector<vector<int>> colors(n);
    colors[0].push_back(-1);
    colors[0].push_back(-1);
    vector<int> Q;
    Q.push_back(0);
    while (!Q.empty()) {
        int u = Q.back();
        Q.pop_back();
        ans[u] = true;
        if (colors[u].size() == 2) {
            for (auto el : g[u]) {
                int v = el.first;
                int c = el.second;
                if (colors[v].size() == 2) {
                    continue;
                }
                if (colors[v].empty()) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                    continue;
                }
                if (colors[v][0] != c) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                }
            }
        } else if (colors[u].size() == 1) {
            int cur = colors[u][0];
            for (auto el : g[u]) {
                int v = el.first;
                int c = el.second;
                if (c == cur) {
                    continue;
                }
                if (colors[v].size() == 2) {
                    continue;
                }
                if (colors[v].empty()) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                    continue;
                }
                if (colors[v][0] != c) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (ans[i]) {
            cout << i + 1 << " ";
        }
    }
    cout << "\n";
}
 
int32_t main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
    return 0;
}

Problem E

#include<bits/stdc++.h>
 
using namespace std;
using pi=pair<int,int>;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &nx : a){cin >> nx;}
    vector<int> b(n);
    for(auto &nx : b){cin >> nx;}
    vector<int> c(n);
    for(auto &nx : c){cin >> nx;}
 
    // 0 ... nothing
    // 1 ... cc...caa...acc...
    // 2 ... cc...caa...a
    vector<vector<long long>> dp(n,vector<long long>(3,-8e18));
    vector<vector<pi>> pre(n,vector<pi>(3));
 
    dp[0][0]=b[0];
    pre[0][0]={-1,1};
    dp[0][1]=c[0];
    pre[0][1]={-1,2};
    for(int i=1;i<n;i++){
      // from 0
      if(dp[i][0] < dp[i-1][0]+b[i]){
        dp[i][0]=dp[i-1][0]+b[i];
        pre[i][0]={0,1};
      }
      if(dp[i][1] < dp[i-1][0]+c[i]){
        dp[i][1]=dp[i-1][0]+c[i];
        pre[i][1]={0,2};
      }
 
      // from 1
      if(dp[i][2] < dp[i-1][1]+a[i]){
        dp[i][2]=dp[i-1][1]+a[i];
        pre[i][2]={1,0};
      }
      if(dp[i][1] < dp[i-1][1]+b[i]){
        dp[i][1]=dp[i-1][1]+b[i];
        pre[i][1]={1,1};
      }
      if(dp[i][1] < dp[i-1][1]+c[i]){
        dp[i][1]=dp[i-1][1]+c[i];
        pre[i][1]={1,2};
      }
 
      // from 2
      if(dp[i][2] < dp[i-1][2]+a[i]){
        dp[i][2]=dp[i-1][2]+a[i];
        pre[i][2]={2,0};
      }
      if(dp[i][2] < dp[i-1][2]+b[i]){
        dp[i][2]=dp[i-1][2]+b[i];
        pre[i][2]={2,1};
      }
      if(dp[i][1] < dp[i-1][2]+c[i]){
        dp[i][1]=dp[i-1][2]+c[i];
        pre[i][1]={2,2};
      }
    }
 
    // for(auto &nx : dp){
    //   for(auto &ny : nx){cout << ny << " ";}
    //   cout << "\n";
    // }
 
    vector<int> pt;
    int tg;
    if(dp[n-1][0]<dp[n-1][2]){tg=2;}else{tg=0;}
 
    // cout << max(dp[n-1][0],dp[n-1][2]) << "\n";
 
    vector<int> his(n);
    for(int i=n-1;i>=0;i--){
      his[i]=pre[i][tg].second;
      tg=pre[i][tg].first;
    }
 
    vector<int> p(n);
    int ofs=0;
    vector<int> sft;
 
    // for(auto &nx : his){cout << nx << " ";}cout << "\n";
 
    his.push_back(2);
    int phs=0;
 
    for(int i=0;i<=n;i++){
      if(his[i]==2){
        if(phs==2){
          int sz=sft.size();
          for(int i=0;i<sz;i++){
            p[sft[(i+ofs)%sz]]=sft[i];
          }
          ofs=0;
          sft.clear();
        }
 
        sft.push_back(i);
        ofs++;
        phs=1;
      }
      else if(his[i]==1){p[i]=i;}
      else if(his[i]==0){
        if(phs==1){phs=2;}
        sft.push_back(i);
      }
    }
 
    long long act=0;
    for(int i=0;i<n;i++){
      if(p[i]<i){act+=a[i];}
      else if(p[i]==i){act+=b[i];}
      else{act+=c[i];}
    }
    // cout << act << "\n";
 
    for(int i=0;i<n;i++){
      if(i){cout << " ";}
      cout << p[i]+1;
    }cout << "\n";
  }
  return 0;
}

Problem F

#include <bits/stdc++.h>
 
using namespace std;
 
const long double PI=acosl(-1);
const int MAXN=2e5+2;
pair<long double,long double> xy[MAXN];
vector<pair<long double,bool>> sweep;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n,m;
        cin >> n >> m;
        long double x,y,ang,rot=2*PI/m,maxDist=0;
        for (int i=1;i<=n;i++) {
            cin >> x >> y;
            ang=atan2l(y,x);
            ang-=floorl(ang/rot)*rot;
            xy[i]={sqrtl(x*x+y*y),ang};
            maxDist=max(maxDist,xy[i].first);
        }
        long double l=maxDist,r=3*maxDist,mid;
        int cnt,cnt2;
        while (r-l >= 1e-10) {
            cnt=0;cnt2=0;sweep.clear();
            mid=(l+r)/2; // bin search on size
            for (int i=1;i<=n;i++) {
                if (xy[i].first <= mid*cosl(rot/2)) continue;
                cnt++;
                ang=rot/2-acosl(mid*cosl(rot/2)/xy[i].first);
                if (xy[i].second < ang) {
                    sweep.push_back({rot+xy[i].second-ang,0});
                    sweep.push_back({ang+xy[i].second,1});
                    sweep.push_back({0,0});
                }
                else if (xy[i].second >= rot-ang) {
                    sweep.push_back({0,0});
                    sweep.push_back({ang-rot+xy[i].second,1});
                    sweep.push_back({xy[i].second-ang,0});
                }
                else {
                    sweep.push_back({ang+xy[i].second,1});
                    sweep.push_back({xy[i].second-ang,0});
                }
            }
            sort(sweep.begin(),sweep.end());
            for (auto &i : sweep) {
                if (i.second) cnt2--;
                else cnt2++;
                if (cnt2 == cnt) break;
            }
            if (cnt2 != cnt) l=mid;
            else r=mid;
        }
        cout << setprecision(10) << l << endl;
    }
}

Full text and comments »

Tutorial of TheForces Round #27(3^3-Forces)

physics0523
11 months ago
2

Invitation to TheForces Round #27 (3^3-Forces, TheForces-Rated, Prizes!)

By physics0523, history, 11 months ago, In English

Hello, Codeforces!

We are happy to invite you to TheForces Round #27 (3^3-Forces), which will take place on 10.12.2023 17:35 (Московское время)

Editorial is out!

What is TheForces Round?

You will have 120 minutes to solve 6 problems.

Note:there is an interactive problem in this round. If you are unfamiliar with interaction problems,you can read the guide for interactive problems here.

The round is TheForces rated! After the round you can find your rating changes here.

Prizes: the participant in the $$$i$$$th place will receive $$$2^{3-i}$$$ dollars $$$(1 \leq i \leq 3)$$$ as a prize. In addition, we will randomly select $$$\lfloor \frac{p}{30} \rfloor$$$ lucky participants and give each of them $$$1$$$ dollar as a prize, where $$$p$$$ is the number of participants. Please actively participate!

You can get more information about theforces rating and prizes in our discord server.

Problems were prepared and authored by blxst,pavlekn, wuhudsm, KitasCraft,chromate00, Yugandhar_Master,granadierfc.
We would like to thank our army of testers: satyam343, pavlekn,Error_Yuan,blxst, vikram108,Yugandhar_Master,HexShift, Misbaul_Hasan, MisterReaper.
Also we want to thank You for participating in our round.

Contests' archive

Congratulations to the winners:

1.liympanda

2.Joshc

3.arvindf232

And $$$2$$$ lucky participants:

MarcosK

DF_Pite

(Pls DM wuhudsm in CF or Discord for your prize :) )

Editorial

Full text and comments »

Announcement of TheForces Round #27(3^3-Forces)

physics0523
11 months ago
9

TheForces Round #26 Editorial

By physics0523, history, 12 months ago, In English

104802A - Submission Bait Writer: wuhudsm

Editorial

Rate the problem

104802B - Snowy Bus Writer: pavlekn

Editorial

Rate the problem

104802C - Nafis and Strings Writer: BF_OF_Priety

Editorial

$$$Hint 1$$$ : What's the minimum frequency of the most frequent character of a decimal string?

$$$Hint 2$$$ : What's the minimum size of $$$LCS$$$ between two strings of length $$$K$$$ required to make a string of size $$$19k/10$$$?

We can observe one thing that as there are only $$$\tt{10}$$$ possible different characters in a string of length $$$K$$$ then it's obvious that the frequency of the most frequent character in it is $$$\ge K/10$$$ , let's assume that character is $$$\tt{0}$$$ in the first string that we observe.All we need to solve this problem is finding a $$$LCS$$$ of size atleast $$$K/10$$$ between two strings.So we already have a string where there are $$$K/10$$$ $$$\tt{0}$$$s.Now let's observe any other $$$9$$$ strings where the most frequent characters suppose are : $$$1$$$ $$$2$$$ $$$\dots$$$ $$$9$$$ . Notice that we are assuming that there are no same characters among the first $$$10$$$ observed strings' most frequent characters co-incidentally. If there are duplicates we already have our answer. Assuming there are no duplicates in the first $$$\tt{10}$$$ observed strings, it is guaranteed the most frequent character appearing in the $$$11th$$$ string must have appeared before as there are $$$\tt{10}$$$ possible characters only.Then we have our answer , we will construct our answer by merging two strings with same most frequent character.It's basically the $$$pigeonhole$$$ principle like if we have $$$\tt{10}$$$ types of chocolates in $$$\tt{11}$$$ boxes , there has to be duplicates.So we prove that $$$11$$$ strings are enough to generate an answer , so we always have an answer as we have $$$20$$$ decimal strings

Time complexity of optimal implementation of this problem : $$$O(20 * K)$$$ , although there are $$$O(20^2 * K)$$$ solutions which may also pass which takes advantage of the fact that there has to be a pair of strings which have $$$LCS$$$ of length >= $$$K/10$$$

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back
#define pf push_front
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin>>k;
    vector<string> v;
    string s;
    vector<ll> adj[10];//to store indices of string where a particular character is most frequent
    for(int i=1;i<=20;i++){
        cin>>s;
        v.push_back(s);
    }
    int l=-1;
    int r=-1;
    char aa='Z';
    for(int i=0;i<=19;i++){
        ll m[10]={};//character frequency array
        for(auto u : v[i]){
            int kk=u-'0';
            m[kk]++;
        }
        ll best=0;
        ll yy=-1;
        for(char xx='0';xx<='9';xx++){
            ll xx1=xx-'0';
            if(m[xx1]>best){
                best=m[xx1];
                ll pal=xx-'0';
                yy=pal;
            }
        }
        adj[yy].push_back(i);
        if(adj[yy].size()==2){
            aa='0';
            aa+=yy;
            l=adj[yy][0];
            r=adj[yy][1];
            break;
        }
    }
    deque<ll> v2,v3;//used for storing indices of LCS of two optimal strings
    string ans="";
    //string merging process starts
    ll kk=-1;
    for(auto u : v[l]){
        kk++;
        if(u==aa) v2.pb(kk);
    }
    v2.pf(-1);
    kk=-1;
    for(auto u : v[r]){
        kk++;
        if(u==aa) v3.pb(kk);
        
    }
    v3.pf(-1);
    for(ll aa1=1;aa1<=k/10;aa1++){
        
        for(ll bb=v2[aa1-1]+1;bb<=v2[aa1]-1;bb++){
            ans+=v[l][bb];
            
        }
        for(ll bb=v3[aa1-1]+1;bb<=v3[aa1]-1;bb++){
            ans+=v[r][bb];
            
        }
        ans+=aa;
        
    }
    for(ll aa1=v2[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[l][aa1];
    for(ll aa1=v3[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[r][aa1];
    cout<<ans<<endl;
    
}

Rate the problem

104802D - Rudraksh's Sleepiness Writer: Ashutosh.Singh

Editorial

Rate the problem

104802E - Anuj's Longest Subarray Writer: Ashutosh.Singh

Editorial

Rate the problem

104802F - Nafis and Mex Writer: BF_OF_Priety

Editorial

$$$hint 1$$$ : Maximum possible score of a subsequence is $$$n$$$ as in an array of size $$$n$$$ $$$\rm{mex}$$$ can't be greater than $$$n$$$

$$$hint 2$$$ : Calculating number of subsequences where $$$score$$$ is $$$i$$$ for each $$$0 \le i \le n$$$ is enough

First let's calculate for each $$$0 \le i \le n$$$ the number of subsequences where score is $$$i$$$.How to calculate that?Well when is mex of a subsequence a positive integer $$$i$$$?How does the subsequence look like?In that subsequence there can be arbitrary integers greater than $$$i$$$ ,no appearance of $$$i$$$ and every integer from $$$\tt{0}$$$ to $$$i-1$$$ is present in the subsequence each arbitrary number of times.So if $$$f_i$$$ is the value of number of subsequences where $$$mex$$$ is $$$i$$$ , $$$f_i$$$ : $$$ 2^X * (2^{a_0}-1) * (2^{a_1}-1) * (2^{a_2}-1)* \dots * (2^{a_{i-1}}-1)$$$ where $$$X$$$ is count of elements greater than $$$i$$$ and $$$a_j$$$ is count for j in the array.If subsequence count for some $$$i$$$ crosses $$$K$$$ we minimise it to $$$K$$$.In case of $$$0$$$ : $$$f_0$$$ = $$$2^y$$$ where $$$y$$$ is count of elements greater than $$$0$$$. But we subtract $$$\tt{1}$$$ from that count as we are considering $$$non-empty$$$ subsequences only. Now when we pick and arrange $$$K$$$ subsequences it's obvious that we have to pick $$$(k+1)/2$$$ subsequences with $$$minimum$$$ scores and $$$k/2$$$ subsequences with $$$maximum$$$ scores. As the range of possible $$$scores$$$ is very low $$$[0 \dots n]$$$ we just iterate greedily from the beginning of the range to add scores of $$$odd$$$ indices and after that we iterate from the end greedily to subtract the scores of $$$even$$$ indices.

Time complexity of optimal implementation of this solution : $$$O(N)$$$


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   ll t=1;
   cin>>t;
    ll m[100002];//subsequence count array
    ll m2[100002]={};//frequency array
    ll fact[100002];//array for storing values of 2^i
    for(int j=1;j<=t;j++){
        ll n,k;
        cin>>n>>k;
        ll i,x;
        vector<ll> v;
        fact[0]=1;
        m2[0]=0;
        for(i=1;i<=n;i++){
            m2[i]=0;
            fact[i]=fact[i-1];
            fact[i]*=2;
            fact[i]=min(fact[i],k+1);
        }
        ll sum=0;
        for(i=1;i<=n;i++){
            cin>>x;
            if(x<=n) m2[x]++;
        }
        sum=n;
        ll dal=1;
        for(ll i=0;i<=n;i++){
            m[i]=dal;
            sum-=m2[i];
            m[i]*=fact[sum];
            if(i==0) m[i]-=1;
            m[i]=min(m[i],k);
            dal*=(fact[m2[i]]-1);
            dal=min(dal,k+1);
        }
        ll ans=0;
        ll jh=(k+1)/2; // odd
        ll jk=k/2; // even
        for(i=0;i<=n;i++){
            ll kk=min(m[i],jh);
            ans+=(i*kk);
            jh-=kk;
            m[i]-=kk;
        }
        for(i=n;i>=0;i-=1){
            ll kk=min(m[i],jk);
            ans-=(i*kk);
            jk-=kk;
            m[i]-=kk;
        }
        cout<<ans<<endl;
        }
}

Rate the problem

104802G - Che Forest Writer: pavlekn

Editorial

Rate the problem

Appendix: physics0523's code for all problems (C++)

Some solutions depends on some library and I pasted them into the solutions. In that case, main logic is at the lower side of the code.

Problem A

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n;
    cin >> n;
    deque<long long> dq;
    for(long long i=0;i<n;i++){
      long long x;
      cin >> x;
      dq.push_back(x);
    }
    long long res=0;
    while(dq.size()>=2){
      long long pre=dq.front();dq.pop_front();
      long long bac=dq.back();dq.pop_back();
      if(pre==bac){continue;}
      if(pre<bac){
        res++;
        dq.push_back(bac-pre);
      }
      else{
        res++;
        dq.push_front(pre-bac);
      }
    }
    cout << res << "\n";
  }
  return 0;
}

Problem B

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,m;
    cin >> n >> m;
    vector<long long> a(n);
    for(auto &nx : a){cin >> nx;}
    vector<long long> b(n);
    for(auto &nx : b){cin >> nx;}

    vector<long long> eff;
    for(long long i=0;i<n;i++){
      m+=a[i];
      eff.push_back(a[i]+b[i]);
    }
    sort(eff.begin(),eff.end());
    reverse(eff.begin(),eff.end());
    long long res=-1;
    for(long long i=0;i<n;i++){
      m-=eff[i];
      if(m<=0){res=i+1;break;}
    }
    cout << res << "\n";
  }
  return 0;
}

Problem C

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  std::random_device seed_gen;
  std::mt19937_64 engine(seed_gen());

  int k;
  cin >> k;
  vector<string> s(20);
  vector<vector<int>> bk(20,vector<int>(10,0));

  for(int i=0;i<20;i++){
    cin >> s[i];
    for(int j=0;j<k;j++){
      bk[i][s[i][j]-'0']++;
    }
  }

  vector<pair<int,int>> vp;
  for(int i=0;i<20;i++){
    for(int j=i+1;j<20;j++){
      vp.push_back({i,j});
    }
  }
  shuffle(vp.begin(),vp.end(),engine);

  vector<int> p={0,1,2,3,4,5,6,7,8,9};

  for(auto &nx : vp){
    int i=nx.first;
    int j=nx.second;
    shuffle(p.begin(),p.end(),engine);
    for(auto &tg : p){
      if(min(bk[i][tg],bk[j][tg])>=(k/10)){
        string res;

        int p=0,q=0;
        while(p<k && q<k){
          if(s[i][p]-'0' != tg){
            res.push_back(s[i][p]);
            p++;
            continue;
          }
          if(s[j][q]-'0' != tg){
            res.push_back(s[j][q]);
            q++;
            continue;
          }
          res.push_back(s[i][p]);
          p++;q++;
        }

        while(p<k){res.push_back(s[i][p]);p++;}
        while(q<k){res.push_back(s[j][q]);q++;}

        while(res.size()<(k/10)*19){
          res.push_back('0'+(engine()%10));
        }
        cout << res << "\n";
        return 0;
      }
    }
  }
  return 0;
}

Problem D

// factorize
// https://judge.yosupo.jp/problem/factorize
#include<bits/stdc++.h>

using namespace std;

// https://hitonanode.github.io/cplib-cpp/number/binary_gcd.hpp.html
template <typename Int> Int binary_gcd(Int x_, Int y_) {
  unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
  if (!x or !y) return x + y;
  int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
  x >>= n, y >>= m;
  while (x != y) {
    if (x > y) {
      x = (x - y) >> __builtin_ctzll(x - y);
    } else {
      y = (y - x) >> __builtin_ctzll(y - x);
    }
  }
  return x << (n > m ? m : n);
}

struct factorizer{
  long long smlrng;
  vector<long long> lpf;
  vector<long long> plis;
  // init
  // https://37zigen.com/linear-sieve/
  factorizer(long long smlrng_){
    smlrng = smlrng_;
    lpf.resize(smlrng+1);
    fill(lpf.begin(),lpf.end(),0);
    plis.clear();
    for(long long i=2;i<=smlrng;i++){
      if(lpf[i]==0){
        lpf[i]=i;
        plis.push_back(i);
      }
      for(auto &p : plis){
        if(p*i > smlrng || p>lpf[i]){break;}
        lpf[p*i]=p;
      }
    }
  }

  vector<long long> tinyplis = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

  long long mulmn(long long a,long long b,long long n){
    __int128 c128=a;
    c128*=b;
    return ((long long)(c128%n));
  }
  long long powmn(long long a,long long b,long long n){
    long long res=1;
    while(b>0){
      if(b&1ll){
        res=mulmn(res,a,n);
      }
      a=mulmn(a,a,n);
      b/=2;
    }
    return res;
  }

  bool isprime(long long n){
    if(n<=1){return false;}
    if(n<=smlrng){return (n==lpf[n]);}
    for(auto &p : tinyplis){
      if(n%p==0){return false;}
    }

    // from now, n should be odd
    // https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
    vector<long long> a={2,7,61};
    if(n>=(1ll<<32)){
      a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    }

    long long s=__builtin_ctzll(n-1);
    long long d=((n-1)>>s);
    for(auto &ca : a){
      if(powmn(ca,d,n)==1){continue;}
      bool cp=true;
      for(long long r=0;r<s;r++){
        if(powmn(ca,(1ll<<r)*d,n)==(n-1)){cp=false;break;}
      }
      if(cp){return false;}
    }
    return true;
  }

  long long ffrho(long long n){
    long long m=(1ll<<((64-__builtin_clzll(n))/8));
    for(long long c=1;;c++){
      auto f = [&](long long v){ return (mulmn(v,v,n)+c)%n; } ;
      long long x,y=2,r=1,q=1,g=1,ys;
      while(g==1){
        x=y;
        for(long long i=0;i<r;i++){
          y=f(y);
        }
        long long k=0;
        while(k<r && g==1){
          ys=y;
          for(long long i=0;i<min(m,r-k);i++){
            y=f(y);
            q=mulmn(q,abs(x-y),n);
          }
          g=binary_gcd(q,n);
          k+=m;
        }
        r<<=1;
      }
      if(g==n){
        g=1;
        while(g==1){
          ys=f(ys);
          g=binary_gcd(abs(x-ys),n);
        }
      }
      if(g<n){
        if(isprime(g)){return g;}
        else if(isprime(n/g)){return (n/g);}
        return ffrho(g);
      }
    }
  }

  // https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
  vector<long long> factorize(long long n){
    vector<long long> res;
    for(auto &p : tinyplis){
      while(n%p==0){
        n/=p;
        res.push_back(p);
      }
    }
    while(n>1){
      if(isprime(n)){res.push_back(n);break;}
      long long cf=ffrho(n);
      while(n%cf==0){
        n/=cf;
        res.push_back(cf);
      }
    }
    sort(res.begin(),res.end());
    return res;
  }
};

vector<int> gb(int x,factorizer &fz){
  for(int i=2;i<=x-i;i++){
    if(fz.isprime(i) && fz.isprime(x-i)){
      return {i,x-i};
    }
  }
  return {-1,-1};
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  factorizer fz(10000005);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int x,y;
    cin >> x >> y;
    if(fz.isprime(x+y)){
      cout << 1 << "\n";
      cout << x << " " << y << "\n";
      continue;
    }
    else if(fz.isprime(x+y-2)){
      cout << 2 << "\n";
      cout << 1 << " " << 1 << "\n";
      cout << x << " " << y << "\n";
      continue;
    }
    else if((x+y)%2==0){
      vector<int> v=gb(x+y,fz);

      cout << v.size() << "\n";
      int s=0;
      for(auto &nx : v){
        s+=nx;
        cout << min(x,s) << " " << max(0,s-x) << "\n";
      }
    }
    else{
      vector<int> v=gb(x+y-3,fz);
      v.push_back(3);

      cout << v.size() << "\n";
      int s=0;
      for(auto &nx : v){
        s+=nx;
        cout << min(x,s) << " " << max(0,s-x) << "\n";
      }
    }
  }
  return 0;
}

Problem E

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n,k;
    cin >> n >> k;
    vector<int> inv(n);
    for(int i=0;i<n;i++){
      int p;
      cin >> p;
      p--;
      inv[p]=i;
    }

    set<pi> st;
    for(int i=0;i<k+5;i++){
      st.insert({-1,1e9+i});
      st.insert({n,1e9+i});
    }

    vector<int> res(n,0);

    for(int i=n-1;i>=0;i--){
      auto ifw=st.lower_bound({inv[i],i});
      auto ibk=ifw;ibk--;
      vector<int> pf,pb;
      for(int i=0;i<k;i++){
        pf.push_back((*ifw).first);ifw++;
        pb.push_back((*ibk).first);ibk--;
      }
      // for(auto &nx : pf){cout << nx << " ";}cout << "\n";
      // for(auto &nx : pb){cout << nx << " ";}cout << "\n";
      for(int p=0;p<k;p++){
        int q=k-1-p;
        res[inv[i]]=max(res[inv[i]],pf[p]-pb[q]-1);
      }
      st.insert({inv[i],i});
    }

    for(int i=0;i<n;i++){
      if(i){cout << " ";}
      cout << res[i];
    }cout << "\n";
  }
  return 0;
}

Problem F

#include<bits/stdc++.h>

#include <algorithm>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

using namespace std;
using namespace atcoder;

long long big=2e9;
long long op(long long a,long long b){
  return min(a*b,big);
}
long long e(){
  return 1;
}

long long power(long long a,long long b){
  long long res=e();
  while(b>0){
    if(b&1ll){
      res=op(res,a);
    }
    a=op(a,a);
    b/=2;
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,k;
    cin >> n >> k;

    long long gtn=0;
    vector<long long> bk(n+1,0);
    for(long long i=0;i<n;i++){
      long long a;
      cin >> a;
      if(a>n){gtn++;}
      else{bk[a]++;}
    }

    vector<long long> ini(n+2);
    for(long long i=0;i<=n;i++){
      ini[i]=power(2,bk[i]);
    }
    ini[n+1]=power(2,gtn);

    segtree<long long,op,e> seg(ini);
    vector<long long> cnt(n+1);
    for(long long i=0;i<=n;i++){
      seg.set(i,1); // not contain
      cnt[i]=seg.all_prod();
      seg.set(i,power(2,bk[i])-1); // at least 1
    }
    cnt[0]--; // remove empty set

    long long pre=(k+1)/2;
    long long suf=k-pre;
    long long res=0;
    for(long long i=0;i<=n;i++){
      long long del=min(pre,cnt[i]);
      pre-=del;
      res+=del*i;
    }
    for(long long i=n;i>=0;i--){
      long long del=min(suf,cnt[i]);
      suf-=del;
      res-=del*i;
    }
    // for(auto &nx : cnt){
    //   cout << nx << " ";
    // }cout << "\n";
    cout << res << "\n";
  }
  return 0;
}

Problem G

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;

    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    int fw=(k+1)/2;
    int bc=k/2;
    int md=n-fw-bc;

    string pre,mid,suf;

    for(char c='a';c<='z';c++){
      for(int i=n-1;i>=0;i--){
        if(pre.size()<fw && s[i]==c){
          pre.push_back(s[i]);
          s[i]='*';
        }
      }
    }

    string ns;
    for(auto &nx : s){
      if(nx!='*'){ns.push_back(nx);}
    }

    int l=ns.size();
    vector<vector<int>> mem(l+1);
    vector<int> bk(26,1e9);
    mem[l]=bk;
    for(int i=l-1;i>=0;i--){
      bk[ns[i]-'a']=i;
      mem[i]=bk;
    }

    int pt=0;
    while(mid.size()<md){
      // cerr << mid << " " << pt << "\n";
      for(int i=0;i<26;i++){
        // cerr << pt << " " << i << " " << ((int)mid.size())+(l-mem[pt][i]) << "\n";
        if(((int)mid.size())+(l-mem[pt][i]) >= md){
          mid.push_back(ns[mem[pt][i]]);
          ns[mem[pt][i]]='*';
          pt=mem[pt][i]+1;
          break;
        }
      }
    }

    for(auto &nx : ns){
      if(nx!='*'){
        suf.push_back(nx);
      }
    }
    sort(suf.begin(),suf.end());
    cout << pre+mid+suf << "\n";
  }
  return 0;
}

Full text and comments »

Tutorial of TheForces Round #26 (Readall-Forces)

physics0523
12 months ago
12

Invitation to TheForces Round #26 (Readall-Forces, TheForces-Rated, Prizes!)

By physics0523, history, 12 months ago, In English

Hello, Codeforces!

We are happy to invite you to TheForces Round #26 (Readall-Forces), which will take place on 16.11.2023 17:35 (Московское время). As you can see in the subtitle, you are highly encouraged to read all the problems!

What is TheForces Round?

You will have 150 minutes to solve 7 problems.

The round is TheForces rated! After the round you can find your rating changes here.

You can get more information about Theforces rating and prizes in our discord server.

Writers: wuhudsm, pavlekn, BF_OF_Priety, Ashutosh.Singh
Testers: blxst, Error_Yuan, Yugandhar_Master, k1r1t0, pavlekn, Banis, _Berlin_, BF_OF_Priety, ivls, Rifat02
Coordinators: wuhudsm, physics0523
Also we want to thank You for participating in our round.

Contests' archive

UPD:

Congratulations to the winners:

1.Golovanov399

2.neal

3.1_2_3_4_5_9

And $$$5$$$ lucky participants:

11.IgorI

45.satyam343

58.pgiaminh8368

99.hi124

124.cseshamim47

(Pls DM wuhudsm in CF or Discord for your prize :) )

Editorial

Full text and comments »

Announcement of TheForces Round #26 (Readall-Forces)

physics0523
12 months ago
25

Strange Comparison: vector<vector<int>> vs vector<pair<int,int>> ?

By physics0523, history, 23 months ago, In English

If we want to use a 2D dynamic array, some C++ user writes following 2D vector:

vector<vector<int>> a(n);

// add y to a[x]
a[x].push_back(y);

// walkthrough a[x]
for(auto &nx : a[x]){
  cout << nx << "\n";
}

But we can do the equivalent thing with handwritten linked list (when we know the total size) by using 1D vector<pair<int,int>>:

pair<int,int> empty={-1,-1};
vector<pair<int,int>> b(n+total_size,empty);
int add_point=n;

// add y to b[x]
if(b[x]!=empty){
  b[add_point]=b[x];
  b[x].second=add_point;
  add_point++;
}
b[x].first=y;

// walkthrough b[x]
int current=x;
while(current!=empty.second && b[currnt]!=empty){
  cout << b[current].first << "\n";
  current=b[current].second;
}

So, what's the benefit for the later implementation? The merit is the generation time of later one is very fast.

vector size = $$$10^5$$$, Total elements = $$$10^6$$$ (this means we need vector<vector<int>>(1e5) and the sum of the size of $$$10^5$$$ vectors is $$$10^6$$$)

	generate	walkthrough
vector<vector<int>>	49.04 ms	3.12 ms
vector<pair<int,int>>	12.78 ms	19.52 ms

vector size = $$$10^6$$$, Total elements = $$$10^6$$$

	generate	walkthrough
vector<vector<int>>	138.56 ms	10.92 ms
vector<pair<int,int>>	17.4 ms	7.8 ms

vector size = $$$10^6$$$, Total elements = $$$10^7$$$

	generate	walkthrough
vector<vector<int>>	1406.84 ms	32.86 ms
vector<pair<int,int>>	120.48 ms	437.28 ms

( on CF judge(C++20 64bit), x10 average, experiment code )

So, when the vector size is large and need small number of walkthrough, the vector<pair<int,int>> implementation have an advantage.
I use this implementation for 303C - Minimum Modular (because the package is old, current TL is 1s). 185222734

Full text and comments »

physics0523
23 months ago
7

Thank you, dXqwq!

By physics0523, history, 2 years ago, In English

According to some comments, dXqwq may be a rhythm game player.
As a rhythm game player, I receive a huge motivation for my CP journey from dXqwq.
dXqwq is not only a DX competitor but also a choseinou(super-skilled) writer of Pinely Round 1.

So, to honor him, I made a theoretical maximum score for this song in CHUNITHM. You are shining!!!

Full text and comments »

physics0523
2 years ago
3

[Suggestions] Ideas For The Hacking System

By physics0523, history, 2 years ago, In English

These days, the current usual haking system is in danger because new cheating method was discovered ( this ).
So let me share my ideas for the hacking system instead of the current one.

Current hacking system

Contestants can hack the codes of other contestants in the same room during the coding phase.
Contestants who can't solve a task or who don't lock their solution can't make hacking attempts at the task.
Successful: +100pts
Unsuccessful: -50pts

scoring by me

Suggestion 1: Open hacking system(long)

Contestants can hack the codes of any other contestants, Like edu.
Hacking has around 12h, and no points will be awarded.
Any contestants can make hacking attempts on any submissions.
Users can copy and execute the codes by themselves.
The only benefit for contestants is reducing other contestants' scores.

scoring by me

Suggestion 2: Open hacking system(short)

Exactly the same as Suggestion 1, except for the length of the hacking phase.
The length of the hacking phase is around 30min, at most 60min
- these lengths are just my idea

scoring by me

Suggestion 3: Room-division hacking phase

Contestants can hack the codes of other contestants in the same room, but it's not at the coding phase but at a hacking phase separated from the coding phase.
Duration is 30min or 15min.
- maybe uncopiable 30min or copiable 15min is good?
Any contestants can make hacking attempts on any pretest passed submissions in the same room.
Successful: +100pts
Unsuccessful: -50pts

scoring by me

Suggestion 4: Room-free hacking phase

Any contestants are presented with about min(20,AC count for the problem) submissions (chosen equally, randomly, independently) for each problem.
Duration is 30min or 15min.
- maybe uncopiable 30min or copiable 15min is good?
Any contestants can make hacking attempts on any submissions which are presented to the contestants.
Successful: +100pts
Unsuccessful: -50pts

scoring by me

Suggestion 5: Removing the hacking system

Nowadays tests are strong enough(really?) and hacking is a thing of the past.
Then, why not remove the hacking feature?

scoring by me

All of my suggestions are preventing to see other contestants' codes during the coding phase, but there may be some ideas to do coding and hacking in parallel like now.
Feel free to share your idea. I'll add them to the list.

Full text and comments »

hacking, suggestions

physics0523
2 years ago
7

Codeforces Round #654 (Div. 2) Editorial

By physics0523, history, 4 years ago, In English

Tutorial is loading...

Jury solution: 85699387

Tutorial is loading...

Jury solution: 85699884

Tutorial is loading...

Jury solution: 85699939

UPD: $$$m<\min(a,b)$$$ is wrong, the right text is $$$m\le \min(a,b)$$$

Tutorial is loading...

Jury solution: 85700178

Tutorial is loading...

Jury solution: 85700334

Tutorial is loading...

Jury solution (Solution 1): 85700515

Jury solution (Solution 2): 85700518

Tutorial is loading...

Jury solution: 85700669

Feel free to share your approach here!

Full text and comments »

Tutorial of Codeforces Round 654 (Div. 2)

654, #tutorial

+134

physics0523
4 years ago
283

Codeforces Round #654 (Div. 2)

By physics0523, history, 4 years ago, In English

Codeforcesの皆さん、こんにちは!(Hello, Codeforces!)

I'm glad to invite you to my first contest, Codeforces Round 654 (Div. 2) which will be held on Jul/01/2020 16:35 (Moscow time) (notice earlier time than usual). All of the problems were mainly written and prepared by me. The round is rated if your rating is strictly less than 2100.

You will be given 6 problems (one problem has a subtask) and 2 hours to solve them. Please, read all the problems.

I would really like to thank:

isaf27 for amazing coordinating my round.
300iq , alireza_kaviani , AmShZ , antontrygubO_o , dorijanlendvaj , lucky_21 , Monogon , noobiesAG , GrandDaddy and zxyl for mighty testing the problems.
MikeMirzayanov for marvelous Codeforces and Polygon platforms.

The scoring distribution will be announced later.

Good luck, have fun and wish your high ratings :)

UPD: Scoring distribution : $$$500 - 1000 - 1250 - 1500 - (1500 + 1250) - 3000$$$

UPD: Editorial is out

Full text and comments »

Announcement of Codeforces Round 654 (Div. 2)

654, #announcement, div2, codeforces

+732

physics0523
4 years ago
477

Say Hello to Codeforces — Codeforces #440(Div.2)

By physics0523, history, 7 years ago, In English

Hello,Codeforces!

Tell trueth,I've already joined 4 other contests in here.

Today,I joined in #440(Div.2). Codeforces Round 440 (Div. 2, based on Technocup 2018 Elimination Round 2)

A:First,judge 1~9,After that,judge 10~99.

B:If k==1,output the minimum number.
If k==2,output the maximum of a[0],a[n-1],and the 2nd lowest number.
If k>=3,output the maximum number.

C:The best idea is 4+4+4+...+4+k.
If k==0,the output is q[i]/4.
If k==1, last +4+4+1 change to +9.
So,the output is (q[i]/4)-1.
If k==2, last +4+2 change to +6.
So,the output is q[i]/4.
If k==3, last +4+4+4+3 change to +9+6.
So,the output is (q[i]/4)-1.
In every query, you can response the answer in O(1).

Accepted:ooo--
Rating change:1441->1527(+86,highest)

Atcoder:Blue(1626,max1729)
Twitter:@butsurizuki

Nice to meet you!

Ja: こどふぉ始めてみました!(とはいえこれ含めもう5回コンテスト出てるんですが)
ブログのシステムがよく分かっておらず、とりあえず一本書いてみました(解法…ですかねぇ…)
これから日本人にとって人権的な時間のコンテストなら積極的に出ようと思います!
精進を重ねてひとまず青になりたい…
暫くはDiv.2で戦いますが、将来的にはDiv.1でも戦えるような地力を付けたいです(^q^)

Full text and comments »

-2

physics0523
7 years ago
0