CodeChef September Long Challenge 2019

5 years ago, # |

← Rev. 2 →

can someone please explain their approach for DODGERS and DOOFST?

→ Reply

5 years ago, # ^ |

+17

DOOFST:

Subtask 1: Everyone hates each other, so everyone has to be in different groups at some point. Divide the bit string in half, left half gets all $$$0$$$, right half gets all $$$1$$$, then recursively divide each half again. You get something like

00001111
00110011
01010101

Subtask 2: In short: it should be a complete k-partite graph for some k.

In not-short: If there is no edge between some pair of people, then these people must belong to the same group every time. Let's "invert" the graph, in every pair where there was an edge, now there's no edge, and vice-versa. Find the connected components in the inverted graph, you get this problem.

After we've found the inverted connected components, let's return to our original graph. If there is any edge that connects two nodes in the same inverted connected component, then answer is $$$-1$$$. Otherwise we can consider each inverted CCs as a single node, every inverted CCs hate each other, so now the problem is literally subtask 1 again.

→ Reply

navneet.h

5 years ago, # ^ |

← Rev. 2 →

more related problem than connected components, https://codeforces.net/problemset/problem/190/E after building connected components, we just have to build complete graph. using divide and conquer and maintain address of parent.

→ Reply

5 years ago, # ^ |

Hello!

First of all thanks a lot for such a nice explanation. I implemented the solution but got WA in just 1 test case. If possible then Can you please help?

solution

→ Reply

5 years ago, # ^ |

I think you missed case $$$M = 0$$$. Should be $$$0$$$ operations.

→ Reply

akshat99

5 years ago, # ^ |

Can you please explain me this a little more.

→ Reply

5 years ago, # ^ |

Can you please explain me your question a little more? :)

I don't know which part you are not understanding. It is simply "subtask 2 = subtask 1 + 920E or 190E".

Take a small test for example:

3 1
1 2

We can see here that $$$1$$$ and $$$3$$$ don't hate each other, so every time the hate-inator fires, they have to be in the same group. $$$2$$$ and $$$3$$$ must also be in the same group. Since $$$1$$$, $$$3$$$, and $$$2$$$ must be in the same group every time, it's impossible to get $$$1$$$ and $$$2$$$ to hate each other, so the answer is $$$-1$$$.

With the same reasoning we can invert the graph and solve with the exact same idea as 920E or 120E.

→ Reply

5 years ago, # ^ |

← Rev. 3 →

I couldn't solve DODGERS, but I liked DOOFST a lot. Try to think for a few minutes, before opening each successive hint.

Hint 1

Hint 2

Hint 3

Final

→ Reply

5 years ago, # ^ |

+27

DODGERS: Let's solve subtask 1 first.

For each guest, let's find the closest left and closest right to that guest that they dislike. Now each guest can be represented as an interval $$$[Lguest, Rguest]$$$ in which they'll think the game is fair iff only the guests in that range are invited. We want to know how many guest think the game is fair for each query $$$[L, R]$$$.

Let's think of it another way. Let's think of each query $$$[L, R]$$$ as points $$$(X, Y)$$$ on the 2D plane $$$(X = L$$$ and $$$Y = R)$$$. We have $$$O(N^2)$$$ possible points. For each guest, they will answer YES for a specific set of points. These points form a rectangle. So we have $$$N$$$ YES-rectangles, each corresponds to a guest.

Let's get back to our question: "Given a query $$$[L, R]$$$, how many guest say YES for that query?". We rephrase the question as "Given a point $$$(X, Y)$$$, how many YES-rectangles does this point lie in?".

This is now solvable offline with a line sweep + a range addition/point query data structure in $$$O((N+Q)logN)$$$. Fenwick is very fast.

Subtask 2 is just subtask 1 with persistence.

→ Reply

5 years ago, # ^ |

can you please explain the first part a little more? How you are finding [Lguest, Rguest]?

→ Reply

5 years ago, # ^ |

$$$Lguest$$$ is the closest to the left guest that they dislike, and $$$Rguest$$$ is the closest to the right that they dislike.

For example, if guest $$$1$$$ dislikes guest $$$4$$$ and $$$5$$$, then we only really care that $$$1$$$ dislikes $$$4$$$, since they'll say "NO" to parties $$$[1, 4]$$$ or $$$[1, 5]$$$ or anywhere further anyway.

To find the closest left and closest right guests that they dislike, you just DFS once to find the order of befriendings. Then for every guest, you just go through their adjacency list and find the closest left and right by index that they dislike. Basically follow the statement.

"Go through their adjacency list" for all the guests takes $$$O(sum\ of\ vertices'\ degrees)$$$ in total, which is just $$$O(M)$$$

→ Reply

5 years ago, # ^ |

Sorry to disturb you again but can you please show a little how to add persistence to this to solve the subtask 2?

→ Reply

5 years ago, # ^ |

Have you solved subtask 1?

For subtask 1 we want to query how many rectangles that contain a certain point. We can solve offline, so let's sort the queries by $$$X$$$ first. Then let's do a line scan in increasing $$$X$$$. We have to do the following:

Whenever the scan line encounters the start of a rectangle, update the $$$Y$$$-range in which the rectangle lies in.
Whenever we encounter a query point, just query the corresponding $$$Y$$$.
Whenever the scan line encounters the end of a rectangle, update the $$$Y$$$-range in which the rectangle lies in (again).

Therefore we need to support these operations:

Update some range by $$$+1/-1$$$
What is the current value of an element?

The easiest way to do this is by using a fenwick (but segment tree does work):

When we want to update some range $$$[L, R]$$$ by $$$1$$$, we update $$$arr[L]$$$ with $$$+1$$$ and $$$arr[R+1]$$$ with $$$-1$$$
When we want to find out the value of $$$arr[P]$$$, we simply query the sum of $$$arr[1..P]$$$

No need for lazy propagation and goes very well with persistence.

Now, for subtask 2, since we're solving online, we can't actually sort the queries. But we can still pre-process all the rectangles. Now the operations we need to support becomes:

Update some range by $$$+1/-1$$$
What is the value of an element at some past version of the array?

This is where persistent data structures come into play. It allows for us to query at a specific version of the DS.

A little bit about persistent DS: the main idea is that instead of modifying the value in the DS, we create a new version of it without actually deleting the old version. We exploit the fact that very little $$$(O(logN))$$$ changes are made during each update, so we don't have to build the entire thing anew. There are two common ways of building a persistent DS: path copying (creating new root node, copy the entire new path) and fat node (turn every nodes into a dynamic array, store every value along with their version, and binary search for the most up-to-date version to the version we query) . There are plenty(1) of(2) tutorials(3) online.

→ Reply

5 years ago, # |

← Rev. 6 →

I was stuck at last two questions ( excluding Challenge question ).

For PSUM, I thought about going from some state of $$$a^k + b^k + c^k$$$ to $$$(a+val)^k + (b+val)^k + (c+val)^k$$$, but that requires $$$O(K^2)$$$ time, using binomial expansion and precalculating factorials and inverse factorials. I think it was FFT based question, but I couldn't figure out how to apply FFT here. I thought maybe we can do transition between states in $$$O(KlogK)$$$. What I want to know here is, what's the correct way to think about something when you have some idea that, ok, maybe FFT could be used here? In this case, I didn't know how FFT works before I read this problem. I just knew FFT is something that can multiply polynomials in $$$O(KlogK)$$$ compared to the naive $$$O(K^2)$$$. I tried to read a lot of blogs of FFT, but I guess I was too focussed on bringing $$$O(K^2)$$$ down to $$$O(KlogK)$$$ whereas maybe we had to do something else.

For DODGERS, if we look closely at the three conditions, you see that there is no point in graph structure ( please correct me if I am wrong ). If some guest has number outside $$$[L,R]$$$, then he won't be invited. If among all guests in $$$[L,R]$$$, we just find how many are directly connected ( friends ), then among all those there will always be one person who became friends with Dodger before other. i.e. problem reduces to find number of edges with endpoints in $$$[L,R]$$$. For each edge between $$$u$$$ and $$$v$$$, if $$$u$$$ finds it fair, then $$$v$$$ has to find it unfair. So we can drop the whole graph representation, and don't even need $$$DFS$$$. We just need for query $$$[L,R]$$$, how many intervals ( consider input $$$a$$$,$$$b$$$ as interval ) lie completely inside it. But I tried mergesort tree and fractional cascading too ( Credits: ifsmirnov for blog ). But it was too slow, and was giving WA on some cases. What am I doing/assuming wrongly here?

UPD: Trying to clear its_aks_ulure's doubt, I got what I am doing wrongly! I was counting unfair because maybe people who think it is fair, overlap, i.e. They come before multiple people. But forgot to think same for unfair. For unfair also, there might be overlaps, thus counting edges from one person twice is wrong.

→ Reply

its_aks_ulure

5 years ago, # ^ |

For DODGERS, shouldn't it be how many intervals, lie completely inside it or lie partially intersecting ?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Partially intersecting doesn't matter, because if one end point is outside $$$[L,R]$$$, then that person wasn't invited ( only guests from $$$[L,R]$$$ are invited ).

Did I understand something wrongly in the question?

→ Reply

its_aks_ulure

5 years ago, # ^ |

← Rev. 2 →

I think so it actually matters, for example consider a Query [l, r] like [2, 5] say. The segment [L, R] for person 2 is say [1, 3], then surely person 2 is not happy because he has person 3 in the same set tho the segment [1, 3] is not completely inside query range [2, 5]

→ Reply