I too shared your dream and went to the same contest as well, my team got 6th place in that regional but it wasn't enough to get to WF (or even playoffs) as well. (in fact we did not even get a medal because of the rules)

The 2 problems are very different though. There are plenty of problems with sum of max element of all subsets, just tat the condition for the subsets are different

is the intended time complexity for E something like O(NlogN (N/B) + QB), B = 1000 or something? What I did was partition the queries by k, and do sqrt decomp for each k-bucket (after doing some processing like hashing suffixes, removing short elements etc)

I made a claim that mi is increasing. Then the number of transitions become mnlogm

Write the math and you realise the answer is sum(Si/mi) * 2 — n. Si is the sum of m0.. mi Then a simple DP follows

What is the intended solution for B? I did something fishy and got AC but with 1980 ms (so high chance I fail systest) I ran normal BFS and realise around 2000 states in total which should be fast enough, if not because of a map, so I did some preprocessing to reduce a b c d and m into 8 bit numbers (since bit combinations of at a particular position of (a,b,m) will give the same result of (c,d) after some operations), then I use a global array to store distances to pass.

Also if not because of the editorial of this: https://codeforces.com/contest/1866/problem/M I wont have solved D

As expected, I failed systest... (rip IGM dreams)

Actually, I think quite easy to kill random approaches for F, one can just construct a tree with all possible subtrees of size k except for 1 which random will find it hard to find.

Is this upcoming round the same as the UCup Season 1 Stage 9? Both seem to be 2018 Qingdao Regionals

I think G implementation was quite painful (finding the shifts, then finding the ordering constraints, then doing a topsort), and there's special cases like all row/col shifts only (which I failed to recognise in contest)

For E actually there is a kinda simple solution that just uses sets which I ACed after contest. You just need to maintain a records array and a pointer.

The idea is that everything to the right of ur pointer may not be valid currently, while everything before is accurate. Then, in your records you can store (is this x 'useful' (contribute to distinct count), x, how many 'useful'). Then, to handle -k, you just jump the ptr to k before, to handle ?, just find how many 'useful' ptr is at, and to handle + x, its abit tricky, but you just need to keep track of the indices of useful x, and make sure there is one useful x before the ptr, so u can use another set to do it. Then you override the current record to the new record, (but make sure to store the change to handle rollback). Then rollback can be done with a stack.

The key is to notice that suppose you delete and then add stuff, you must rollback the added stuff before rollbacking the delete so by doing that and restoring the records after rollbacking add, you are sure that your records are correct before rollbacking the delete.

Submission: https://codeforces.com/contest/1858/submission/219002981

You can think of another way. What if you already have the maximum absolute number? Then you don't need to do doubling. If all is positive/negative, you only need 19 operations, so you can use your biggest to fix at most 12 elements before doing that. (so you can have 12 positive/negative where the biggest is not at) Suppose then, there is 7 and 13. Then you use your approach of doubling (which is 5 operations) then 5 + 7 + 19 = 31

did you do the coinchange subproblem greedily? (i cant see of a fast way to do that part fast, so I just do greedy)

How to do 1E? I tried putting some number of 1s, and then filling the rest with >30 by taking nCr greedily, (I try with all possible numbers of 1) but based on my runs, I can only do <70 for most at best.

I tried using a bit trie to do the binary search. Suppose you want >= m, then you can build the graph implicitly by doing the following bfs. You take a current node u, and then use your bittrie to take all values arr[x] such that arr[u]&arr[x] < m, then remove those x you used and add them to your queue. In this way you will prevent n^2 edges and get an implicit forest. Now that you have 2 different partitions, and check your check both of them to make sure their minxor >= m. At first, I tried using a bitTrie to do the checking as well but that TLEs, turns out the approach of sorting and checking adjacent elements as pointed out above will make it fast enough to pass. Also, I had to do alot of constant optimisation to make it work (recursive calls are too slow and pointer based bit trie is also too slow)

Submission: https://codeforces.com/contest/1849/submission/215997707

For E, I had a O(n^3 + Q) solution, with dp of the form:

dp[L][R] = min( max(combine(dp[L][k], dp[k+1][R]), {1, #queries intersecting [L,R]*2})) over all k inside [L,R].

Can this be optimised by knuth as shown in here: https://cp-algorithms.com/dynamic_programming/knuth-optimization.html#generic-implementation ?

It seem to give WA for some reason. Is the cost function and combine function (instead of simple plus) valid to be used here? (Brute n^3 solution seem to work and give TLE instead so the dp should be correct)

I did something different, although I didnt manage to debug and AC within contest.

Basically, my dp state was dp[n][cc][m] = how many different graphs of n vertices have cc connected components and m edges from small to big. Once u have that its just simple math.

The transition then is take k vertices to form the 1st CC in the DAG, suppose it has m1 s->b edges, and suppose the 1st CC to the rest of the CC have m2 s->b edges and the remaining CC-1 components have the rest (m — m1 — m2 edges). If you get the 3 parts, you can just multiply all 3 and add to dp[n][cc][m]. So ull add something like (ways to pick k vertices with m2 as described above)*dp[k][1][m1]*dp[n-k][cc-1][m- m1 — m2]

Also u cant compute dp[n][1][m] directly, but you can get it via C(n*(n-1)/2, m) — dp[n][2][m] — dp[n][3][m] — etc. (Or maybe there is a combinatorial argument that eludes me)

For the ways to choose the k vertices, basically its the number of multisets such that k numbers from 0 to (n-k) such that it add up to m2. (You can write a dp for that, I dont know of a formula, bars and stars is ordered which is not what we want)

Depending on how u do it, it can take very long (like O(n^10)), but what I realised after the contest was that by reordering the loops, u can do convolution on the results of the 3 parts to get the result fast, instead of having 3 for loops (which is O(n^6)) and reduce to just O(n^4) or O(n^2logn) with NTT. Link: https://atcoder.jp/contests/arc163/submissions/43206412

How to do E? I have a O(n^2 k) DP which TLEs. Is this the intended solution, or is there anything faster?

I discovered another way which is possibly easier (only ACed 7mins after end)

Consider 4 cases of sum(x) and sum(y). Assume sum(x) and sum(y) is positive, then you take all (+x,+y) and discard all (-x,-y). Then you take all (+x,-y) into your sum(x) and sum(y). Next, take the remaining (-x, +y) you didnt take as well as -(+x, -y) which you took (to undo taking them) and sort them increasing (abs(x)/abs(y)) ratio. Then you keep adding the (-x,+y) in sorted order to your sum(x) and sum(y) and take max everytime you do so. Repeat for all 4 cases. (Easiest way is just multiply all the x and y by 1/-1).

The idea is like the 2 extreme points form like an arc, then the intermediate points form a convex hull of some sort. I cant prove but it feels like it works intuitively.

Submission: https://codeforces.com/contest/1841/submission/209475017

Actually how would one create a BIT to do those in O(N log N) time?

For F, I manage to solve it except for this one part:

How to find the number of m-tuples that add up to n such that at least j numbers is greater than k? Find this for all j from 0 to m.

With this, you can change the question to how many different ways to place the empty space, then depending on the number of regions of empty space > k, you multiply some power of 2. (Fix the tree to always fall left if possible).

div 1D was very evil, no sum(m) = 1e5 * 1e5 in pretests

It seems that the timing URL is broken if you are logged out. It should work if you log back in. The contest should be 10 April 2023, 9.35am UTC.

Any idea on how to solve F?

I am not sure if this is the solution for F (didn't implement on time) but it rests on this key claim which I cant really prove or disprove: If I have a class of size k and I have at least 2*k-1 bags, I can always find a knapsack of size k divisible by k.

Suppose this is true, then its always possible and I can just take knapsack from small to big. Can anyone prove or disprove the claim?

How do you remove the log factor? I used a fenwick tree to keep track of the checkpoints to allow querying the most number gold coin saved fast given a certain amount of silver coins.

How long does registeration usually take? I just sent an email a few hours ago and hoping to get registered by tomorrow's contest

How did so many people falsely solve C? I stared at it for like 20mins and had no idea, but seeing that many people solving it so fast, I started to doubt myself. I tried some stupid greedy ideas but all failed on paper.

Any idea how to solve E? I can reduce the problem to maximal weighted vertex cover with V = 40 and I think the question itself is NP-hard since you can reduce maximal weighted vertex cover to the question itself. Brute force seems to take 2^40.

Can count the number of occurrence for each string over all tries and then add nC3- (n-count)C3 for each string (since each string will only occur once per trie)

Can use it for third trie too (I did and AC)

Since I would have lost a lot of rating (due to FST), I strongly agree with this decision! :)

Btw, I FST for D, but when I try to resubmit the exact same code, it passes (barely). Is it possible to reverse the FST?

how to reach IGM like you good sir?

I spent an hour trying to optimise 1C, then I realised you dont need to try all k = factors, just k = n/prime factor! Also, how do you prove that greedy works for 1B?

thanks. I found my bug.

I am not sure if I made a bug for E but I would to confirm the correctness of my idea. A puzzle is solvable iff all cells except 1 have at least one neighbour smaller than it. Thus, we can find a 'bad' cell and attempt to try swapping its neighbours with every other cell (including itself) and check each scenario in O(1).

Reverse the graph and then do something very similar to dijstrak starting from n-1. Notice that at some node, you have a bunch of nodes you can go to and if you know their distances, you can kill some in descending order(so like their effective distance is +0 +1, +2 +3....) and find the optimum of that. Thus, what you can do is to store the current estimates incoming (after reversing) for each node and pick the best (similar to dijstrak) after adding some weights. Then, we process the nodes by current estimate similar to dijstrak. But this may potentially force you to reupdate the whole set everytime you process a node. But, you realise that you only add numbers greater than numbers you add before (since you process nodes in ascending estimates). So, you can just store the best estimate.

Essentially its just do dijstrak with the following modification: dist[v] = min(dist[v], dist[u] + indeg[v]) indeg[v]--

Connect a line between 2 points if you can possibly colour them as the same colour. Notice that this will result in a graph of disconnected cliques. The clique can either be colored with 1 colour or different colours for each point. Then, we can use DP to colour them.

Oh wow, I didn't think of it that way.

E was a nice question with 2 parts to it. How to solve F though?

Of course, you still need to handle cases where just picking 1 reverse suffice, but at least you know that you can always solve in at most 2 reverses.

Find the peak of the prefix vals, then 2 operations: 0, peak and peak, n is enough. When you choose 2 endpoints with different values to rotate upon, only the values outside the range will 'flip' sides. So when you choose 0 and the highest value, there will be no higher value to 'flip' to the negative side.

U can try to every possible assignments from children to sweets and then reduce the problem to some toposort problem where u add edges from sweets to children if its closer than the the assigned sweet.

For H, consider the value a-b instead. You want to maximise sum of (a-b) of the best m people in the bus. You can use a fenwick tree to maintain it.

How to solve L and M? For L, I tried cheesing with bitsets but doesn't work :(

Starting from the leaf with the deepest depth, mark all nodes as visited as you go up, until you reach another visited node, then store the number of nodes as a path. Do it from deepest to shallowest.

Note the unusual timing, it is 30 minutes earlier.

I didn't notice it -> came to contest 20mins late -> only managed to code and solve F1 5mins after contest end! What a sad day.

I think it is easier to reduce the question to the following: Flip all the bits k times (meaning to say flip all the bits once if k is odd and do nothing otherwise). Then you need to do k operations of flip one chosen bit. It is easier to reason about things this way. Observe that flipping everything and then flipping one bit is an equivalent operation.

I think the key observation is that if minus count > plus count + 1, you can always combine some minuses together to makes plus (since they would definitely be minuses adjacent to each other), which simplifies the question greatly because now you don't really need to keep track of the position of minuses and whether they can merge or not. When that idea struck me after trying for a while, the question became rather classic.

How to do F? I kinda figured out you need to find an MST where the $$$a_i + a_j$$$ part of edges add up to 0. However, I am not sure how one would do that though.

delayforces REEEE

How to do F?

how to do F? Is it some DnC magic?

How to solve Div 1D? I have a feeling I am missing some important observation.

Imagine getting penalty (and time penalty because I doubted my solution) for D because of this: #define INF 999999999

It seems for E, you can just copy and paste this , modify it a little and run binary search to get K. Unfortunately, I was unaware of it and coded a solution from scratch... RIP rating

I solved it by cutting the tree up with a couple of DFS and height counters, what is small child trick and Aliens trick though?

Delayforces!

I realised it only 1-2mins before the contest end that you do not need to do that, you just need to make sure that the number of W cells = number of B cells. Forcing number of BB = number of WW while not caring the number of WB and BW, it is actually the same as the constraint number of B cell = number of W cells. Of course, you have to deal with the case where there is no BB or WW.

Figuring that out too late and having my C fail systest means I will be back to candidate master :(

Yes, I agree. I also started CP with CP4 last November and did most of the problems in Book 1. With just Book 1 and the Math chapter in Book 2 (important for Mathforces), you should be able to do most rated <2000 problems which is like until Div2D. Beyond that, you probably have to dig around and learn more exotic stuff. You can also do past IOI/ICPC problems.

Sad, I should have googled this trick earlier in the contest and would not have wasted 1.5hours debugging B trying to figure out what's wrong. In the end I changed my code from recursive to iterative out of desperation and AC. But, because of that, I did not have time to do C....

How to do E?

I did the same thing but used a Fenwick Tree. Unfortunately, it TLEs. Maybe $$$O(nlognlogn)$$$ is not intended to pass.

How to solve Div 1C/2E?

Is Question E a MCBM problem? I was thinking of modelling both of the possible moves as a fraction x/y then try to do matching between points with the one of the same fractions. However, this is potentially O(n^2) so I am not sure if there is a way to optimize it.

Can someone explain Problem E? I sorted it by descending |ka -kb| pairs and queries a b if a>b and b a otherwise until I get a match. I did not expect it to work but somehow it passed test cases.

How to solve Div 2 E?

.

How to solve E?