Comments
0

I think I get it now. Thanks a lot!
0

Ohhh! Makes sense. But lets just say if v is the minimum value that gives us the best possible result, so this means that we can say that there would be a v' > v that can be created by some ai = floor(ai / pi) that gives us the same result. Did I get that right?
0

Hey, can anyone please help me clear doubt in the editorial of Problem D1? It says that we can consider that the minimum can have a range of anything from (0....a[0]). But what if let say a[0] was 4, but constructing 3 was not possible by dividing any of the ai's with any value of p (and we might get the minimum difference when assuming the minimum value to be 3).

For example, Let A = [4, 4, 8, 16] and K = 2

Here we will also consider 3 as the minimum value when iterating from 0 to 4, but constructing 3 as a minimum value is not possible. We can also state that there might be an array for which having 3 as the minimum value is not possible but having 3 gives us the minimum difference

Thanks!
0

Hey, can someone please explain in Problem D why maintaining visited in BFS mentioned 164445974 works whereas maintaining visited like 164445625 fails? Just an example would also help.

In the first case (164445974) as we have the following condition in BFS

if(visited[curr]) continue;

why does it differ from the second way of maintaining visited?

Thanks!
0

Just one more thing, in the first cycle, we can see that the eventh element is j'. So, a path from i to i' must contain even elements. Hence, can we say that we are considering (i, j') as a single node?
0

Hey! Thanks! That makes things clear.
0

Can someone please help me understand this solution to problem E? I know that checking for bipartiteness does the trick, but this solution seems new and interesting (no offense intended)

The thing that I understood (not concretely) are (and please correct me if I'm wrong):

  1. The nodes x and x+n represent the same node
  2. If a node in (1...n) is connected to a node in (1+n....2n) [either directly or indirectly] then the number of edges must be odd
  3. If x is connected to x+n then there is a cycle (starting from x and ending at x, because of point 1)

I don't understand why:

  1. Take 2 * n size of dsu, (obviously, I understand that doing dsu.find_set(x) == dsu.find_set(x) is useless)
  2. Connecting x to y+n (is it to make the number of edges between nodes odd? because If a node in (1...n) is connected to a node in (1+n....2n) then the number of edges must be odd)
  3. Connecting both (x to y+n) and (y to x+n) (is it because to make it undirected),

I am unable to concretely understand the idea behind it. Can someone please help me out here?

0

Oh! I just realized that it's a YES/NO question (Sorry my bad!). I was counting the total number of total subsequences. If it's a YES/NO then we can totally ignore all 0s except one, makes sense. Thanks!
0

Hey, could you explain to me why only consider one 0, what about the case, [-1, 0, 0, 1]? In this can we not have 2 pairs of sums satisfying the condition, [-1, 0, 1] (for the 1st 0) and [-1, 0, 1] for the second 0?