lusho's blog

WA????
By lusho, history, 7 years ago, In English

Why this code is giving me WA in 811C - Владик и запоминающаяся поездка, i used DP the tipical take or not take:

here is my code: 27467986

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Consider lines 57-58:

if(Ini[V[i]]==i)
  Sum[i]=SubArray(Ini[V[i]],Fin[V[i]]);

You then use this Sum array in lines 40-41:

if(Ini[V[k]]==k)
  first=Sum[k]+Solve(Fin[V[k]]+1);

The problem is that in the Sum array you're considering the xor-sum of a subarray from the first occurrence of a number to its last. However, within this subarray, there may occur other numbers, whose first occurrence is before the beginning or whose last occurrence is after the end. This would make taking such a subarray into the solution illegal. You're not considering this, which is why your answer comes out to be greater than the judge's solution.

→ Reply