Блог пользователя InvKhush

Автор InvKhush, история, 4 часа назад, По-английски

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]

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится