[Official] May Long 2020 - Post-contest discussion - Live stream session

admin · April 30, 2020, 7:15am

Hey all,

We plan to have an informal live stream for discussing the problems of May Long Challenge 2020.

The details are as follows:

Agenda:
Discussion of MAY20 problems
Session Panelist:
Rajarshi Basu and others.
Date-Time:
Session 1: Covering the first 5 problems.
12th May 2020.
15:30 IST to 17:00 IST
To register:
If you are interested just register by clicking on the “Going” button below the title of this post at the top. You will get notified with the Zoom meeting details 30 minutes before the session.
We will also be posting the meeting details as an update on this post at the start of the session.
Note: Entry to the Zoom session will be on first come first serve basis - limited to 100 seats.
Platform for video conferencing:
Zoom Meetings
Rest of the participants can join live on CodeChef’s YouTube channel , where the discussions will be parallely streamed.

If there are any specific queries that you have from these problems, please post them below after the contest, and we will try to answer them during the session.

[Update1] Zoom Meeting details:
https://us02web.zoom.us/j/89036811966?pwd=RVhlN3N2TE5KNi85bldaTTg3Nzlxdz09

Meeting ID: 890 3681 1966
Password: 120949

[Update2] Catch the session live on YouTube here: [Official] CodeChef May Long Challenge - Post Contest Discussion - Part 1 - YouTube

[Update3] Kindly share your valuable feedback here: https://forms.gle/HgYpw6ZBGoLpwffY6

i_64 · April 30, 2020, 7:26am

Is the limit 100 or 500, the next to the going button it says “499 left”

admin · April 30, 2020, 1:25pm

Zoom has a limit of 100. 500 is an arbitrary upper bound. Youtube can handle any number of viewers who come after the Zoom capacity is filled.

admin · May 11, 2020, 9:16am

swa_raz · May 11, 2020, 3:42pm

In the triple sort editorial it said that knowledge of permutation groups was required to solve, so I looked it up before proceeding further. Could you guys spend a couple of minutes towards the end of the video on recommending some resources that a newbie can follow to learn some of the maths thats required for competitive coding?

dcoderpikachu · May 11, 2020, 7:29pm

Not actually brother…It was a implementation based question. It hardly used any permutations. But I too think permutations can be given a moment or two.
Happy coding. Best wishes.

sayan_1999 · May 11, 2020, 7:56pm

@dcoderpikachu Sir, can you explain your approach for the TRIPLE sort problem?

dgupta0812 · May 12, 2020, 8:40am

TRPLSRT
I have solved the question using the greedy approach by choosing three indexes and swapping…
But I couldn’t get my head around the solution using permutation cycles and transpositions.
Can you just spare few minutes in explaining the concept of permutation cycles, transposition, representing permutation as a product of transpositions and how are we using them to construct a solution by giving examples and solve them ?
I know it’s a lot to ask but it will be very grateful of you. Thanks in advance!!

dcoderpikachu · May 12, 2020, 9:42am

Hii sayan…I solved my problem in three steps

I used a loop to find the location of "i"th element( here I starts from 1 and ends at N ). Suppose that the number is currently at its correct position( i.e. position[i]== i ) then i would just increment “i” and do no changes to the number. But suppose it is at an arbitrary location–
if at some incorrect position then I would search for the value arr[i]…i.e. number that is present at the position where the number “i” need to be placed. So arr[i] will be choosen as the second number.
Now for the third number again two cases are possible( actually this was a tricky part )
for this I will either choose the next number to be arr[arr[i]] OR the next number to “i” which is not at its correct position and is not equal to arr[i] .

After finding the three numbers I just performed right shift as depicted in question(don’t forget to count the number of times the loops run as this will be equal to the number of shifts required in the output)

PS: I won’t say my code was good as it was lacking sophistication and elegance that a perfect code must have…but it was correct for all the test cases that I could find.
PPS: It is nearly of 250 lines because I love hitting ENTER key a lot but if you write it neatly it can be implemented in 70-80 lines.

I hope you got my approach but I still suggest to use editor’s approach as it is better than mine…if you just want answer( which you musn’t) then you’re welcome to use mine.
this is my solution
best wishes for future
happy coding

techie_pals · May 12, 2020, 10:00am

We have updated the Zoom meeting details and YouTube live stream details on the main post.

Looking forward to see you all join.

sayan_1999 · May 12, 2020, 10:29am

How are you confident that your code will be able to sort nos. in N/2 steps all the time?And if it does not, then actually it’s impossible to sort them…how do you prove that?

hackxsaras · May 12, 2020, 10:39am

We think too similarly…
AC in all except last

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define tc int t;cin>>t;while(t--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff(i,a,b) for(int i=a;i<b;i++)
#define fb(i,b,a) for(int i=b;i>a;i--)
#define ffi(i,a,b,c) for(int i=a;i<b;i+=c)
#define fbi(i,b,a,c) for(int i=b;i>a;i-=c)
#define clin(s) getline(cin,s)
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define ub upper_bound
#define lb lower_bound
int main() {
	//freopen("rt.txt","r",stdin);
	fio;
    tc{
        int n,k,i,j;
        cin>>n>>k;
        vector<int> arr(n);
        ff(i,0,n){
            cin>>arr[i];
        }
        if(is_sorted(all(arr))){
        	cout<<"0\n";
        	continue;
		} 
		int nsteps=0;int count=0;
		int num=0;
		bool stopsearch=false;
		vector<vector<int>> rec;
		int start=0,actual=0;
		ff(i,0,k){
		    vector<int> tmp;
	        ff(j,start,n){
	            if(arr[j]!=j+1){
	                if(tmp.size()==0)start=j;
	                tmp.pb(j);
	                tmp.pb(arr[j]-1);
	                int q=arr[tmp[1]]-1;
	                if(q!=tmp[0]&&q!=tmp[1]){
	                    tmp.pb(q);
	                    break;
	                }
	                j=n-1;
	                while(j>tmp[0]){
	                    if(arr[j]!=j+1&&j!=tmp[1]){
	                        tmp.pb(j);
	                        break;
	                    }
	                    j--;
	                }
	                if(tmp.size()==2&&tmp[1]-tmp[0]==2){
	                    tmp.pb(tmp[0]+1);
	                    break;
	                }
	                else if(tmp.size()==2){
	                    break;
	                }
	            }
	            if(tmp.size()==3)break;
	        }
	        if(tmp.size()==3){
	            nsteps+=1;
	            if(count!=0)start=tmp[0]-count;
	            count=0;
	            if(rec.size()>0&&rec[rec.size()-1]==tmp){start++;}
	        	rec.pb(tmp);
	        	int tmpi=arr[tmp[2]];
	        	arr[tmp[2]]=arr[tmp[1]];
	        	arr[tmp[1]]=arr[tmp[0]];
	        	arr[tmp[0]]=tmpi;
	        }
	        else{
	            i--;
	            start++;
	            count++;
	            if(count>2)break;
	            continue;
	        }
	        if(stopsearch)break;
	    }
	    if(is_sorted(all(arr))){
	        cout<<nsteps<<"\n";
	        for(int i=0;i<rec.size();i++){
	        	cout<<rec[i][0]+1<<" "<<rec[i][1]+1<<" "<<rec[i][2]+1<<"\n";
	        }
	    }
	    else{
	    	cout<<"-1\n";
		}
    }
	return 0;
}

dcoderpikachu · May 12, 2020, 5:27pm

ohh wow…I was purely lucky to get AC I assume. Your code is the same…great to see someone thought the same

dcoderpikachu · May 12, 2020, 5:31pm

No brother I haven’t said it will sort in N/2 times.
I just kept sorting them till they are not completely sorted.
I don’t actually even think there is a fixed number till which we have to sort. Just iterate through the whole array till we get sorted string, That is what I meant to say. I know it is tough to make someone else understand your code through language

sayan_1999 · May 12, 2020, 6:51pm

you got me wrong,I want to say how can you guarantee that your algo will sort in <=N/2 steps cz that is the minimum value in third subtask?and if it does not, then how you guarantee that it cannot be done in any other way?

dcoderpikachu · May 12, 2020, 7:00pm

ohh that…well that’s what we call try and error…I wrote a lot of versions of my code and did their dry run. Initialy while I was doing on paper, I was already sure that this method will work( AMOF I thought of algo in such a way that it sorts within N/2 and suppose that it actually gets sorted but the count variable is greater than N/2 then of course it will be returning “-1” in output.

In simple words, first I sorted the string and then checked if the number of shifts were in the range or not.

hackxsaras · May 13, 2020, 12:41am

The thing is it atleast sorts two positions( or three) in a single shift