I am Beginner and always stuck into 3rd-4th Problem of Weekly Contest .NEED ADVICE AND SUGGESTION

general
,
1

I always stuck into 4th Problem of Weekly Contest .How can i improve it so i can solve atleast 4 problem of WEEKLY CONTEST.

First two are always cakewalk but 3rd problem usually take a lot of time and effort and in 4th and onward i cannot even think the approach. :zipper_mouth_face:

Can anyone help me here and give a piece of advice

2

There are some problems that will seem not to be logical or that theyā€™ll be very hard to imagine at first sight. They have this cute statement: ā€œyou (can)/(have to) do X amount of operationsā€ to this array/string", like this Permutation Disturbance Practice Coding Problem - CodeChef problem you are talking about.

If you face this kind of problems, itā€™s a good idea to give yourself a couple of minutes of writing down with pencil and paper examples of this so-called operation the problem states.

Think of counter examples, think of how you could force the operations work for you. Play with the operation so you can learn how it works and what it does. After a couple of examples that you can see with your eyes in a notebook, youā€™ll start to spot patterns.

In this problem, you will start wondering things like:

  • ā€œIf I run each index and find a number that correlate with its index, then Iā€™ll have to swap itā€
  • ā€œBut if I swap it, would it be a risk that I bring a number to its right positionā€
  • ā€œThat makes no sense, because if Iā€™m moving the number in a permutation from its position, by definition Iā€™m moving the disturbance oneā€

And so on, so on.
Donā€™t be afraid to give yourself a couple of minutes of writing down and doing try and failure from what you are learning from that so-called operation.

I originally solved it on Python, but Iā€™ll leave you a C++ equivalent I just made for this:
Feel free to ask any doubt if you donā€™t understand something

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

void solve(){

    ll N;
    cin >> N;

    // I fill my vector with right size    
    vector<ll> A(N);
    for(ll i=0; i<N; i++){
        cin >> A[i];
    }
    
    /*
     I'll try to shift the numbers to their right
     There's not a strong numberical reason to do this
     Or maybe it is, who cares?
     I spotted this after try and failiring a couple of minutes in my notebook
    */
    ll swaps = 0;
    for(ll i=0; i<(N-1); i++){
        ll num = i+1;
        if (num == A[i]){
            swap(A[i], A[i+1]);
            swaps++;
        }
    }
    
    // I have to be sure my last element be "distubed" too
    if (A[N-1] == N){
        swap(A[N-1],A[N-2]);
        swaps++;
    }

    cout << swaps << "\n";

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T;

	cin >> T;
	while(T--){
		solve();
	}
}

My (original) Python solution

for T in range(int(input())):
    
    N = int(input())
    A = list(map(int,input().strip().split()))
    
    swaps = 0
    for i in range(N-1):
        num = i+1
        if num == A[i]:
            A[i], A[i+1] = A[i+1], A[i]
            swaps += 1
    
    if A[N-1] == N:
        A[N-1], A[N-2] = A[N-2], A[N-1]
        swaps += 1
    
    print(swaps)
2 Likes
3

Practise!
Solve problems around that Q rating to be specific or you can use codechef list for help.
for ex: 1000 to 1400 difficulty problems Programming Practice Problem Course Online - CodeChef