Easy Coding Contest-10 Editorial

All contest related discussion goes here. Both Dev Skill and Non Dev Skill contest related discussion is allowed. (But please keep the forum clean)

Easy Coding Contest-10 Editorial

by BishalG » Mon Apr 17, 2017 10:27 am

Problem A: Happy New Year
Link: http://devskill.com/CodingProblems/ViewProblem/308
Problem Setter: Bishal Gautam

In this problem, you are given a line of New Year Wish text in Bengali and Nepali Language, you have to convert wish of one language to another one.
You can see that, you can easily distinguish two wishes by comparing first string "Shuvo" or "Shuva" then after distinguishing, year conversion can be done easily by adding or subtracting 650 years as mentioned in the problem statement.


Problem B: Interest Research On Training Courses
Link: http://devskill.com/CodingProblems/ViewProblem/309
Problem Setter: Bishal Gautam

In this problem, you have to find the summation of all integer values mentioned in the problem description part of problem.
You can get this as: 7000+8+10+1+2+3+4+5+6+7+1+5+7= 7059.
You just need to print 7059 in a single line of output. :D


Problem C: Replace HIS name
Link: http://devskill.com/CodingProblems/ViewProblem/312
Problem Setter: Jaber Kibria

In this problem, you are given a line of input. You have to replace each word of format: [ not alphabet ]Sharif[ not alphabet ]
into Officer. A careful implementation by checking above mentioned word format is enough to get AC for this problem.


Problem D: Walk Left and Right
Link: http://devskill.com/CodingProblems/ViewProblem/310
Problem Setter: Bishal Gautam

You are given an array of height and your array position X and walking distance K to both upwards and downwards from position X, you have to output how may array element has height strictly greater than your height. For this problem, You just need to be careful that K's value can be as large as 10^12 . So, you have to iterate array once and check whether that array position is within distance K from position X and its value is strictly larger than value at position X.


Problem E: Saanvi and Card Game
Link: http://devskill.com/CodingProblems/ViewProblem/305
Problem Setter: Bishal Gautam

In this problem, you are given cards numbered from 1 to N ( upto 13) , you can shuffle cards as many times as you want so that the summation of absolute differences of consecutive card's value after shuffle will be maximum.

Note: Greedy approach of taking leftmost value then rightmost and leftmost and so on after sorting will not work here.Consider case: 4 cards with values : 1 4 5 6, answer will be 11. :roll:

Bruteforce Solution:
You can generate all possible permutation of values then calculate summation and update maximum value accordingly. The permutation generation will take O(N!) complexity. So, as N can be as much as 13. trying 13! will certainly results TLE. :cry:

Actual Solution:
We can solve this problem using Bit-mask Dynamic programming.
Bitmask is a term used for Binary number which is very useful for representing state of subset of indices taken while performing dp operation.
Lets see how binary number represent subset of indices taken:
Lets consider our Cards array is: {1,4,5,6}.
if we want to memorized that we have already taken two values before which are 1st index and 3rd index.Then, we can easily get it if we see bitmask of format: 0101, where bit at position 1st and 3rd are Set ( means are bit value is 1 ).
So, if we can memorize state from 0 to 2^N-1 , then we can get information of which indices are taken previously.
Now, we can solve actual solution using dp with state ( mask, prv_ind ).
where, mask: represent the state of indices taken already.
prv_ind: represent the previous index which is useful for calculating consecutive value's absolute difference.
If we know these two values, we can easily decide any indices that we can take currently by iterating over mask and finding Off Bit position ( bit with value 0 ) then we can calculate consecutive value's absolute difference using prv_ind and give call to next state by changing mask to new mask with addition of Set on current position and setting prv_ind to current position of bit and finally maximizing over all possible calls.
So, overall complexity of solution will be: O( N*2^N ).
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Easy Coding Contest-10 Editorial

by RezwanArefin01 » Thu Apr 27, 2017 9:24 am

Problem E: Saanvi and Card Game
Any counter example where greedy doesn't work?
I mean first sorting the array and then
ans[0] = arr[0]
ans[1] = arr[n-1]
ans[2] = arr[1]
ans[3] = arr[n-2]
.....
 
Posts: 1
Joined: Thu Apr 27, 2017 9:20 am

Re: Easy Coding Contest-10 Editorial

by BishalG » Thu May 04, 2017 9:22 am

@RezwanArefin01; Thanks for curiosity.
For 1 4 5 6, answer will be 11.
But, if we do accordingly your greedy approach.
we will get less-8.
after changing: 1 6 4 5
so ,here sum= (6-1)+(6-4)+(5-4) =5+2+1 = 8.
Whereas, you will get 11, if arranged by=> 5 1 6 4
= (5-1)+(6-1)+(6-4) =4+5+2=11
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm


Who is online
Users browsing this forum: No registered users and 2 guests
cron