getitright's blog

Interview problem doubt — 2
By getitright, history, 7 years ago, In English

Hi codeforces community,

I have been preparing for interview round for placements. I came across these 2 problems which I have not been able to solve for the past 2 days.

Q1) A and B play a game. They are given an array of positive numbers. Each player in his turn picks up 2 numbers from the array such that the difference of the numbers does not exist in the array. He then places the difference into the array too thus increase the array count by 1. Then the next player repeats the same process. The game continues till there are no 2 numbers such that difference does not exist in the array. The one who’s not able to choose numbers loses. If A starts the game and the game proceeds optimally, find who’ll win the game

Example : Input array : 2,5,3

A: 2,5,3,1

B: 2,5,3,1,4

A has no choice so B wins.

Q2) Given a string containing only lowercase alphabets, you have to convert it into a string such that it contains only vowels by doing minimum number of operations. In one operation, you could select a substring always starting from index 0, and move that substring forward or backward. Example of rolling forward or backward are given :

Rolling Forward

Input- axzf

Let index chosen be 0 to 3 and moving it forward

Output- byag

Rolling Backward

Input – axze

Let index chosen be 0 to 2 and moving it backwards

Output- zwyd

Please help me in solving the above problems. I would be highly thankful to you all.

UPDATE : Doubts are cleared. Thanks everyone for help.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

For the first problem.

Each time you add |A — B| which means the difference is divisible by gcd of A and B. So you can see that the lowest number you add is the gcd of the whole array.

Once you obtain that you can generate max(a[i]) / gcd numbers. Consider gcd is g then you can generate g*1,g*2,g*3..up to max(a[i]).

So it means in the end the problem is transformed into a nim pile of size max(a[i]) / gcd(a1,a2..an) — n.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got the gcd part but , aren't the total answers possible is N(the max number). For eg 7 2. We could generate 5 3 1 4 6 ,so there will be 5 numbers and the winner would be the first player. So if We can find who wins using numbers given and max number.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the second problem start fixing letters from the right-most to the left-most.

Try a dp solution that uses the state dp[pos][how_many_flips][forward_or_backward].

When you are solving for a letter first turn the to its appropriate form then try moving it to forward for all vowels and moving backword for all the vowels.

Time complexity is n * 26 * 2.

Not sure about it tho.

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The first question is incidentally a CodeForces question as well.

Here is some explanation about my approach to it and code from my GitHub.

Note — I used Stein's binary algorithm for GCD in my program. You can use Euclidean as well. No problem.

The main observation is that of an invariant. What is the property that remains the same as we add more elements to the set ? f(x, y) = f(x, x — y) .... The answer is the GCD ! Now, with this property how many elements can we add to this set ? max{S}/gcd.

Now we know how many elements the set initially has and how many it will have in the end. We also know that it increases by one element in each turn. This leads to a simple parity argument to find the answer.

→ Reply