While solving Skibidi Table problem, (problem link: https://mirror.codeforces.com/contest/2093/problem/D ) I was wondering How to Generate the Pattern->

Number of Rows: $$$2^n$$$

Number of Columns: $$$2^n$$$

Number of Cells: $$$2^{2n}$$$

$$$n=1:$$$

1  4

3  2

$$$n=2:$$$

1   4   13  16 

3   2   15  14 

9   12  5   8 

11  10  7   6

$$$n=3:$$$

1   4    13   16  49  52  61  64 

3   2    15   14  51  50  63  62 

9   12   5    8   57  60  53  56 

11  10   7    6   59  58  55  54 

33  36   45   48  17  20  29  32 

35  34   47   46  19  18  31  30 

41  44   37   40  25  28  21  24 

43  42   39   38  27  26  23  22

And so on......

An idea of implementing it by Recursion came to my mind Alhamdulillah!

As for each case, we are first entering the $$$1st$$$ cell, then the $$$4th$$$ cell, then the $$$3rd$$$ cell, then $$$2nd$$$ cell. Recursively calling it, we can store the pattern in an array & print it to get the pattern!

Code:

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

const int n=1000;
int arr[n][n];

void fillArray(int x,int y,int p,int val){
	if(p==1){
		arr[x][y]=val;
		return;
	}

	fillArray(x,y,p/2,val);
	fillArray(x+p/2,y+p/2,p/2,val+p*p/4);
	fillArray(x+p/2,y,p/2,val+2*p*p/4);
	fillArray(x,y+p/2,p/2,val+3*p*p/4);
}

int main(){
	int n;
	cin>>n;
	int p=pow(2,n);
	fillArray(0,0,p,1);
	for(int i=0;i<p;i++){
		for(int j=0;j<p;j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
}

You can check it by running the code!!!

Here is a simple problem made by me. Solve it & Give it a rating in comment section if you want.

Problem Name: Range Mex

You are given $$$n$$$ non-negative integers- $$$a_1,a_2,\ldots,a_n$$$. You have to find $$$mex_i$$$ for each $$$1\le i\leq n$$$ such that $$$mex_i$$$ is the mex of all numbers in the array except the $$$i-th$$$ number. e.g. if $$$a=$$${$$${2,5,0}$$$},

$$$mex_1 = mex(a_2,a_3)=mex(5,0)=1$$$

$$$mex_2 = mex(a_1,a_3)=mex(2,0)=1$$$

$$$mex_3 = mex(a_1,a_2)=mex(2,5)=0$$$

Input:

The first line contains a positive number $$$t (1\le t\le 10^4) - $$$ the number of test cases. The description of the test cases follows:

Each test case consists of 2 lines.

The first line contains a positive integer $$$n (1\le n\le 2\cdot 10^5) - $$$indicating the size of array $$$a$$$.

The second line contains $$$n$$$ non-negative integers $$$a_1,a_2,\ldots,a_n (0\le a_i\le 10^9) - $$$ the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output:

For each test case, output $$$n$$$ integers- the $$$i-th$$$ of them indicating $$$mex_i$$$.(i.e. $$$mex_1, mex_2, mex_3,\ldots, mex_n)$$$

Examples:

Input:

5
0 1 2 3 4
5
1 0 2 5 9
2
1 2
3
1 0 2
4
4 7 0 1 

Output:

0 1 2 3 4 
1 0 2 3 3 
0 0 
1 0 2 
2 2 0 1 

Notes:

Here for the first test case,

$$$mex_1 = mex(1,2,3,4) = 0$$$

$$$mex_2 = mex(0,2,3,4) = 1$$$

$$$mex_3 = mex(0,1,3,4) = 2$$$

$$$mex_4 = mex(0,1,2,4) = 3$$$

$$$mex_5 = mex(0,1,2,3) = 4$$$

//﷽ [Bismillaahir Rahmaanir Raheem]

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

#define ll long long int
#define ul unsigned long long int
#define ld long double
#define TT int TC;cin>>TC;for(int ti=1;ti<=TC;ti++)
#define TT1 int TC=1;for(int ti=1;ti<=TC;ti++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define ans_YN if(ans)YES;else NO;
#define pb push_back
#define pr_q priority_queue
#define F first
#define S second
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define B begin()
#define E end()
//#define endl "\n"
ll ceill(ll a,ll b){if(a>=0){if(a%b==0)return a/b;else return a/b+1;}else return a/b;}//Here b>0 for being divisor
ll flr(ll a, ll b){if(a>=0){return a/b;} else {if(a%b==0) return a/b; else return a/b-1;}}//Here b>0 for being divisor
ll GCD(ll a, ll b){ ll ans=__gcd(a,b);if(ans<0)ans=-ans;return ans;}
ll LCM(ll a, ll b){ return (a*b)/(GCD(a,b));}
ll rem(ll a, ll b){ if(a>=0) return a%b; else{a=-a; return (b-a%b)%b;}}
int const mod=1e9+7;
int const AND=1073741823;

int main()
{
    fastio
    TT
    {
        ll n;
        cin>>n;
        ll a[n];
        ll mex;
        map<ll,ll>occ;
        for(int i=0;i<n;i++){
            cin>>a[i];
            occ[a[i]]++;
        }

        for(ll i=0;i<=n;i++){
            if(occ[i]==0){
                mex=i;
                break;
            }
        }

        for(int i=0;i<n;i++){
            ll mexx=mex;
            if(occ[a[i]]==1){
                mexx=min(mex,a[i]);
            }
            cout<<mexx<<" ";
        }
        cout<<endl;

        
    }
    return 0;
}

This is my first own problem created on Polygon! So I am excited!

I request you to try first before reading the tutorial!

You can submit your solution through this invitation link: https://mirror.codeforces.com/contestInvitation/1d814de17ea46b3255e85ecac66b0fd6adcf138d

Problem Name: Arithmetic Geometric Series

time limit per test: 1 second

memory limit per test: 256 megabytes

Problem Description

Salehin has recently learnt about Arithmetic Series (where the difference between 2 consecutive terms remains constant e.g. $$$1+2+3+\ldots +n$$$ Here Constant Difference $$$=2-1=3-2=1$$$) and Geometric Series (where the ratio between 2 consecutive terms remains constant e.g. $$$3+3^2+3^3+\ldots 3^n$$$ Here Constant Ratio $$$=\frac{3^2}{3}=\frac{3^3}{3^2}=3$$$).

Now an idea came to his mind to combine or mashup these 2 series and he named it "Arithmetic Geometric Series"! Arithmetic Geometric Series forms of 2 parameters: $$$x$$$ & $$$n$$$. Arithmetic Geometric Series for $$$x$$$ & $$$n$$$, $$$AG(x,n)=x+2\cdot x^2+3\cdot x^3+4\cdot x^4+\ldots +n\cdot x^n=\sum_{k=1}^{n}{k\cdot x^k}$$$

Salehin wants to determine the values of the series for different values of $$$x$$$ & $$$n$$$. But he is very tired to do such calculations! So he needs your help!

Hence you have to determine the value of $$$AG(x,n)$$$ for given values of $$$x$$$ and $$$n$$$.

Since the answer can be very large, output $$$AG(x,n)$$$ modulo $$$998$$$ $$$244$$$ $$$353$$$.

Input

The first line contains one integer $$$t(1\leq t\leq 10^4)-$$$ the number of test cases. Then $$$t$$$ test cases follows.

Each test case consists of only one line which contains $$$x(0\leq x\leq 10^5)$$$ & $$$n(1\leq n\leq 10^9)-$$$ the parameters of Arithmetic Geometric Series.

Output

For each test case, print one integer $$$-$$$ $$$AG(x,n)$$$ modulo $$$998$$$ $$$244$$$ $$$353$$$.

Example

input

3 5
5 4
4 7
100000 1000000000
0 4

output

1641
2930
145636
110642754
0

Note

In the first test case, $$$AG(3,5)= 3+2\cdot 3^2+3\cdot3^3+4\cdot 3^4+5\cdot3^5=1641$$$

In the second test case, $$$AG(5,4) = 5+2\cdot5^2+3\cdot5^3+4\cdot5^4=2930$$$

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

#define ll long long int
#define ul unsigned long long int
#define ld long double
#define TT int TC;cin>>TC;for(int ti=1;ti<=TC;ti++)
#define TT1 int TC=1;for(int ti=1;ti<=TC;ti++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define ans_YN if(ans)YES;else NO;
#define pb push_back
#define pr_q priority_queue
#define F first
#define S second
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define B begin()
#define E end()
//#define endl "\n"
ll ceill(ll a,ll b){if(a>=0){if(a%b==0)return a/b;else return a/b+1;}else return a/b;}//Here b>0 for being divisor
ll flr(ll a, ll b){if(a>=0){return a/b;} else {if(a%b==0) return a/b; else return a/b-1;}}//Here b>0 for being divisor
ll GCD(ll a, ll b){ ll ans=__gcd(a,b);if(ans<0)ans=-ans;return ans;}
ll LCM(ll a, ll b){ return (a*b)/(GCD(a,b));}
ll rem(ll a, ll b){ if(a>=0) return a%b; else{a=-a; return (b-a%b)%b;}}
int const mod=998244353;
int const AND=1073741823;

//Binary Power Function
ll POW(ll a, ll b){
    if(b==0) return 1;
    if(b==1) return a;
    ll p=POW(a,b/2)%mod;
    if(!(b&1))return (p*p)%mod;
    else return (((p*p)%mod)*a)%mod;
}

//Modular Multiplicative Inverse
ll inversemod(ll x, ll m){
    // (x^(m-2))%m = x^(-1) mod m
    // Condition GCD(x,m)=1
    ll ans=(POW(x,m-2))%m;
    return ans;
}

int main()
{
    fastio
    TT
    {
        ll x,n;
        cin>>x>>n;
        //x+2x^2+...+nx^n
        ll ans;
        if(x==1)ans=((n%mod*(n+1)%mod)%mod*inversemod(2LL,mod))%mod;
        else ans=(rem(((n*POW(x,n+2))%mod-((n+1)*POW(x,n+1))%mod+x%mod),mod)*inversemod(POW(x-1,2),mod))%mod;
        //Here rem function used to convert negative mod to non-negative
        cout<<ans<<endl;
    }
    return 0;
}

In C++, for output, we usually write cout<<x;

But if we want to write in reverse-> x>>cout;

Same case for cin. Instead of cin>>x, if we want to write x>>cin.

We can do it in class.

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

class number{
    int x;
public:
    number(){}
    number(int x):x(x){};
    istream& operator>>(istream& in){
        cin>>x;
        return in;
    }
    ostream& operator<<(ostream& out){
        cout<<x;
        return out;
    }
};

int main(){
    number n;
    n>>cin;
    n<<cout;
    return 0;
}

Problem Name: Chocolate Bunny

Problem Rating: 1600

Problem Link: https://mirror.codeforces.com/problemset/problem/1407/C

[If I make any mistake, please pardon me & correct me!]

In this problem, we can ask $$$2$$$ indices $$$(x,y)$$$ in 1 query & get $$$P_{x} \bmod P_{y}$$$. Our limitation is we can ask no more than $$$2\cdot n$$$ queries. Here is the main trick! If we were allowed to ask $$$n^{2}$$$ queries, we could easily do it asking ? x y for each $$$x (1- \gt n)$$$ and each $$$y (1- \gt n $$$ except $$$x)$$$

e.g. if $$$n=5$$$, to get $$$a[3]$$$ we can ask

?1 3

?2 3

?4 3

?5 3

All these results must be all numbers $$$1 \lt =r \lt a[3]$$$($$$r$$$ can also be $$$0$$$ for some numbers), so $$$a[3]=max($$$ all remainders $$$)+1$$$

But as we can ask no more than $$$2\cdot n$$$ queries, we have to focus on the mathematical property of $$$MOD$$$.

Let's think about $$$a \bmod b$$$ & $$$b \bmod a$$$: If $$$a \gt b$$$, then $$$a \bmod b \lt b$$$; and $$$b \bmod a = b \gt a \bmod b$$$

So if we ask ? x y and ? y x, we get $$$a[x]\bmod a[y]$$$ and $$$a[y]\bmod a[x]$$$, Between these, the max one is the real one that exists in the Permutation & the min one is the changed remainder of the max one. So if $$$a[x]\bmod a[y] \gt a[y]\bmod a[x]$$$, then $$$P[x]=a[x]$$$, then $$$x++$$$ and compare $$$x$$$ with the previous $$$y$$$.And if $$$a[x]\bmod a[y] \lt a[y]\bmod a[x]$$$, $$$P[y]=a[y], y=x, x++$$$.[Here we are iterating over x]

Thus we can get $$$(n-1)$$$ numbers except the max one which we all know to be $$$n$$$.

Here Queries used $$$2\cdot (n-1)=2\cdot n-2$$$

Complexity: $$$O(2\cdot n)$$$

My Submission: https://mirror.codeforces.com/contest/1407/submission/320641205

Solution:

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


#define TT1 int TC=1;for(int ti=1;ti<=TC;ti++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int main()
{
    fastio
    TT1
    {
        int n;
        cin>>n;
        int a[n+1];
        for(int i=1;i<=n;i++)a[i]=n;
        int j=1;
        for(int i=2;i<=n;i++){
            int r1,r2;
            cout<<"? "<<j<<" "<<i<<endl;
            cin>>r1;
            cout<<"? "<<i<<" "<<j<<endl;
            cin>>r2;
            if(r1>r2){
                a[j]=r1;
                j=i;
            }
            else{
                a[i]=r2;
            }

        }
        cout<<"! ";
        for(int i=1;i<=n;i++)cout<<a[i]<<" ";
            cout<<endl;

        
    }
    return 0;
}

Since Nowadays, cheating on codeforces has increased to a great extent, what about if there is an approval by the institution under which a registered participant is. Can this system be made (somewhat like IUPC or ICPC)? In this system, after registration for a contest, a participant should be approved to participate in the contest by the institution. If a participant is proved cheat by the institution, then that institution will not approve to participate in the contest.

Or there should be such a system that every contestant must be under an institution AND the institution may send an application to codeforces Headquarters to ban the id of the participants caught fraud by the institution.

CHEATING causes DEMOTIVATION to the HONEST participants! So it is high time!