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