Codeforces Round 967 (Div. 2) Solutions with mathematical proofs

Revision en2, by InvKhush, 2024-08-20 21:58:23

I am starting to share brief solutions for problems of contests and try to provide with a fundamental mathematical proof inorder to be sure intuitively as well as mathematically (will try to keep it brief but fundamentally strong)

Codeforces Round 967 (Div. 2)

Problem A : Make All Equal: A simple problem where obviously since we know that at the end only a single unique number along with its duplicates will remain and we can remove any 1 number from the array at once, thus solution can be

c = no. of occurrences of highest occuring element in the array

ans = n — c

//SAMPLE CODE
int n;
cin>>n;
vector<int> a(n);
map<int,int> mp;
for(int i=0;i<n;i++){
    cin>>a[i];
    mp[a[i]]++;
}
int ans=0;
for(int i=0;i<n;i++){
    ans=max(ans,mp[a[i]]);
}
cout<<n-ans<<endl;

Problem B : Generate Permutation: Problem framing was a little tricky but in a one line the problem is just to find a permutation of [1...n] such that irrespective of the typewriter i use, i will need some x number of carrier returns in order to type that permutation. Note : x carrier returns (same) for both the typewriters.

Most common thought to strike is make permutations that can be traversed in similar way from both sides eg. 2 3 1 2 4 5 3 1 2 4 6 7 5 3 1 (Toggle between end and start, i hope you get it)

Try to simulate it in your brain and see that if n is odd : for both typewriters the number of carrige returns will be same if n is even : it won't be same

//SAMPLE CODE
int n;
cin>>n;
if(n%2==1){
    for(int i=2;i<n;i+=2){
        cout<<i<<" ";
    }
    cout<<n<<" ";
    for(int i=n-2;i>0;i-=2){
        cout<<i<<" ";
    }
    cout<<endl;
}
else{
    cout<<-1<<endl;
}

[UPDATING SOON]

Tags 967 (div. 2)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English InvKhush 2024-08-21 14:41:45 0 (published)
en7 English InvKhush 2024-08-21 10:37:46 2 Tiny change: ''?'<<" "<<'a'<<" "<<b<<' -> ''?'<<" "<<a<<" "<<b<<' (saved to drafts)
en6 English InvKhush 2024-08-21 10:31:04 429 (published)
en5 English InvKhush 2024-08-21 10:29:19 98
en4 English InvKhush 2024-08-21 10:27:24 664 (saved to drafts)
en3 English InvKhush 2024-08-20 22:21:54 13 Tiny change: 'es\neg. \n2 3 1\n2' -> 'es\neg. \n\n2 3 1\n2'
en2 English InvKhush 2024-08-20 21:58:23 43 (published)
en1 English InvKhush 2024-08-20 21:54:26 1921 Initial revision (saved to drafts)