Yes it is related, you are missing the case when you split the augmenting path in two and shift everything in each half to cover the free cell instead of shifting everything along the path ie creating two free cells at the end or the beginning.

Welcome to the club

A student who meets the Basic Requirements and FIRST began post-secondary studies in 2017 or later is eligible to compete. A student who meets the Basic Requirements and was born in 1998 or later is eligible to compete.

Did they increase the age requirement ?

I suppose that if they won't count the WF 2020 they should.

I knew he would make it :)

I hacked both

I cannot believe this solution passed system test 124170859 on problem D.

I fucked on uoi and came...

What a chad

I passed it in 3.5s :) 122866086

Yeah that's probably the real reason, but it killed my $$$O(n^3 log n)$$$ fft solution, so i had to squeeze it in $$$O(n^3)$$$.

I guess the given mod on E is to stop fft solutions, though 114961513 it can be passed easily, sadly i finished some minutes after the end :(

Contribution is overrated.

I forgot to sort the adjacency list to perform binary search after i switched from set to vector (because the amazing tle) and it somewhat passed even the system test, amazing tests too ;)

https://codeforces.me/contest/1439/hacks/678778

To be honest seems more hard to create tests where my solution is correct than where it's wrong, but you guys did it, unbelievable.

I had the same issue, having 168 * 200000 vectors with one element is very bad, avoid small dimensions at the end.

I did if (n > m) swap(n, m); and got AC with less than 200MB

https://github.com/mfornet/acmx/wiki#basic-settings

I did another random sol 89458561 during testing, I have an extra log because I was lazy to code linear sort, but it seems pretty fast, my idea is: take a random dfs tree find the diameter or try pairing consecutive nodes(ordered by depth).

As a tester you will know why 5 is enough :)

Or just a person with bipolar disorder :)

I'm lazy to write it, this is almost my sol by dorijanlendvaj

dp[i][j]=amount of solutions if you remove index j of string i looking at strings<=i add a space at the end of each string for each string you can sort indexes by the substring you get when you remove that index(how is left as an exercise to the reader, you can compare 2 substrings of 2 strings in log with hashing you can also compare (string x without index i) and (string y without index j) using 3 substring comparisons now you can do 2 pointers on the sorted indexes on this string and the previous strings to find which dp values of the previous string to add to the dp values of the current string

I got tle on system tests because I did everything with extra log, here is the same sol in C++17(64) :)

"also most testers did not find any problems boring" I guess you're talking about A-D maybe

Please stop writing problems like E

It seems that your testcase takes advantage of how I'm traversing the graph and causing lot of cache miss.

Passed it now :)

88143085

88143055

Hi again it's almost 6am now :)

This sol 88113088 (3.8 seconds) is an official sol (the one I messed up in my first comment), but doing only dfs instead of bfs + dfs for each mask and relabeling the nodes to make it more cache friendly.

And this 88113666 (1.7 seconds) is the same, but giving priority to time consuming masks (this idea was in another official sol which I did to speed up $$$O(2^k * flow)$$$ sols)

Hi, marX sol got tle on your last test because it's not cache friendly on it, I fixed it but it's almost 4am and I don't want to set it as model without checking it carefully, here is the sol in advance: 88104366 88104631

Yes, the dp is well defined in each one, remember that at the end we use $$$dp(i)$$$ where $$$i$$$ is the position of the first one.

I messed up something in my last sol that I added like ~30 mins ago and it fail on pajenegod test, I set the old model (which is correct and was used in the contest) for now again.

Thanks, it's fixed now :)

I'm pretty sure he rejected ~15 problems

Thanks anthoctryhardO_o for this beautiful round!!

Now I finally know how to become red

Trial_and_error XD

I got AC, copying and pasting that code, just changing EPS and using long double

Same complexity, doesn't need any updates but with a worse constant in the query, so it's more slow :(

Can you explain how you do that in O(n), smh

Someone passed Chefland Squads and the Army Chief with wavelet matrix ? (I got AC with fenwick tree ):)

It is a possible reason, but I think maybe the main problem is that the judge divides the test cases into different (processes or threads), in case of failure of any test, killing all (processes or threads) for higher numbered tests takes time

I got $$$O(n 3^n)$$$ 78249435 because I conjectured that the minimum value of the last element can be implicit in $$$dp_{pos,mask} = $$$ (the minimum number of operations, the minimum value of the last element), What do you think ?

So 125M is the new standard for 2 seconds, smh

Lemma: Only the last and maybe the first element appears once in the input

You know that one of them is the last element, fix the last element and remove its segment (it's unique), again the lemma is true, keep doing it while the last element is unique, when it is not, one of the elements is the first, then fix the first element, now the last element must always be unique and you can restore the permutation.

So summarizing, you have two possible last element this take $$$O(2*n^2)$$$ and each one can return two possible first element, so you need $$$O(4*n^2)$$$

Complexity should not intimidate participants with such high constraints

Why the hell are you waiting $$$O(720 ^ 3)$$$ operations on double in problem B ?:(

It can be solved even in $$$O(n^2)$$$ https://codeforces.me/blog/entry/76306?#comment-608280

vovuh Maybe you want to mention that there is a $$$O(n^2)$$$ solution

I have a solution $$$O(n^2)$$$ https://codeforces.me/blog/entry/76306#comment-608280

77550191 $$$O(n^4/32)$$$ using bitset

77584382 $$$O(n^2)$$$ using the fact that only the last and maybe the first element appears once in the input

https://clist.by/standings/code-jam-round-1a-16820932/?country=

4 1 3 3 7 8 7 9 10 7 11

3 5 0 -2 5 3 6 7 8 2 4

You need coach mode or solve the problem to see the solution, so here are the codes:

optimized solution AC 1747 ms

original solution TLE

ok, put 3 or 4 seconds not 2

I have another completely different beautiful solution with same complexity, but I need two fenwick instead of one and that's why I got TLE, so after many many many optimizations finally I got AC with the monster that my solution became 75647531

Just my opinion: I think that the main purpose of the time limit in a problem is to differentiate a $$$log^3$$$ from $$$log^2$$$ or $$$log$$$ from $$$log^2$$$ etc... not force the contestant to do constant optimizations...

"How to deal with TL? There are three parts of solution which give log^2: coordinates compression, events sorting and Fenwick tree. We will get rid of the first two, leaving only log^2 from Fenwick"

What is the point of making constant optimizations ? The difficulty of the problem is not how wtf it would fit in 2 seconds, instead of write some decent $$$O(n $$$ $$$log (n)$$$ $$$log (4*10^8))$$$

Solution 75417750 Contest submission 75411025

The idea is start a bfs from every possible start for a total of $$$O(n^3)$$$ and use Hungarian with the same complexity, look at my solution

It's easy to prove https://codeforces.me/blog/entry/8219?#comment-139242

Use https://en.wikipedia.org/wiki/Hungarian_algorithm

Suppose that you want to know for a fixed $$$k$$$ if the answer is $$$\le$$$ $$$k$$$

Let's see it as an array $$$A$$$ of $$$n$$$ elements with value $$$k$$$

Then for each query $$$l, r, x$$$ you need to subtract a total of $$$x$$$ between $$$[l, r]$$$, if you can do that and $$$A_i \ge 0$$$ for all $$$i$$$ in the end then the answer is $$$\le k$$$

The best way of do that is greedy sorting the queries by $$$r$$$ and for each one do:

for i in [l, r]:
    z = min(x, A[i])
    A[i] -= z
    x -= z

if all the queries have $$$x = 0$$$ in the end the answer is $$$\le k$$$

For speed up the solution just use the compression path idea of disjoint set for find the next $$$A_i \gt 0$$$ instead of iterate from $$$l$$$ to $$$r$$$, here are the solution

Binary search on the answer, sort the queries by $$$r$$$ and for each query go from $$$l$$$ to $$$r$$$ taking the maximum you can until that query become 0 or it's impossible.

Problem K: The arrays x and y will be destroyed after this query; the new array receives the index of the smallest positive integer that has not been used yet. The meaning of destroyed in this case is very confusing, I couldn't send it in time because I understood that destroying restores the id :(

Several months ago I send a email because I won laddus and didn't receive it, after the third email finally I get my laddus, currently I won laddus on two more contest and never received it I send another email and I never receive a reply, it's very annoying the situation.. So I decided ignore all that come from codechef, sometimes I participate in a contest but just for fun.

awoo Why the same solutions receive completely different times?:

72925974 4321 ms = 72925981 2885 ms

72927822 1668 ms = 72927856 920 ms

1316E - Выбор команды can be solved too running $$$p$$$ times a min-cost-max-flow algorithm where the max-flow is $$$p$$$: 72494005

You can ignore the degree of a node because the bfs order is a topological order of the shortest paths graph, awesome ;)

Yeah, But I wanted to share another solution that involve more thinking about graphs and for my it's cool and simple. Btw you are one of my favorite L$$$\color{red}{\textrm{GM}}$$$.

Every edge that don't belong to the shortest paths graph from node $$$1$$$ can be deleted, because it isn't optimal traverse along it before take the added edge, so the graph now is a DAG and have a topological order, in that order the added edge connect two special nodes so for every special node $$$u$$$ if it's a extreme of the new edge is optimal connect $$$u$$$ with the node that maximize the distance from $$$n$$$(in the original graph) and is at the right of $$$u$$$ in the topological order.

Problem 1307D - Cow and Fields can be solved in linear time 71305246 doing a topological sort over the shortest paths graph.

What do you mean by path compression ?

$$$O(n)$$$ with a stack, while the top is <= x pop, then top is the next largest element and push x to the stack.

"for a full test case, the lenght of the euler circuit is nearly $$$10^6$$$, it is almost not impossible to compress its length into $$$\frac{1}{300}$$$ of the original length" 70990140

Do you have a link for this problem ?

A year ago I implemented that (in linear time) for buscando-palabras (the constraints allow quadratic solutions but I wanted to challenge myself with a linear solution).

My solution passed in one second

I implemented the solution with dsu but put stupidly(r instead r^x) bug and I couldn't submit it on time, so I don't know if my solution would pass

When I can submit again ? It say "You're not allowed to submit at this time."

You can use euler tour + segment tree + trie or dsu + trie(with lazy and a function for merge two tries) over the final tree, in both keep for every node of the trie the most "old" node in the subtree(necessary for search the maximum xor only with the nodes added before the current query)

Simplex_algorithm

log(1e9) = ~30 not 1e3

Happy Hacking in 1288F - Красно-синий граф 68818026 !!! System test passed!! awoo it should be ok?

Remplace all a * b with (long long)a * b % mod

What are the hacking test cases for 1279F - New Year and Handle Change ?

My solution for problem E is similar but definitely much shorter, the main idea is to take an arbitrary triangle to remove it and recursively solve on the three sides, I have a list with the order of vertices and other for the order of triangles, in my recursive function I have a fixed side(edge) then I find one arbitrary triangle with that edge and solve similarly for both sides

Reading $$$3 * 10^6$$$ numbers of $$$19$$$ digits is not a good idea. Even the solutions in $$$O(Q * log(R))$$$ without many optimizations got TLE :(

Can someone explain what is the complexity of your solution for The Inexplicable Giant Floating Baby Head

It's $$$\lceil{log_2(N)}\rceil$$$ the minimum number of airlines required for the Div1 500 problem ? If it's true how to prove that is a lower bound ?

When the results will be posted ?

I thought about that for a while at the end of the contest, but I don't know how to send flow through the students which attend three or two classes, I solved it using simplex method but didn't have enough time for implemented it in the contest

Solution 66967994 using simplex method should be correct for 1271F - Divide The Students ?

Here is my solution

But if the hash is as I said, isn't easy to break it on function of $$$u$$$ and $$$v$$$

The hash should be: Hash of string of path $$$u..R..v$$$ is $$$hash(u...R)+hash(R...v)∗base^{dist(R,u)}$$$ and hash of string of path $$$v..R..u$$$ is $$$hash(v...R)+hash(R...u)∗base^{dist(R,v)}$$$ ?

Using your hash definition the letter on node $$$R$$$ is counted twice, this can be handled...

+

If you pass $$$k \gt 1$$$ units of flow on some edge then these edge have cost $$$k$$$ not $$$1$$$, so I think that your solution are wrong, you have implemented it?

Between witch nodes are you running min-cost-max-flow ?

Your solution got AC :), I changed a bit your segment tree (it's not very efficient), It's so painful see one line with 1000+ characters :(

Try using fast_mod, my 65887298 is almost the same and only with fast_mod pass the testcase 14

65657404 your code runs on ~600 ms, if you call check $$$~log2(min(n, m))$$$ times. Look at the two lines before for (int step...

I got AC (~500ms) 65655948 using prefix sums, without any optimization.

My idea was the following, for a fixed type of element $$$x$$$, construct an array $$$b$$$ such that $$$b_i = +1$$$ $$$if$$$ $$$a_i = x$$$, $$$-1$$$ otherwise, then accumulate $$$b$$$, if a interval $$$b[l...r]$$$ is dominated by $$$x$$$ then $$$b_r - b_{l-1} \gt 0$$$, so we have an $$$O(k * n log n)$$$ solution using fenwick tree or ordered set for count how many $$$b_{l-1}$$$ satisfy the condition for a fixed $$$b_r$$$, for the $$$O(n log n)$$$ solution, before accumulate all the elements of $$$b$$$, compress all sub-array of $$$b[l...r] = -1$$$ on a single element with value $$$-(r-l+1)$$$ then maintain on a segment tree for each position $$$i$$$ how many numbers are lower or equal that $$$i$$$ so for a element of $$$b$$$ (without compress) the answer is some position of the segment tree, if the elements is compressed then the answer is a range (note that none of the prefix sum that ends on the compressed element is candidate), and the update for a element without compress is add $$$+1$$$ on some $$$range[j, +oo]$$$, if the element is compressed the update is like add $$$1, 2, 3, ..., w, w, ..., w$$$ on some $$$range[j, +oo]$$$. This is my submission for more detail. I tested it locally and it runs on ~6 seconds with $$$n=k=10^6$$$, i know that my segment tree not is too fast, so probably i should need change them :( UPD I got AC improving my segment tree

Someone solved F using segment tree adding arithmetic progression on range ?, i got TLE with my implementation O(n log n) but with a bad constant, Maybe someone have a more simple solution ?

For problem F — Cheap Robot i have one alternative approach 65217904 that not use the observation "replace the weight of each edge $$$(u,v,w)$$$ by $$$w′=du+dv+w$$$". Run Dijkstra from node 1, when reach other node $$$u \in [1, k]$$$ not already seen connect $$$u$$$ with the origin of the minimum path that reach $$$u$$$ with cost $$$dist[u]$$$, set $$$dist[u] = 0$$$ and push $$$u$$$ again on the queue and continue running Dijkstra. Basically i am doing Prim over the nodes $$$[1, k]$$$, so i have a Spanning Tree of the nodes $$$[1, k]$$$ on which for every pair of nodes $$$u, v \in [1, k]$$$ in the original graph the maximum traveled distance (without recharge) between the nodes $$$u, v$$$ is minimized, so the answer for every query is the maximum on the unique path between $$$u$$$ and $$$v$$$. The most interesting part is the complexity of the modified Dijkstra, I'm 99% sure that the complexity still $$$O(E log E)$$$

Div1 B can be solved almost directly using Borůvka's algorithm, but on the contest i found more convenient using a mix of bfs and Borůvka idea 64380663

My greedy 56221717 passed that test, but i think that maybe my solution should be wrong.

I added #include <bits/stdc++.h> using namespace std; and got CE again, i compiled in c++, but now i am not sure about this "You have compilation errors listed when you try to compile, read them and figure it out from there." Thanks for replied

I am new on topcoder, i try to submit the following code for the second problem and i got compilation error, i wasted much time on that, so i decided implemented it on python, finally only remains 10 min and i got very low score on this problem. Someone can said me, why i got compilation error ?

class OrderlyString
{
public:
	int longestLength(string s)
	{
		int n = s.length();
		vector<vector<int> > dp(n+1, vector<int>(26, -100000000));
		dp[0][0] = 0;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < 26; ++j)
			{
				dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
				if (j <= (s[i]-'A'))
					dp[i+1][s[i]-'A'] = max(dp[i+1][s[i]-'A'], dp[i][j]+1);
			}
		return *max_element(dp[n].begin(), dp[n].end());
	}
};