Opencup: GP of Peterhof

6 years ago, # ^ |

← Rev. 2 →

B: do sqrt decomposition, in each block calculate prefix and suffix sums and also find sum for each group of consecutive blocks, also make a segment tree (it's ~ 3n queries). Then for big queries do a lookup (it's 2 operations) and for small queries use a segment tree. It may be too much still, but if you shuffled everything first, then expected number of small queries is small and this gets AC

→ Reply

6 years ago, # ^ |

С: rotate(and shrink) everything a little bit, so that centers of unusable cells are in integer coordinates. You get some bigger "squares". Suppose you want to go from some cell in the square (x1, y1), to the "same" cell in square (x2, y2). Not proved fact: you need 4min(|x1-x2|, |y1-y2|))+3(max(|x1-x2|, |y1-y2|))-min(|x1-x2|, |y1-y2|))) actions. Now, make a bfs near one or both of starts and then use the formula.

→ Reply

6 years ago, # ^ |

← Rev. 4 →

D: solution if those were programs (I do not know to code this as functional scheme in finite time).

We have log n iterations where we have some graph and exchange log n bits: first program gives an id of vertex v₁ in the clique that has least degree, second program gives an id of vertex v₂ in the clique that has biggest degree. After that each program calculates subgraph that has only vertices that are connected to v₁(and v₁) and that are not connected to v₂ (and v₂). 3 cases possible

deg(v1) > deg(v2). Then there's no answer
deg(v1) <= n/2. Then graph becomes ~2 times smaller
deg(v2) >= n / 2 Then graph becomes ~2 times smaller

Stopping condition should be checked more carefully,

→ Reply

6 years ago, # ^ |

← Rev. 2 →

tunyash, I wonder if you had a simpler solution than this, and how long it took to write one if not.

→ Reply

6 years ago, # ^ |

+28

The problem itself (if you take out the binary circuits) is well-known communication complexity problem (I've hoped that it is only moderately known in the competitive programming community). I wanted to give a problem based on it for a long time and before the championship I thought that I can do it. Unfortunately the way I initially planned failed and there were only two days before the championship so I've decided to do everything in the straightforward way.

I've cursed this idea, the problem and myself many times when I implemented the solution for about 4 hours and then debugged it for another 3 (it is so awfully unpleasant to debug a circuit inside communication protocol).

I've hoped that the participants will come up with something easier to implement than me and that since they code much faster they will make it :) Apparently it was way too tedious.

I am sorry that I've spoiled a nice problem with this gargantuan implementation, but there are a lot nice ideas in communication complexity and probably better ways to wrap it as an ACM problem.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

B: Separate the array into $\text{[math]}$ blocks of length $\text{[math]}$ . Compute the operation on all prefixes and suffixes of the blocks. After that build a new array b of length $\text{[math]}$ where $\text{[math]}$ .

One can build a data structure with $\text{[math]}$ initial operations such that the data structure could compute $\text{[math]}$ in 1 operation for any $\text{[math]}$ . I denote this number as $\text{[math]}$ and respectively $\text{[math]}$ .

Assume for now that we have a data structure like this. How to solve the initial problem? In order to find the answer for the query x₁, ..., x_k you can compute $\text{[math]}$ .

$\text{[math]}$ where $\text{[math]}$ is the smallest number $\text{[math]}$ such that $\text{[math]}$ and r' is the biggest number ≤ r such that $\text{[math]}$ . $\text{[math]}$ and a(r', r) are a suffix and a prefix of a block. Therefore, given the described data structure it is easy to solve the problem.

The needed structure can be constructed as follows: divide the array A in two halves and compute the operation on the suffixes of the first half and on the prefixes of the second one. With that we can compute $\text{[math]}$ if $\text{[math]}$ in one operation. The next step is to recursively construct the structure for the both halves of the array. The depth of recursion is $\text{[math]}$ therefore the complexity is $\text{[math]}$ .

The only part we did not cover is how to deal with the situation when we need to answer a query $\text{[math]}$ and both $\text{[math]}$ and r are in the same block. How can we deal with it? We can randomly shuffle the array. After that one can compute the expected number of queries for the same block and convince themselves that it is o(n).

→ Reply

6 years ago, # ^ |

what if both l and r in the same block?

→ Reply

6 years ago, # ^ |

I've written a short paragraph about it in the end. The key idea is that in this problem you can shuffle the array arbitrary and the expected number of queries inside blocks is very low (I think it is line O(1)). That is the reason $\text{[math]}$ .

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Yep, we actually did that too in our solution, just wanted to check if there was another idea for that.

→ Reply

300iq

6 years ago, # ^ |

I've just splitted everything into blocks by 8 elements (for 2000), and then you can just build the segment tree inside each block

→ Reply

PavelKunyavskiy

6 years ago, # ^ |

Or array of size 5, and count all subsegments of it.

→ Reply

6 years ago, # ^ |

I guess I was the one stupid enough not to consider random shuffling, here is my ugly solution which works without random:

Do a sqrt-decomposition, for each block calculate prefix- and suffix- sums, for each segment of blocks also compute a sum. Total number of queries to do it is $\text{[math]}$ . If segment is not inside one block, we will answer it in 2 queries. For each block build the same sqrt-decomposition. We already spent 5n operations which is not great. But we can divide initial sequence into $\text{[math]}$ pairs (using $\text{[math]}$ queries), and then build sqrt-decompositions on array of size $\text{[math]}$ using only $\text{[math]}$ queries, so we have n more queries to spend on the data structure.

If segment is not inside smallest block, we will spend only 2 queries to answer it. One can calculate, that smallest blocks will be of size not more than 6, therefore segments strictly inside them will be of size not more than 4. We could answer them in 3 queries, but that's too much, so we will spend our n queries to calculate operations between neighbors. Now we can answer each segment in 2 queries.

It looks like because I divided initial sequence into pairs, I will have to do 2 more queries per segment. But that's not true: borders of my segments are x and x + 1 where x is deleted position, one of these borders is even. So, I will have to do 1 more query per segment (amortized). And 1 more query to unite the answers.

→ Reply

rng_58

6 years ago, # ^ |

Is anyone interested in even more weird solution?

For simplicity let's assume that n is divisible by 35. Let's precompute the answer for each interval [l, r) such that:

Both l and r are multiples of 35.
Both l and r are multiples of 7, at least one of them is a multiple of 35, and r - l ≤ 35.
At least one of l and r is divisible by 7 and r - l ≤ 7.

We need (11 / 7)n + (1 / 5)n + (n / 35)² / 2 ≤ 4n opertaions to get these values. Then, since any interval can be written as a disjoint union of at most 5 of these intervals, we need only 4 operations per query.

→ Reply

6 years ago, # ^ |

That is kinda cool :)

But don't you have to combine answers from segments afterwards, which means that you have to do in no more than 3 operations per segment?

→ Reply

rng_58

6 years ago, # ^ |

Hmm, yes, I completely forgot about that. I guess I was just lucky.

→ Reply

nocriz

5 years ago, # ^ |

I participated in the round and used an idea almostly the same with yours, but mine solution uses one less operation per segment.

Do a sqrt-decomposition, but make sure that every block has a length divisible by $$$4$$$. Then divide the blocks into even smaller blocks of length $$$4$$$. For every small block of length $$$4$$$ calculate all subsegment sums, using $$$6$$$ operations. Then use $$$2$$$ more operations to calculate the sum without the second or third element. Since for every two adjacent segments we query there is one missing element, we could use the pre-calculated value for both the segments. If there are more than one missing element in one block of size $$$4$$$, we can use brute-force to calculate the sum in that block. This method uses less than $$$4$$$ operations per segment, no matter how big k is and also doesn't rely on random.

→ Reply

cdkrot

6 years ago, # |

+18

D's idea is cute, but looks close to impossible to code in limited time.

I would be nice if you could write a program, not a boolean scheme.

→ Reply

6 years ago, # ^ |

+10

it would be rather easy problem, though

→ Reply

6 years ago, # ^ |

+18

Moreover, it would be well-known problem. "Included in textbooks on communicational complexity"-level of well-known.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Well, I think it is not really well-known in this community so it'd be nice to spread such ideas this way. I would better give the problem without making it implementation disaster.

→ Reply