algorithm - Codility EvenSums Game -

-

i'm trying finish codility challenge improve programming skills. details of challenge here.
copy problem statment down here also.

even sums game 2 players. players given sequence of n positive integers , take turns alternately. in each turn, player chooses non-empty slice (a subsequence of consecutive elements) such sum of values in slice even, removes slice , concatenates remaining parts of sequence. first player unable make legal move loses game.

you play game against opponent , want know if can win, assuming both , opponent play optimally. move first.

write function:

string solution(vector< int>& a);

that, given zero-indexed array consisting of n integers, returns string of format "x,y" x , y are, respectively, first , last positions (inclusive) of slice should remove on first move in order win, assuming have winning strategy. if there more 1 such winning slice, function should return 1 smallest value of x. if there more 1 slice smallest value of x, function should return shortest. if not have winning strategy, function should return "no solution".

for example, given following array:

a[0] = 4 a[1] = 5 a[2] = 3 a[3] = 7 a[4] = 2 function should return "1,2". after removing slice positions 1 2 (with sum of 5 + 3 = 8), remaining array [4, 7, 2]. opponent able remove first element (of sum 4) or last element (of sum 2). afterwards can make move leaves array containing [7], opponent not have legal move , lose. 1 of possible games shown on following picture:

https://codility-frontend-prod.s3.amazonaws.com/media/task_img/even_sums_game/media/auto/tikz242689cc8162bed50db48168cf844337.png

note removing slice "2,3" (with sum of 3 + 7 = 10) winning move, slice "1,2" has smaller value of x.

for following array:

a[0] = 2 a[ 1 ] = 5 a[2] = 4 function should return "no solution", since there no strategy guarantees win.

assume that:

n integer within range [1..100,000]; each element of array integer within range [1..1,000,000,000]. complexity:

expected worst-case time complexity o(n); expected worst-case space complexity o(n), beyond input storage (not counting storage required input arguments). elements of input arrays can modified.

first have miss understanding problem statement as, why in given example first player can't take 4 range in first move, function should return 0,0 instead of 1,2.


second thought solving problem count number of ranges in input array, if count player 1 win, , should find first range player 1 can take.

but can't solve in allocated time, , can't take test again.

here attempted code:

    string solution(vector<int> &a) {     int num_even_ranges = 0;     int sum = 0;     (int = 0; < a.size(); i++)     {         sum += (a[i]%2);         if (sum % 2 == 0 || a[i]%2 == 0)         {             num_even_ranges++;             sum = 0;         }     }     if (num_even_ranges % 2 == 0)         return "no solution";     sum = 0;     int start = 0;     (int = start; < a.size(); i++)     {         sum += a[i];         if (sum % 2 == 0 && > start)         {             return to_string(start) + "," + to_string(i);         }          if (i + 1 < a.size())         {             if (a[i] % 2 == 0 && a[i+1] % 2 == 1)             {                 sum = 0;                 start = + 1;             }         }     } }


solution probelm correct if not correct solution intersting problem.

regarding first question, if first player takes 4 (0,0) remaining array is: 5,3,7,2. opponent can take 3,7,2 , first player loose because remaining 5 odd. it's not valid solution.


Comments

Post a Comment

Popular posts from this blog

Django REST Framework perform_create: You cannot call `.save()` after accessing `serializer.data` -

-
i have following viewset: class artistprofileviewset(viewsets.modelviewset): queryset = artistprofile.objects.all() serializer_class = artistprofileserializer def perform_create(self, serializer): if serializer.is_valid(): serializer.save() with following serializers: class simpleartisttrackserializer(serializers.hyperlinkedmodelserializer): class meta: model = artisttrack fields = (...my fields...) class artistprofileserializer(serializers.hyperlinkedmodelserializer): owners = userserializer(many=true, required=false) tracks = simpleartisttrackserializer(many=true, required=false) class meta: model = artistprofile fields = (...my fields...) i getting following error: assertionerror: cannot call `.save()` after accessing `serializer.data`.if need access data before committing database inspect 'serializer.validated_data' instead. i don't see editing serializer.data object. th...
Read more

Why does Go error when trying to marshal this JSON? -

-
i'm trying rather simple example of trying decode json file structs using golang. however, when attempting error that json: cannot unmarshal object go value of type []main.track which don't understand. here's code in question, , json can found here . package main import ( "encoding/json" "fmt" "net/http" "os" ) // tracks group of track types type tracks struct { tracks []track } // track represents singular track type track struct { name string url string artist artist } // artist represents single artist type artist struct { name string mbid string url string } func main() { url := "http://ws.audioscrobbler.com/2.0/?method=geo.gettoptracks&api_key=c1572082105bd40d247836b5c1819623&format=json&country=netherlands" response, err := http.get(url) if err != nil { fmt.printf("%s\n", err) os.exit(1) } de...
Read more