Editorial for ZCO Prep

KFIB

Prerequisites : Prefix Sums.

A naive brute force of this algorithm would be O(N*K) because calculating each term will take K calculations. To calculate the ith we will have to add a[i-k], a[i-k+1] …a[i-2], a[i-1] terms. So if we use a prefix sum, then we can do this computation in O(1). a[i-k] + a[i-k+1] …a[i-2] + a[i-1] = prefix[i-1] - prefix[i-k-1].

    a[0] = 0;
	for(i from 1 to k)
		pref[i] = 1 + pref[i-1];
	for(i from k+1 to n){
		pref[i] = (pref[i-1] + (pref[i-1] - pref[i-k-1]))%mod;
	}
    print (pref[i] - pref[i-1])%mod

This reduces the complexity to O(n) and is fast enough to get full points!

BRKTREE

Prerequisites: DFS, Tree

When we remove an edge, the tree breaks into two parts with sum W1 and W2. Also W_1 + W_2 = W(the original tree).
If we know the sum of all nodes in one tree, then we can also find the other one in O(1)

W_2 = W - W_1

Whenever, we remove an edge, one of the complete subtree gets removes. So if we know the sum of all subtrees(which we can calculate using a DFS in O(n)), then we can easily find the answer in O(N) by iterating through all the subtrees and checking if the answer matches for each query.
Since, all queries are independent we can calculate all the possible difference and store it in a set. Then whenever we get a query we can just check whether the value exists in the set.

We are very sorry for the fault in the second subtask

LNGHW

Each element has a specific remainder when divided by M. Lets make an 2d array, vector b[M].
Then we can push all the elements to their specific array depending on their remainder. After that sort all the arrays depending on its a[i] value. Then we can easily answer the queries.

for(i from 0 to n-1){
     int inp; read inp
     b[inp%M].push_back(make_pair(inp, i));
}
for(i from 0 to M-1){
     sort(b[i].begin(), b[i].end());
}
for(q--){
     int i, R; read i and R
     if(i <= b[R].size()) print( b[R][i-1].second + 1)
     else print (-1)
}

PIZPAR

The problem can be solved using a greedy approach. By induction we can prove that for a single pizza, if we make n cuts in it, the maximum number of slices we get is (n*n + n + 2)/2.
Now with this formula we can prove that it’s always optimal to make the maximum possible number of cuts on a single pizza, rather than dividing the total cuts among the pizzas.
Let’s suppose we have a total of x+y cuts. Now, if we divide the cuts (ie. make cuts in two separate pizzas) the total slices we get is (x*x + x + 2)/2 + (y*y + y + 2)/2. Where as if we make the x+y cuts on a single pizza, we get (x*x + y*y + x + y + 2*x*y)/2 slices.
We can clearly notice that the latter provides more slices. This means that it is always more optimal to make as many cuts as possible in one of the pizzas. This gives us our greedy solution.

4 Likes

BRKTREE had weak test cases I think. In my submission 16203598 I used set<int> by mistake instead of set<long long> but I still got AC.

1 Like

@vijju123 @adhyyan1252 can you please tell me how this is calculated " the maximum number of slices we get is (n*n + n + 2)/2 ".

For problem Pizza Party,

Shouldn’t the problem statement specify that the cuts could be made in any direction, not necessarily passing from center of pizza, as common in typical pizza cutting (atleast as many as i ate were cut along diameter)?

I wasted whole my time, not understanding how number of slices was 31, though i got the idea to greedily make cuts.

Anyways, Nice problem set.

PS:I would like to know what was wrong in second sub-task of BRKTREE, if u don’t mind. (I too got 80 points)

1 Like

Yes, the test cases were weak. This was a learning experience for us; first time we had ever made a problem.

Lets solve this using an induction based proof.
T(0) = 1,
T(1) = 2,
T(2) = 4,
T(i) = i + T(i-1) because whenever we make a new cut, we can intersect ‘i-1’ other lines and create ‘i’ more slices.
Now we can use arithmetic progression to get the formula because T(i) = i + i-1 + i-2 … 1 + 1 = (nx(n+1))/2 + 1 = (nxn + n + 2)/2

1 Like

Sorry for the vague problem statement. It looks like there was a small bug in the test cases of the second subtask. We are also very sorry for that

Happens :stuck_out_tongue:

@devu_1234 it’s called the circle/pancake cutting problem. You can find it if you search online, such as here.
The numbers of the series are formally known as central polygonal numbers.

No problem at all, mate…

@adhyyan1252 @meooow thanks guys ,now i am clear with the concept .Nice problem , learnt something new :slight_smile: