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

Автор prithwiraj15, 5 лет назад, По-английски

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.

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

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

Constraints?

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

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?

»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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)