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

Автор eleganc, история, 18 месяцев назад, По-английски

Hi, I faced this question in a recent mock assessment. I cannot think of any approach to solve this. Ideas are welcomed. Problem: A new method has to be derived for decrypting secret codes. THere is a secret array arr of length n, along with a 2D array query with dimension m*2, where each row denotes a pair (L, R) which denotes the sum arr[L] + arr[L+1] + .... + arr[R]. The goal is to determine all the indices of arr whose value can be identified.

Eg. n = 4 query = [[1, 3], [1, 2], [4, 4]]

First query gives the value of arr[1] + arr[2] + arr[3]. The second query gives the value of arr[1]+ arr[2]. Third query gives the value of arr[4] directly.

Using the above only index 3 and 4 can be determined (1 based indexing). So ans = [3, 4].

Constraints: 1 <= n <= 1e5; 1 <= m <= 1e5; 1 <= l <= r <= n

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

»
18 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

https://atcoder.jp/contests/abc238/tasks/abc238_e

Inspire from the above problem, my idea is for each $$$L-R$$$, connect the node $$$L-1$$$ and $$$R$$$. Then for each node $$$i$$$ we check if $$$i-1$$$ or $$$i+1$$$ lies in the same connected component maybe ?

»
18 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

My idea is to use UFDS.
whenever you get a query in the form of l,r , merge r and l-1 if they don't lie in the same CC.
after all query we just have to check if i and i+1 lie in the same component where 0<=i<=n-1, if yes ans+=1.
I am not sure if this works though.