As an author, I suggest reading all the problems and not missing out on free positive delta.

You missed a green tester :(

as a tester, BEST CONTEST I HAVE EVER TESTED!

As a blue tester,

Hope,

orz sir

Huge tip everyone! The problems for this contest are sorted by difficulty order! Good luck @everyone

It's really a seldom Div3.It starts at Tuesday.

As a tester, I can ensure u that the round is balanced and all the problems are interesting. Good luck in the round!

Can I go to specialist in that contest Div 3 :? Hope

As a tester, it's my first time to test a Div.3 round.

まどか

Thank Aris for purple coordination!

As a yellow tester, I want to recommend to read all of the problems. Problems are quite varied. More think before coding. Don't go to implement the first idea which you got. Try to understand each example in problem statement before thinking on the problem. Don't waste a lot of time in solving a single problem and go to solve another problem if you get stuck.

I miss participating in Div 3 contests.

There's an interactive problem in the contest?

Gonna be my very first Contest :-)

My first unrated round. All the best and positive delta to everyone participating!

omg madoka

Good Luck!

Good Luck!!

Hope for positive delta.

The picture is so beautiful awa.

will try to go for 8/8 this time.

Madoka

Proud of MODI

hope to become Specialist in this contest.

My first unrated Div. 3 :)

Finally out of competition :)))

hello people, whats max positive delta i can get from this contest?

Can I become expert today?

I love madoka!

Typo on explanation for D?

In the thir s example, the carvers can choose patterns 14...

is it Div. 2 :)

It is hard for being div3

G2 is almost the same as 2022 ICPC Asia Hangzhou Regional Programming Contest problem I. The only difference is the constraints and input/output format. https://mirror.codeforces.com/gym/104090/problem/I

Hint Of Some Problems :p

A: Divide some no overlapping subarray like x***x. add all * char to the answer.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);


int main(){
   FastIO;
   
   int Test=1; cin>>Test;
   while(Test--){
       int n; string s; cin>>n>>s;
       string ans;
       ll pos=0;
       for(ll i=pos+1;i<n;i++){
        if(s[i]==s[pos]){
          ans+= s[pos]; pos=++i;
        }
       }

       cout<<ans<<endl;
       
   }
   return 0;
}
/*

*/

B: Main tricks is k>=30 cross 1e9 so have to consider onely k=0 to min(k-1,29). if(k>=30) ans=n+1. else ans= min(n+1,2^k).

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll pw[35];
void pre_cal(){
   pw[0]=1;
   for(ll i=1;i<=30;i++) pw[i]=pw[i-1]*2LL;
}

int main(){
   FastIO;
   pre_cal();
   
   int Test=1; cin>>Test;
   while(Test--){
       ll n,k; cin>>n>>k;
       if(k>=30) cout<<n+1<<endl;
       else cout<<min(n+1LL,pw[k])<<endl;
       
   }
   return 0;
}
/*

*/

C: Took every subarray maintain given condition and find all way of that subarray[x= (cnt-k+1) & way= (x*(x+1)/2], here cnt is thw continuous subbarray ne which maintain given condition.answer is summation all such subarray.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);


int main(){
   FastIO;
   
   int Test=1; cin>>Test;
   while(Test--){
       int n,k,q; cin>>n>>k>>q;
       ll cnt=0,ans=0,a; 
       for(ll i=0;i<=n;i++){
         if(i<n) cin>>a;
         if(i==n || a>q){
            if(cnt>=k){
               ll baki= cnt-k+1;
               ans+= (baki*(baki+1))/2;
            }
            cnt=0;
         }
         else if(a<=q) ++cnt;
       }

       cout<<ans<<endl;
       
   }
   return 0;
}
/*

*/

D: Use Binary Search.

//BS
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);


int main(){
   FastIO;
   
   int Test=1; cin>>Test;
   while(Test--){
       int n; cin>>n;
       vector<ll> a(n);
       for(ll i=0;i<n;i++) cin>>a[i];
       sort(all(a));  
       ll l=0,r=1e9,ans=-1;
       while(l<=r){
         ll m= (l+r)/2;
         ll mn= a[0]+m+m, mx= a[n-1]-m-m;
         ll m1=1e9,m2=0;
         if(mn<mx){
            for(ll i=0;i<n;i++){
               if(a[i]>mn && a[i]<mx){
                  m1= min(m1,a[i]); 
                  m2= max(m2,a[i]);
               } 
            }
         }
         if(m1>m2 || abs(m2-m1)<=(m+m)){
            ans=m; r=m-1;
         }
         else l=m+1;
       }

       cout<<ans<<endl;
       
   }
   return 0;
}
/*

*/

E: maintain the block in a vector with pos and end time. delete when time arrived. and other swap/check operation can be handled easily.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);


int main(){
   FastIO;
   
   int Test=1; cin>>Test;
   while(Test--){
       string s1,s2; cin>>s1>>s2;
       ll n= s1.size(), m= s2.size();
       ll same=0;
       for(ll i=0;i<n;i++) if(s1[i]==s2[i]) ++same;
       vector<pair<ll,ll>> block;
       ll t,q; cin>>t>>q;
       for(ll i=1;i<=q;i++){
         //remove block
         if(block.size()&&block[0].first==i){
            ll pp= block[0].second;
            block.erase(block.begin());
            if(s1[pp-1]==s2[pp-1]) ++same;
         }

         ll x; cin>>x;
         if(x==1){
            ll pos; cin>>pos;
            if(s1[pos-1]==s2[pos-1]) --same;
            block.pb({i+t,pos});
         }
         else if(x==2){
            ll x1,p1,x2,p2; cin>>x1>>p1>>x2>>p2;
            if(x1>x2) swap(x1,x2),swap(p1,p2);
            if(x1!=x2){
               if(s1[p1-1]==s2[p1-1]) --same;
               if(p1!=p2&&s1[p2-1]==s2[p2-1]) --same;
               swap(s1[p1-1],s2[p2-1]);
               if(s1[p1-1]==s2[p1-1]) ++same;
               if(p1!=p2&&s1[p2-1]==s2[p2-1]) ++same;
            }
            else if(x1==x2 && x1==1){ //1 1
               if(s1[p1-1]==s2[p1-1]) --same;
               if(p1!=p2&&s1[p2-1]==s2[p2-1]) --same;
               swap(s1[p1-1],s1[p2-1]);
               if(s1[p1-1]==s2[p1-1]) ++same;
               if(p1!=p2&&s1[p2-1]==s2[p2-1]) ++same;
            }
            else{ //2 2
               if(s1[p1-1]==s2[p1-1]) --same;
               if(p1!=p2&&s1[p2-1]==s2[p2-1]) --same;
               swap(s2[p1-1],s2[p2-1]);
               if(s1[p1-1]==s2[p1-1]) ++same;
               if(p1!=p2&&s1[p2-1]==s2[p2-1]) ++same;
            }
         }
         else{
            if(same+block.size()==n) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
         }
       }
       
   }
   return 0;
}
/*

*/

G1: Find the 1st 1000 number manually using k= +1. Then find every +1000 position difference gap and see which number repeat. its need <=20000 queries.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll pos[1000005];

int main(){
   FastIO;
   
   int Test=1;
   //cin>>Test;
   while(Test--){
       int p=1,val; cin>>val;
       pos[val]=p;
       for(ll i=0;i<1000;i++){
         cout<<"+ "<<1<<endl;
         cin>>val;
         if(pos[val]){
          cout<<"! "<<p<<endl;
          return 0;
         }
         pos[val]= ++p;
       }
       ll ans= 1000;
       for(ll i=0;i<1000;i++){
         cout<<"+ "<<1000<<endl;
         cin>>val;
         if(pos[val]){
           ans+= (1000-pos[val]);
           cout<<"! "<<ans<<endl;
          return 0;
         }
         else{
           p+=1000; 
           ans=p;
           pos[val]=p;
         }
       }
       
   }
   return 0;
}
/*

*/

G2 is a Nice Problem. But can't solve :|

Problem G is quite identical to https://mirror.codeforces.com/gym/104090/problem/I

My randomized solution 208802508 for G1 worked but I don't know why !!

Can someone please explain?

F: We denotes dp[t][i][j]=1 if we can arrive position (i, j) at time t, 0 otherwise. The initial status is dp[0][0][0]=1, and transition is dp[t][i][j]=dp[t-1][i-1][j] || dp[t-1][i][j-1] || dp[t-1][i][j]. And in each second we need to clear positions shot by railguns. We repeat this process until dp[t][n][m]=1 or for all (i, j) we have dp[t][i][j]=0. The complexity is O(n*m*(n*m+r)).

G1: We can solve the problem by sqrt decomposition: First, we use 1000 queries to get a[1], a[2], ..., a[1000]. If there are any value occurs more than once, we have n<1000 and get the answer. Otherwise, we have n>=1000. Now we can use another 1000 queries to get a[2000], a[3000], ..., a[1001000], we must return to some position in [1, 1000] at some time.

G2: The constraint n<=10^6 is too large for 1000 queries, but how can we solve this problem if we've known that M<=n<M+62500 (=M+250^2)? Well, we can use similar strategy: First use 250 queries to get a[1], ..., a[250], if n<250 we can get the answer. Otherwise, first we assume M<=n<M+250, and we query for a[M+250]. If M<=n<M+250, then 1<=M+250-n<=250, that means we will return back to [1, 250] and we can get the answer. Otherwise, we can assume M+250<=n<M+500 and query for a[M+500], then assume M+500<=n<M+750 and query for a[M+750], and so on. Finally we will solve the problem within 500 queries. So how can we use other 500 queries for finding M? Well, we only need to make 500 random queries and take the maximum value of answers. The probability that maximum value is not greater than n-62500 is ((n-62500)/n)^500, when n<=10^6 this probability is no more than 10^-14, therefore this method will pass 1000 testcases for probability >=(1-10^-11), so it's safe enough.

Can someone verify my sketch to G2? I couldn't implement it due to school.

For 100 times, RNG a number x between 1 and 9E8 and move -x +(x+300) (call this a "turn"), which basically advances by 300 and also gives a random position using 2 moves

if we get nothing above 90000, we know $$$n<160000$$$ and we can use the G1 solution for the remaining 800 moves else, do 200 more turns and then the max number we visited is probably within $$$90000$$$ of $$$n$$$, so we can advance by that many spots and then increase by 1 for the next 300 moves, which guarantees that we reach something we know the position of and we can determine $$$n$$$

My approach for G1 and G2 involved randomization, but infortunately it failed on test case 16, can't figure out why so ? Can someone please explain, will be a great help... Also is there anything wrong with the approach?

Approach :

Store all those sectors you have visited till now, also keep track of how much you have to add i.e. +k or -k. Then if we encounter same sector again then our answer will be distance traveled to reach that sector until now — distance traveled to reach that sector earlier. It would be multiple of some number, we would just find for what multiple the answer exists.

My code

#include <bits/stdc++.h>
#define int long long int

const int N = 1e6 + 1;

int query(char sign, int k){
    std::cout << sign << " " << k << std::endl;
    int ans;
    std::cin >> ans;
    return ans;
}

void print_ans(int res){
    std::cout << "! " << res << std::endl;
}

void solve() {

    int n;
    std::cin >> n;

    int sum = 0;
    std::map <int, int> mp;
    mp[n] = sum;

    int r = rand() % N;
    sum += r;
    int q = query('+', r);

    while(mp.find(q) == mp.end()) {
        mp[q] = sum;
        r = rand() % N;
        sum += r;
        q = query('+', r);
    }

    int d = sum - mp[q];
    int p = q;

    std::set <int> ans;
    
    for(int i = 1; i * i <= d; i++) {
        q = query('+', d / i);
        if(p == q) {
            ans.insert(d / i);
        }
        q = query('-', d / i);
        q = query('+', i);
        if(p == q) {
            ans.insert(i);
        }
        q = query('-', i);
    }

    print_ans(*ans.begin());
    
}

signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    solve();
}

Can anyone explain Binary Search solution for D? I got the intuition but couldn't do it

How answer to B is k > 30 ? n + 1 : Math.Min(n + 1, 1 << k), basically how number of ways is being counted?

When will Editorals come out...? Hoping it!

could land into double digit rank for the first time, if not hacked

G2: The (de)merit of asking randomization algorithm under the ICPC rules: resubmit makes no damage

can anyone please explain what the statement of Problem A is trying to say?Thanks in advance.

Can someone check why my binary search solution to D times out? It's supposed to run in O(n log n), but I can't figure out what's going wrong.

My first contest, solved 4 problems :) Can anyone tell how we can hack anyone's solutions or how to come up with any corner testcase which can be used for hacking? Thanks in advance

Can anyone explain E and how to solve it ??

NumberOfWaysForces :))

How did D get so many solutions? It was extremely difficult.

Can someone pls give me any hints for problem F?

Solved problem 1840E - Character Blocking in $$$O(q\times n$$$). Submission. It works because comparison of two strings in C++ works in $$$O\left(\dfrac{n}{16}\right)$$$ (it is possible to compare $$$16$$$ bytes ($$$256$$$-bit registers) per single operation by activating GCC pragmas).

UPD. Hacked!

UPD 2. Wrote new solution which is still alive.

Can some1 please kindly point out what is so terribly wrong with my solution of E: 208819873.

I tried looking at the tests (my solution fails exactly on second pretest token number 5352, test case number appears to be 1665) but it doesn't make much sense to me because the strings appear to be in uppercase (unless I'm missing some silly mistake with my input).

I try to hack the solution of problem F using the following generated test cases, and it just give me "unexpected verdict", what is happening, can problem author fix this?

import sys
sys.stdout.write("10000\n")
for _ in range(10000):
    sys.stdout.write("1 1\n")
    sys.stdout.write("100\n")
    for i in range(100):
        sys.stdout.write(str(i+1)+" "+str(1)+" "+str(1)+"\n")

Can someone tell me why when i try to hack i have message : Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "��1" found (stdin, line 1)]

Also whole test on codeforces has a lot of this random "�" question marks.

PLEASE TELL ME THE INTUITION BEHIND THE G1/G2 PROBLEM???

Reads problem statement for D, sees that time limit is 3s => neuron activation => immediately starts coding out binary search.

F: Holy, the TL is magically changed 3s instead of 1s, and my 100+ successful hacks are disappeared and left -85...

My hacking case is here, this isn't exist in the pretest:

1
10000 1
100
10000 1 10000
10000 1 10000
...

AC A,B,C,D. It's so good!!! Thanks diskoteka,pavlekn,playerr12,isosto and their friends for this great contest.

A very good div3 has increased my rating

I am not a trusted participant (I had given only 2 contests before this), will my rating get increased on the basis of this contest?