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

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: https://www.youtube.com/watch?v=rzaP4qd-b_M

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

6 Likes

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

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.

1 Like

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?

5 Likes

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.
:smile: Happy coding. Best wishes.

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

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!!

Hii sayan…I solved my problem in three steps

  1. 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–
  2. 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.
  3. Now for the third number again two cases are possible( actually this was a tricky part :wink: )
    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 :smile: 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 :smile:

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

Looking forward to see you all join.

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?

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

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

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 :sweat_smile:

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?

1 Like

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.

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