Hello CodeForces Community!

Chef is back again to treat you with his next delicious offering: The November Long Challenge! You are invited to showcase your coding talent and bag exciting cash prizes and goodies.

Joining me on the problem setting panel, we have:

- Problem Authors: chemthan (Trung Nguyen), altruist (Denis Anischenko), ZieiN (Zain Ali), PraveenDhinwa (Praveen Dhinwa), I_love_PHP (Hanlin Ren), Dipjal.Chhetri (Dipjal Chhetri), Abizer (Abizer Lokhandwala)
- Problem Tester: iscsi (Istvan Nagy)
- Editorialist: adamant (Alexander Kulkov)
- Admin: kingofnumbers (Hasan Jaddouh)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.

**Contest Details:**

**Time:** 3rd November 2017 (1500 hrs) to 13th November 2017 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

**Details:** https://www.codechef.com/NOV17

**Registration:** You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

**Prizes:** For Indians: 1st prize: INR 12000/- 2nd prize: INR 8000/- For Rest of the World: 1st prize: $400 2nd prize: $300 Top 10 global and top 20 Indian winners get 300 Laddus each, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck! Hope to see you participating!

I'm stupid

Contest is not over yet !!

Wow it was eneded on main page plz remove this

Actually, TL is really tight for SEGPROD, I also wrote that solution, but did many and many optimizes, also finding modular inverses in O(N + logMOD) will optimize your code nice. Check my code.

How to solve POLY? I wrote convex hull trick for 30 points, but obviously, if function is not linear this will not work.

Contest is still going... (40 min left)

Sorry. I thought it finished 1 hour before, also:

It's over now , so please go on

This is what I did.

Precomputation : For every multiple of 1000, less than 10, 000, and for every multiple of 2500 less than 100, 000, store 10 minimal

Y_{i}.Query : For each query, if

X< 100, brute force. Now check for the highestx_{1}wherex_{1}<Xand lowestx_{2}wherex_{2}>Xfor which you stored 10 minimalY_{i}. Checked only for those 20(or lesser)Y_{i}(x).I know it sounds silly for a 9th problem, but maybe it is tough to make a case in which this fails. Keen to know the intended solution.

Did you get 100 points with that solution?

Yes, he got. I don't know how this got AC...

It is very funny and brave solution, good job, sinus_070. I don't get why his answer was downvoted, he shared with all AC-solution. Yes, it was not very strict, but it is problem of authors and test-creators, not participant.

Too much proness there!

I generalized convex hull trick for higher powers.

Let's call diff(x, A, B) = (a0 — b0) * x^0 + (a1 — b1) * x^1 + (a2 — b2) * x^2 + (a3 — b3) * x^3.

It's obvious, that diff has no more than 3 roots than diff(root, A, B) = 0.

Let's say than roots are R1, R2, R3.

For X < R1 diff(x, A, B) < 0 — A is better.

For R1 < X < R2 diff(x, A, B) > 0 — B is better and so on.

So what we will do: find best function for the leftmost X = MIN_X, let's call it BEST.

For each possible X we will handle list of queries and list of 'interesting' functions.

Function is interesting at XR, if it could became new best function at X = XR.

At the start we for every function F find roots of diff(x, BEST, F) — R1, R2, R3 (Ri >= MIN_X). For R1 we add F as interesting, for R2 — BEST, for R3 — F again.

Now we process all queries offline from MIN_X to MAX_X.

At every Xi we are trying to update our best function with 'interesting' functions for this Xi.

After possible update we find roots for diff(x, NEW_BEST, NOT_BEST) (Ri >= Xi) and similarly to initial actions add interesting functions to the roots.

Roots for line I found with Binary search.

For quadratic function — with formula.

For cubic — I found roots of derivative and did three BS (R < left, left < R < right, right < R)

For excluding problems with non-integer calculations I looked not only roots, but all Xs on the segment [Root — 3, Root + 3] (+-2 was not enough).

I created a comparator function for polinomials, which compares them by

a_{3}, thena_{2}and so on.For first I precompute answer up to 320 (the constant is because 320^2 > 10^5) by brute-force.

After that I sort the queries by ascending. If for some

tquery (t> 320), we find apand aqpolinom, where theppolinom compares less thanqpolinom, andp(t) <q(t) stands, then we can removeqpolinom from the set, because for everyx>t,p(x) <q(x) will hold also. It can be proved indirectly, using the factt> 320.I'm unsure about the number of runs for a given polinomial, but it isn't too much, as I got AC in 0.26.

This is what I did.

https://www.codechef.com/viewsolution/16266475

Sort the given functions by a3,a2, and so on. Remove the useless functions, for e.g functions having the same a3,a2,a1, only one of them will always give optimal output among them, so remove them, that makes sure there are no 2 functions with same a3,a2,a1 coefficients.

Taking linear functions for example, for a given x, realize we don't need to evaluate on all functions to find the minimum value, some of them can never be optimal no matter what. For e.g. functions ax+b and cx+d. If (c-a)*x> 10^5 then lines with coefficients of x >=c will never give better solution than the line ax+b. This way we only check limited lines for all 0<=x<=10^5, and the total number of lines checked will be 10^5 * log(10^5). Similar arguement can be used for higher order polynomials to eliminate the unnecessary functions, and use brute force among the remaining lines for every x.

Works pretty fast, but I know it's far from intended, curious to know the author's solution.

What was the logic behind Chef and Subarray Queries and Product on the Segment?

Problem Links

https://www.codechef.com/NOV17/problems/SEGPROD

https://www.codechef.com/NOV17/problems/CSUBQ/

SEGPROD : Chinese Remainder Theorem CSUBQ : Segment tree

you can find number of subarrays with maximum element less than equal to R and number of subarrays with maximum element less than L than take difference of both to find answer of query. To find subarrays use segment tree; https://www.codechef.com/viewsolution/16147584

Damn!! I had the exact same idea but couldn't implement it...

I read your code. Didn't understand quite a few things.

What are your update functions doing?

And what is the use of each element in struct?

SEGPROD:

Firstly, divide

a_{i}into 2 factor, likea_{i}=b_{i}*c_{i}such thatgcd(b_{i},P) = 1. So, in each query you can calculate answer forb_{i}factors with modular inverse. Factorize eachc_{i}intop_{i}, wherep_{i}are prime factors of P. So,c_{i}= Πp_{i}^{ei}. Now, for each query, answer forc_{i}factors is Πp_{i}^{el + el + 1 + ... + er}which you can handle with prefix sums on exponents ofp_{i}'s. This isO(NlogN+Q* (number-of-primes-product<P) where (number of primes product < P) can be 9 maximally since 2 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 29 > 10^{9}.This solution is intended to TLE, our intended solution is divide and conquer O(n log n) pre-processing then exactly O(1) per query. unfortunately, some people managed to pass with asymptotically slower solutions using non-asymptotic optimizations even though we made TL a bit strict to prevent that.

And I'm in this 'some people' group :P

Waiting for editorial :)

During the competition I had come up with the same solution as the one you have mentioned. The basic idea of the DS: Define M to be the midpoint of the array. 1/2 of all possible queries would be such that its Left endpoint is before M and its right endpoint is after M. So it would be efficient to keep prefix products from M to all other indices(even the ones before M). Any query which has a Left endpoint on the left of M and right endpoint on the right of M can be easily answered in O(1) using this prefix. Now the idea is to recursively do the same thing for the left and right half separately. That's why memory and pre-processing takes Nlogn time/mem.

This DS can subsitute anything a segment tree can do but in O(1) time. However, it takes more memory and doesn't support updates.

My code: https://www.codechef.com/viewsolution/16141888

umm. I actually did really stupid things to optimize. Like rocket io/ changin i%64 to i&63. and x%y to if x>=y:x%=y. I removed functions and wrote functions recursive instead of iterative. Too much effort. Ughh.

@kingofnumbers what is application of this!query to 2*10^7 ? if you use N to 2*10^7 and query to 10^7 it solved with CRT in O(Q*10+N) :) just need precalculate Modeinverse and remain..... this was better you give Q to 10^7 .... it not good! now you think we have Q to 5*10^7 what is different between 4 sec TLE and 4.5 sec ?

even in C++ this way give Overflow and make TLE ... but in some other language do not give TLE ... very mock constraint ...... with your way must you get TLE 3 sec!

That's exaxtly my solution but I didn't manage to squize it under TL (got TLE on only 1 test) ,congratulation anyway !

Or you could use PyPy and write an iterative segment tree.

https://www.codechef.com/viewsolution/16212017

WTF? :D I think admins forgot about TL in PyPy.

Codechef has different time limit for different languages.

Link

You are kidding me.

I spent hours on removing TLE on a solution with a much better approach. Should have thought of it. :'(

I managed to get barely under TL using iterative segment tree and some mod optimizations in C++

CSUBQ:

You can make segment tree with keeping answer, length of left child's answer, length of right child's answer, node index of left child's answer, node index of right child's answer. In merge function, answer for parent node will be left_ans + right_ans + left_len*rigth_len. Update lengths of childs with indexes of nodes you kept.

Solution for Day Schedule?

How to solve Lovers Gift?

This is what I did:

Find the centroid of the tree and root it at the centroid, update the answer for all queries of type 2, with the best two answers that you can get, with the condition that the path must pass through the root, This can be done in O(N+Q). Then, remove the centroid, this will split the tree into parts. At this point, you can also split the queries based on which part contains the node corresponding for that query. If you do this recursively, the process will have O(LogN) levels, and at each level, the time taken to update the answers for the queries will be O(N+Q). Overall complexity is O((N+Q)*LogN)

Look at it this way: adding a bank is detaching a vertex from a tree. A query is asking for second highest number not present in the current connected component. If we process queries backwards, the adding a bank queries simplify to DSU.

Let's have a segment tree, which keeps two top values. If a vertex is a root of some set in DSU, the leaf of segment tree corresponds to the whole set. If a vertex is not a root, the leaf is empty. The segment tree is updated on union operation.

A query "max not in a set" is equivalent to max("max to the left", "max to the right") which can be answered using the segment tree.

My Approach:

Imagine if we are marking a node a bank, we are removing it from the tree. So,we have a forest now. For a node v, the only nodes which we can't reach without passing through a bank are the nodes which are in the same tree as the node v is in. We have to calculate the second largest number <= n which is not in the same tree.

Reverse the queries. Now, we are basically merging tree and maintaining the std::map of number present in the tree and the largest number not present in the tree. For merging, just merge the smaller tree in larger one at each step. When we query for a node, just iterate from the largest number not present in the tree and return the second largest number not present in it and update the largest number not present in the tree. Didn't prove why this should work in given TL but it just did.

Proof by AC, I guess