Блог пользователя codolove

Finding sub-array with maximum xor
Автор codolove, 10 лет назад, По-английски

I am trying to solve this question from many days but getting wrong answe always. I am using a trie to solve this. My code is here.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think you are trying to solve the same problem that are solving here. Check it out, maybe you find the answer there. I couldn't see your code due to technical problems but I solve similar problems using tries too, so I think you are probably on the right way.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am again getting wrong answer on same type of problem here. I have checked on most of the inputs and it's giving correct answer. My solution is here. please do check this.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi, you are considering only the first maximum value that appears, but you can get the same maximum value, with a lexicographic smallest subsequence. Try with this input:

      4
1 1 2 1

      Your output:

      3
2 3

      Correct output:

      3
1 4
      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'll give you a hint, write the maximum number in binary, it's going to have at most 20 digits, now it's obvious that you can have only one of each digit in the answer, and having a digit i is better than having digits 1 . . . i-1 since 2^i > 1 + 2 + . . . + 2^(i-1), so now each time try saving the digit with the most value and your done!

→ Ответить