prithwiraj15's blog

By prithwiraj15, 13 days ago, In English

Ode 2 Code 2021 Round-3

Round 3 of Ode 2 Code gave only one question with a total time of 45 mins to solve it. I was not able to solve this problem. Can anyone help me ? PS :- The competition is already over, hence it the question can be disclosed now

Question Statement

You are given

  • An array A of N integers.

  • And M queries consist of three integers k, y and x.

Beauty of a array A[1], A[2], A[3], A[4],...., A[N] is defined as A[1] + A[2] + A[3] + A[4] + .... + A[N].

For each query, k, y, x, you are given the following conditions :-

  • Let U be the bitwise AND of the beauties of any y subarrays among all subarrays of size k.

  • And, Z = U | x, where | is the bitwise OR operation.

Calculate the maximum possible value of Z for all queries.

Constraints

  • 1 <= N <= 1000

  • 1 <= M <= 1000

  • 1 <= Ai <= 10^9

  • 1 <= ki <= N

  • 1 <= yi <= N-ki+1

  • 1 <= xi <= 10^9

Sample Test Cases

1) Sample Case 1

N = 5

M = 2

A = [1, 2, 3, 4, 5]

Q = [[2, 3, 9], [3, 2, 17]]

Approach

For the first query

  • We have 4 subarrays [1, 2], [2, 3], [3, 4], [4, 5] with beauties 3, 5, 7, 9 respectively.

  • You can select bitwise AND of 3 beauties, i.e 3 & 5 & 7 = 1, so U = 1.

  • Z = (1 | 9) = 9. This is the maximum possible.

For the second query

  • We have 4 subarrays [1, 2, 3], [2, 3, 4], [3, 4, 5] with beauties 6, 9, 12 respectively.

  • You can select bitwise AND of 2 beauties, i.e 9 & 12 = 8, so U = 8.

  • Z = (8 | 17) = 25. This is the maximum possible.

2) Sample Case 2

N = 5

M = 2

A = [5, 4, 2, 4, 9]

Q = [[2, 2, 7], [2, 3, 6]]

Approach

For the first query

  • We have 4 subarrays [5, 4], [4, 2], [2, 4], [4, 9] with beauties 9, 6, 6, 13 respectively.

  • You can select bitwise AND of 2 beauties, i.e 9 & 13 = 9, so U = 9.

  • Z = (9 | 7) = 15. This is the maximum possible.

For the second query

  • We have 4 subarrays [5, 4], [4, 2], [2, 4], [4, 9] with beauties 9, 6, 6, 13 respectively.

  • You can select bitwise AND of 3 beauties, i.e 6 & 6 & 13 = 4, so U = 4.

  • Z = (4 | 6) = 6. This is the maximum possible.

Please look into this problem.

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prithwiraj15 (previous revision, new revision, compare).

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prithwiraj15 (previous revision, new revision, compare).

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Updated the post with constraints now

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      This can be done in MNlog(max(A)) , just complement x, let x1 be the complement of x. First find out all sum with subarray size k. Start from the highest set bit of x1, find if there exist at least y elements with the set bit as highest set bit, if yes add that to answer and otherwise move to next bit, and check the same. Finally add all the set bits of x to the answer as well.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh my god.. I thought it was extremely difficult Thanks anyway for your help. Much appreciated.

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here are you saying that maximizing U | x is same as maximizing U & !x

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it
here is my code
»
12 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

On a side note, Is there anyone who passed all testcases in round 2 but was not selected for round 3? If it was based on speed , then any idea what the cutoff time was?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yeah i was able to pass all the test cases of my given problem in round 2, but didn't get selected for Round 3!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yeah me.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think about 30 mins, cuz i completed mine with about 16-17 mins left.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see, thanks for the response!!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submitted my test before 25 min And I was selected for next round.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I had submitted under 15 mins but not selected.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yeah , same.

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I was able to complete my test in 6 mins, but was not selected :(

      P.S. I didn't even get a rejection mail

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yeah, I passed all test cases in Round 2 in 15mins but didn't get selected for Round 3. My friend passed just 7 test cases but got selected. It wasn't based on speed then, it might be random or based on code implementation.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    No idea lol, I was done in like 7-8 mins. They probably thought I cheated

»
12 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In my case,It took 35 min to understand problem. Problem statement was too bad. when I understood question ,the time remain was less so I got panic and I quit the test.but after few hour,I started doing code and I solved the question in 8 min.[problem]

(https://xp.io/storage/YogVxoL.png)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had this same problem . Understanding the problem statement was tougher than solution..xD . It took me like 15-16 minutes to understand it and 10 minutes to solve .

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Did everyone else get this problem? I got a different problem statement which was a little harder

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone knows when and where will the result be declared ?

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When round 3 result will anounce?