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

Revision en8, by InvKhush, 2024-08-21 14:41:45

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;
}

Problem C : Guess The Tree: In order to understand this one, you will need to agree with a statement which is as follows:

In a tree i can consider any node as a root node and then it will lead a new valid tree with same edges but a different view.

I will consider '1' as the root node and will try to query every other node with the root node. Let me explain how it goes:

? a b

? 1 2

? 1 3

? 1 .

? 1 .

? 1 n

like this... (n-1 queries)

if from each query somehow i could find the parent of b then for each node i will know it's parent and thus the edges.

Understand this and you are done

//SAMPLE CODE
void helper(int a, int b, vector<int>& parent){
    cout<<'?'<<" "<<a<<" "<<b<<endl;
    int x;
    cin>>x;
    if(x==a) parent[b]=a;
    else helper(x,b,parent);
}

void solve() {
    int n;
    cin>>n;
    vector<int> parent(n+1);
    for(int i=2;i<=n;i++) helper(1,i,parent);
    cout<<"!"<<" ";
    for(int i=2;i<=n;i++) cout<<i<<" "<<parent[i]<<" ";
    cout<<endl;
}
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)