math-is-stupid's blog

Need help in SPOJ problems.
By math-is-stupid, history, 8 years ago, In English

Problem 1: http://www.spoj.com/problems/TOINCSEQ/ Problem 2: http://www.spoj.com/problems/TOPALIN/ Even for the partial scores, I am not able to come up with any solution. If someone can explain solution to the above problems; even if it is for the partial scores, that would be really helpful.
p.s Problems are not related. I just have doubt in both of them.

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

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

TOINCSEQ : Consider some point a[i-1] > a[i]. it means that a[i-1] should be decreased to a[i]. (we can increase a[i] to a[i-1], but decreasing is always better when we consider elements beyond i+1~) note that only resolving those "adjacent" cases will make the whole sequence into increasing sequence.

Now we have several pairs which state that we should decrease S -> T (when S > T). This means we should decrease S to S-1, S-1 to S-2 ... T+1 to T. Observe that the total operations we need to do, is the union of all interval [T, S]. It can be calculated in NlgN.

Code : http://codepad.org/gmTlJShB

TOPALIN : Consider some point s[i] != s[|s| — i — 1], it means that we should do some operation to make s[i] to s[|s| — i — 1]. build an undirected graph for those kind of dependencies. for each component, we pick a character with maximum occurences, and change all other vertex (= character) with that character. we can calculate the cost of these operation with dfs.

Code : http://codepad.org/pEELBbfL

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

    Thank you for the great explanation. Regarding TOINCSEQ, I think I got it but I am still not sure :p. I am not able to get my head around two claims i.e 1) Decreasing is always better and 2) Resolving those adjacent cases will do the job for us. If possible, can you elaborate? (may be in terms of intuition or something mathematical)

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

      1) My previous comment was bit wrong. Decreasing don't matter, we can increase it if you want, the key is we should somehow resolve those a[i-1] > a[i] case. (and decreasing will be a clear choice)

      2) if we resolve all those adjacent cases, a[i-1] <= a[i] will always hold for every i (above decreasing operation never make some pair with a[i-1] <= a[i] to a[i-1] > a[i]) so the sequence is nondecreasing.

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

        Thank you again. I get it that if we are able to resolve cases for each index then the resulting sequence would be non-decreasing. But my doubt is, let's say there is some index 'i' where there is a conflict i.e (a[i-1] > a[i]) and as proposed we will decrease a[i-1] till it becomes equal to a[i]. But now assume that there is some other index 'j' (j > i) which has same value as a[i-1] (a[i-1] = a[j]) So whatever changes you do at a[i-1] will also affect a[j]. So my question is how this handled using above solution (as in how the effect of whatever changes we do is propagated throughout the whole sequence and eventually making it non-decreasing).

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

          It's true that changing a[i] affects some other elements, but it doesn't make some pair with a[i-1] <= a[i] to a[i-1] > a[i]. So we don't have to care about it.

          I think it's hard to explain. Try to calculate union of interval by hand, and simulate the decreasing operation to see. (if we have [1, 3] / [7, 11] / [15, 22] then we simulate from the back. 22 -> 21, 21 -> 20 .... 16 -> 15, 11 -> 10 ...)

          → Reply