Enigma20's blog

Help needed in Google Online Challenge Problem!
By Enigma20, history, 3 years ago, In English

I recently participated in Google's Online Coding Challenge. Following is one of the 2 questions given to me. I couldn't solve it during the contest. After the contest, I looked up the internet for the same but to no avail. Question goes as follows,

Problem:

You are given a $$$N*M$$$ matrix where each cell has a positive number, $$$A_{ij}$$$, written on it. You need to start from first column and end at last column such that the cost of the path taken is minimum possible. We define cost of the path as difference between maximum and minimum value among all values lying on the chosen path.

In one move you can go to any row of $$$(j+1)^{th}$$$ column from $$$j^{th}$$$ column. You can start from any row of first column and end up on any row of last column. Find the minimum possible cost.

Constraints:

$$$1\leq N,M\leq 500$$$
$$$1\leq A_{ij}\leq 10^9$$$

I was thinking some modification of some standard DP would do but couldn't come up with one.
Any help will be appreciated. Thanks!

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

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

How are you guys giving these rounds? I didn't even know they exist :(

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +45 Vote: I do not like it

Basically the same as this problem (if I remember correctly): https://codeforces.net/problemset/problem/1413/C

For each cell $$$A_{ij}$$$, generate a pair $$$(A_{ij}, j)$$$. Now sort these pairs in ascending order. Let's denote $$$f_i$$$ as the first value of the $$$i$$$th pair, and $$$s_i$$$ as the second value of the $$$i$$$th pair (when sorted).

(edit: why do I need to do this to get a new paragraph :/) The problem is equivalent to finding the segment $$$[l, r]$$$

with minimum $$$f_r - f_l$$$ such that the set of values $$$s_l, s_{l + 1}, ..., s_r$$$ contain every single element from $$$1$$$ to $$$M$$$. This can be solved via 2 pointers in $$$O(NM)$$$.
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot mate! Got it.

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

    Checking if sl,sl+1,...,sr contains every single element from 1 to M, would require another O(M) time which would make the complexity O(N*M^2). Is there any other way to solve this?

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

      It wouldn't. You can maintain the count of each element, and the count of the number of distinct elements, with additions and removals in constant time.

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

Make pairs as {element, column number in which this element exist}, and then sort them.

The problem reduces to sliding window where you have to maintain window with count of each column number >= 1.

Whenever you find such window update ans = min(ans, difference of extreme elements of window).

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

    Now I really regret not thinking it this way:( Anyways thanks a lot!

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

sort pair<element,col> and iterate using two pointers to find best possible segment containing all columns.

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

What was the other question that you got in the round, can you share, please?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It was problem 1 in this blog
    https://codeforces.net/blog/entry/92729

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

      Oh, you got a comparatively tough set.

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

        Yeah, but I must admit I was a little lucky too. I managed to solve the first one using Trie which I later came to know was not optimal. It would have given TLE if tests were strong. But as usual they don't seem very difficult knowing the answer :(

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

          Can you share your trie implementation for that problem? I found it difficult to implement as there are two possible choices if we encounter a 0-bit.

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

            Actually, that's what makes it non-optimal. If current bit is 1, I am simply checking recursively towards 0 bit. In case where current bit is 0, I recursively checked towards both 1 and 0 bit and returned true if anyone of the two recursive calls returned true.

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

I think we can iterate on the minimum element on our path, let our matrix at any time contain only those values which are greater than the fixed element, than we can find the element just greater than the fixed element in each column easily, this leads to O(N*M*log(N*M)) solution.

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

    Sorry, didn't understand completely. Are you implying that we should binary search over the minimum element in our path? What exactly is the 'fixed element' here?

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

      Sort all the elements in each column consider each column as stacks now consider the min element of top of each stack (the fixed element) and the max element on top of each stack, now update the answer using this max — min, then pop this min element. hence we end up with solution of complexity O(N*M*log(M)) where we checked for each min element that is possible to be on our path(which I was telling to iterate on). Hope you get the gist from above implementation.

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

        Oh, thanks I got it now. Nice approach btw!

        → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I was thinking in following manner -
So, since the order does not matter we can sort up individual columns.
Now, if we fix up a value as maximum then if we can get what minimum difference with this we can get, then we can do this. For this, from other columns we should take least of just less or equal elements than fixed value
So, to process this, we can take a max priority_queue and fill up with greatest element(as tuple of element, row, column) of each column, also store the present minimum of all things present in priority_queue.
Now, we can take out the maximum value and take the current minimum, update the answer, take out the maximum and then store the next maximum of that column in priority_queue, update the current minimum if necessary.
Instead of priority_queue, we can also use set to get max and min, but that has somewhat higher complexity.

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

which platform was the test conducted on?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

was this contest for full time or intern hiring?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I think there is very simple solution for this. Sort all the elements of the matrix in an array of size $$$NM$$$ (make sure elements holds the information about its column). Now our answer will be $$$last_{element}-first_{element}$$$ of some least possible size sub-array which contains all the columns from $$$1-M$$$. Now this can be done using sliding window technique. Due to sorting complexity is $$$O(NMlog(NM))$$$

→ Reply