Thursday, September 29, 2016

Argon 2015 - TrekAndSwim

In this post I am going to discuss the solution for another great Codility problem.
Because of the copyrights I can't paste the problem description here so to view the problem click here.

As you may know most of the Codility problems are tricky and when Codility marks it as hard you should realize that you are going to squeeze your mind to get it resolved so I really envy those who could solve this issue from the first time in less than 30 mins. sometimes I really wish to contact any of them to see how brilliant they are, However lets start thinking in this problem and how to resolve it.

I am going briefly summarize how I think in this problem and how I resolved it.

first imagine you have this array

                                                             {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

So I am going to get the position of the first ZERO ( which meets the requirement of the tourist to enjoy swimming in the sea), also I am going to get the position of the last ONE.
                                                            {1, 1, 0, 1, 0, 0, 1, 1,0,0}
In our example the position of the first ZERO is 2  and the position of the last ONE is 7.

Now lets get the longest sea trip that starts from the first zero and ends with zero. ( it should end with Zero even if adding ones wont make it fail).
                                                           
                                                            {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

Now we realized that the tourist have chance to spend the vacation the way he wants ( first part on the sea and the second part hiking in the mountain)

                                                            {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

But our tourist here is pretty greedy he is looking for the longest vacation so we should try to expand the vacation as much as we can.

it can be done by iterating on the vacation from the last day to the start day and see if we can add hiking days to the second part without making the sea trip fails also we should add hiking days from the first part to the second part IF AND ONLY IF it will let the second part eligible to get more swim days from the rest of the reaming available days.

In our example we can't add more hiking days from the first part to the second part because it will lead that the second part of the vacation won't meet the criteria so the whole vacation will fail but the second part already eligible to add more days from the reaming days on its right.

so we can add one more day from its right

                                                            {1, 1, 0, 1, 0, 01, 1, 0, 0}

lets get to the first part of the vacation. the question ?? is it eligible to add more days from its left ?  the answer simply yes so we should calculate how many days we should add from left ( expand the first part to left).

in our example we can add one more day from the left.

                                                            {1, 1, 0, 1, 0, 01, 1, 0, 0}

Now we got the longest possible vacation.

lets move to translating the description above to a java code.



package trekandswim;

import java.util.Arrays;

/**
 *
 * @author ahmad
 */
public class TrekAndSwim {


    public static void main(String[] args) {
        // TODO code application logic here
        TrekAndSwim tr = new TrekAndSwim();
        int A[];
        int result = 0;
        
        
        
        
        //////////Test the the results 
        A = new int[]{1, 1, 0, 1, 0, 0, 1, 1, 0, 0};
        result = tr.solution(A);
        System.out.println("===========");
        System.out.println("The Result is    " + result);
        System.out.println("****************************************");

    }

    public int solution(int[] A) {
      

        int firstzero = -1;
        int lastone = -1;
        int seaDaysCount = 0;
        int seaEndIndex = 0;
        int seaArraySize = 0;

        int mountainStartIndex = 0;
        
        /////get the first zero and last one 
        for (int i = 0; i < A.length; i++) {
            if (firstzero == -1 && A[i] == 0) {
                firstzero = i;
            }
            if (A[i] == 1) {
                lastone = i;
            }
        }
        // return 0 if  no days for swim or no days for hike or no no hike day after a swim day
        if (firstzero == -1 || lastone == -1 || firstzero >= lastone) {
            return 0;
        }
        
        //get the longest sea trip that ends with ZERO
        int totalNumOfZeros = 0;
        for (int i = firstzero; i <= lastone; i++) {

            if (i == firstzero) {
                seaEndIndex = i;
            }
            if (A[i] == 0) {
                totalNumOfZeros++;
            }

            if (A[i] == 0&&seaTripNotFail(i - firstzero + 1, totalNumOfZeros)) {
                seaDaysCount = totalNumOfZeros;
                seaEndIndex = i;
            }

        }
        
        /// get the sea trip size
        seaArraySize = seaEndIndex - firstzero + 1;

        if (mountainStartIndex - seaEndIndex > 1) {
            return 0;
        }
        int startItrator = lastone;
        int tempones = 0;
        int tempZeros = 0;
        int tempEffectiveZeros = 0;
        int extraDays = 0;
        //check the possiblity of expanding the second part to the right by either adding more hike days from the first part or if the second part already adds elgiable to add more sea days from its right
        while (startItrator > firstzero) {
            if (extraDays + lastone >= A.length-1) {
                break;
            }
            if (startItrator > seaEndIndex) {
                if (A[startItrator] == 1) {
                    tempones++;
                    int newExtraDays = getExtraDays(tempones, tempZeros);
                    if (newExtraDays > extraDays) {
                        extraDays = newExtraDays;
                    }
                } else if (A[startItrator] == 0) {
                    tempZeros++;
                }
            } else {
                if (A[startItrator] == 1) {
                    tempones++;
                    int newExtraDays = getExtraDays(tempones, tempZeros);
                    if (newExtraDays > extraDays) {
                        int newArraySize = startItrator - firstzero + 1;
                        if (seaTripNotFail(newArraySize, seaDaysCount - tempEffectiveZeros)) {
                            extraDays = newExtraDays;
                            seaArraySize=newArraySize;
                            seaEndIndex=startItrator-1;
                            seaDaysCount=seaDaysCount - tempEffectiveZeros;
                            tempEffectiveZeros=0;
                        }
                    }
                } else if (A[startItrator] == 0) {
                    tempZeros++;
                    tempEffectiveZeros++;
                }
            }
             startItrator--;

        }
//      check if the first part elgiable to expand left or no 
        int expantionValue = arrayExpandLeft(firstzero, seaDaysCount, seaArraySize, A);
        firstzero -= expantionValue;
        seaArraySize += expantionValue;
        
        int mountainTripDuration=lastone-seaEndIndex+extraDays;
        return seaArraySize+mountainTripDuration;

    }
 /// methods to get number of zeros that we can add to the seond part withought making it fail ( the number of ones should be greater than the number of zeros)
    int getExtraDays(int numOfOnes, int numOfZeros) {

        return numOfOnes - numOfZeros - 1;
    }

   
  // method to expand the first part of the trip  to the left side 
    int arrayExpandLeft(int firstzero, int seaDaysCount, int seaArraySize, int[] A) {
        int expantionValue = 0;
        while (seaTripHasExtraSwimDays(seaArraySize, seaDaysCount) && firstzero > 0) {
            if (firstzero == 0) {
                break;
            }

            firstzero--;
            seaArraySize++;
            expantionValue++;

        }
        return expantionValue;
    }
     // cheack if the seatrip is ok with this size and this number of zeros  
    boolean seaTripNotFail(int seaArraySize, int numOfZeros) {

        return numOfZeros - (seaArraySize - numOfZeros) >= 1;
    }
  // cheack if the seatrip is elgiable to add more ones 
    boolean seaTripHasExtraSwimDays(int seaArraySize, int numOfZeros) {

        return numOfZeros - (seaArraySize - numOfZeros) > 1;
    }

}


4 comments:

  1. Thanks so much for this!
    I didn't understand the algorithm exactly - especially this paragraph on how to expand the vacation "it can be done by iterating on the vacation from the last day to the start day and see if we can add hiking days to the second part without making the sea trip fails also we should add hiking days from the first part to the second part IF AND ONLY IF it will let the second part eligible to get more swim days from the rest of the reaming available days."

    Once you find the longest first part that hold the invariant of more than half perfect swimming days, can you extend the 2nd part left and shorten back the 1st part?


    I wrote some code in C++ - but it is NOT correct. It is failing on some edge cases apparently - but I don't know what they are...

    works on [1,0] and [1,0,1,0,0,0,1,1,0,0,1,0,1]
    *********************************
    #include


    bool isLegalVacation(int perfectDays, int totalDays)
    {

    if (totalDays/perfectDays <= 1)
    return true;
    return false;
    }
    int solution(vector &A) {

    int swimVacationDays = 0, trekVacationDays = 0;
    int N = A.size();
    int firstSwimVacationDay=N, lastTrekVacationDay=0, lastSwimVacationDay=N;
    int swimDays = 0, trekDays = 0;


    //find the first '0'
    for (int i = 0; i < N; i++)
    {
    if (A[i] == 0)
    {
    firstSwimVacationDay = i;
    break;
    }
    }

    //find the last '1'
    for (int i = N-1; i > 0; i--)
    {
    if (A[i] == 1)
    {
    lastTrekVacationDay = i;
    break;
    }
    }

    //if last zero is not before last one then return 0
    if (firstSwimVacationDay >= lastTrekVacationDay)
    return 0;

    //extend sea vacation as far as possible to the right, preserving n/2 invariant
    lastSwimVacationDay = firstSwimVacationDay;
    for (int i = firstSwimVacationDay; i < lastTrekVacationDay; i++)
    {
    if (A[i] == 0)
    {
    swimDays++;

    if (isLegalVacation(swimDays, i - firstSwimVacationDay + 1))
    {
    lastSwimVacationDay = i;
    }
    }
    }
    //so swim vacation days are from the first zero to the last zero that preserves n/2 invariant
    swimVacationDays = lastSwimVacationDay - firstSwimVacationDay + 1;

    //try to extend swimming vacation to the left
    for (int i = firstSwimVacationDay - 1; i >= 0; i--)
    {
    //all elements before firstSwimVacationDay are ones, so swimDays is constant
    swimVacationDays++;
    if (isLegalVacation(swimDays, swimVacationDays))
    {
    firstSwimVacationDay--;
    }
    else
    {
    //undo that extra day and don't bother checking to the left any more
    swimVacationDays--;
    break;
    }
    }
    //now count up trek days and trek vacation days
    for (int i = lastSwimVacationDay + 1; i <= lastTrekVacationDay; i++)
    {
    trekVacationDays++;
    if (A[i] == 1)
    {
    trekDays++;
    }

    }
    //try to extend trekking vacation to the right
    for (int i = lastTrekVacationDay + 1; i < N; i++)
    {
    //all elements after lastTrekVacationDay are zeros, so trekDays is constant
    trekVacationDays++;
    if (isLegalVacation(trekDays, trekVacationDays))
    {
    lastTrekVacationDay++;
    }
    else
    {
    //undo that extra day and don't bother checking to the right any more
    trekVacationDays--;
    break;
    }
    }
    //return total vacation days
    return swimVacationDays + trekVacationDays;
    }

    ReplyDelete
  2. Hello Rachel,
    I have quickly reviewed my your algorithm I could realize some cases that your algorithm will fail with, however I would like to focous more on my alglorithm which is pretty close to yours.

    you have a problem with this paragraph
    ""it can be done by iterating ...."

    I will give you an example here that explains what I mean

    Imagine you have the following list

    {1,1,0,0,0,0,0,1,1,1,0,1,1,0,0,0,0,0}

    my first step of algorithm will make the stop vacation starts from first zero and stop on the last zero that make it long so it will start with S0 and ends on E0 on the list bellow

    {1,1,S0,0,0,0,0,1,1,1,E0,1,1,0,0,0,0,0}

    the hiking vacations vacations has 2 hiking days so it can extend one day to right , correct ?

    but let think together, the swim trips have some ones before E0 correct ? do you think the swim trip can denote some ones to the hiking part of vacation that let the hiking part of the vacations extend right more and more ? but of course this shouldn't spoil the sea vacation ??
    the answer on the example above is yes its possible
    if the sea part donates with this part {1,1,1,E0} to the mountain trip it will allow the mountain trip to add more days from the right

    so the new list after denotation will be the following

    {1,1,S0,0,0,0,E0,*1,1,1,1,1,0,0,0,0,0}

    *the start of mountain trip after adding extra days to it from the sea trip.
    now sea trip loses one zero ? but it doesn't effect the validty of it as its still valid but it will allow the mountain trip to add more days from right.

    how to implment the above steps simpli iterator from the lastone to the first zero and check if adding 1's from the sea trip to the mountain trip will lead that mountain trip be able to add more days from right or no ?? of course we may meet some zeros so they should be added as well to the mountain trip but in this case we should check if adding such zeros will make the sea trip fail or no ? if no we should ignore them

    summary: we are shiffting some days from sea trip to mountain trip if and only if shifting those days wont spoil the sea trip and will lead that mountain vacations can add more days.

    hopefully its clear now sorry no HTML here in the comment so I could't use visual effects.

    ReplyDelete
  3. Hello Ahmed.

    I have recently attempted this exercise myself and while I was able to produce an O(n^2) algorithm easy enough I spent most of my allotted time racking my brain trying to come up with an O(n) algorithm but was not able to come up with one. As it was I submitted my n^2 algorithm and while it was correct it totally bombed on performance. I them came across your post while looking for an O(n) algorithm.

    Is it true that the first '0' and last '1' must always be in the optimal solution? At first I thought this wasn't necessarily the case but after dwelling on it for some time I am starting to think it must be. I take it you must have realised this early on and designed your algorithm accordingly.

    Any way, thanks for sharing.
    (:

    ReplyDelete
  4. int solution(vector &A) {
    // write your code in C++11 (g++ 4.8.2)
    //declare
    int firstZero, lastOne;
    //find the first 0
    for (size_t i = 0 ; i < A.size();i++)
    {
    if (!A[i])
    {
    firstZero = i;
    break;
    }
    }
    //find the last 1
    for (size_t i = A.size()-1 ; i >= 0; i--)
    {
    if (A[i])
    {
    lastOne = i;
    break;
    }
    }
    //if lastOne < firstZero ,return 0
    if ( lastOne < firstZero)
    {
    return 0;
    }
    //calculate Zero conuts
    int zeroTotal = 0;
    for (size_t i = firstZero; i <= lastOne; i++)
    {
    if (!A[i])
    {
    ++zeroTotal;
    }
    }
    //find the vacotion point
    int middlePoint = 0;
    int maxzeroGap = 0;
    int maxoneGap = 0;
    int vocation = 0;
    for (size_t i = firstZero; i <= lastOne; i++)
    {

    static int zeroCounts = 0;
    if (!A[i])
    {
    ++zeroCounts;
    }
    if (zeroCounts > (i - firstZero + 1 - zeroCounts) && (zeroTotal - zeroCounts) < (lastOne - i - zeroTotal + zeroCounts))
    {
    int length = 2 * zeroCounts - (i - firstZero + 1);
    if ( length > maxzeroGap)
    {
    middlePoint = i;
    maxzeroGap = length;
    maxoneGap = (lastOne - i - zeroTotal + zeroCounts) - (zeroTotal - zeroCounts);
    }
    }
    }
    if (!maxzeroGap)
    {
    return 0;
    }
    else
    {
    vocation = lastOne - firstZero + 1;
    }
    while ( firstZero && (maxzeroGap-1))
    {
    ++vocation;
    --maxzeroGap;
    --firstZero;
    }
    while ( (lastOne < A.size()-1) && (maxoneGap-1))
    {
    ++vocation;
    --maxoneGap;
    ++lastOne;
    }
    return vocation;
    }

    ReplyDelete