tinymon's blog

NOI-'99-Sequence : Help
By tinymon, 6 years ago, In English

Hi, Can someone help me with this problem from NOI.

Thanks for any help.

PS:ko_osaga can you provide hints as u already ACd it.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a system of difference constraints on the prefix sum of the sequence.

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

    Can you elaborate on the solution a bit?

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

    By the way, in this problem, u cant run bellman-Ford. that will give TLE. So...

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

My idea might not be correct, but, still :

Consider l1 > l0. something like dp[n][k][0/1][0/1][0/1][0/1] which denotes, if we are processing the nth element, the range of 1's from n-l0 to n-l1, if there are k 1's in range n ... n-l0 and the [0/1] states basically determines some of the important values of the array, like n-l0, n-l0-1, n-l1, n-l1+1

→ Reply