When the $$$2 \times 2$$$ matrix is empty, there are actually $$$6$$$ ways to fill it such that every square will add to $$$2$$$. Here are the options:

10 10 11 00 01 01
01 10 00 11 01 10

So when we set the cell with coordinates $$$(1, 1)$$$ we get only first $$$3$$$ options out of the above.

Your input/output is too slow. This is caused by using iostream (cin/cout) with stdio (printf/scanf) synchronisation. Add the following lines to boost the speed considerably.

ios_base::sync_with_stdio(0);
cin.tie(0);

Beware, however, that this makes it dangerous to use cin/cout alongside printf/scanf.

I submitted your code with these two lines and it works within the time limit (129564251), albeit still a bit slow.

I do not understand what the variable names mean exactly but based on what I've written in my solution, the first bit of code should be the embodiment of the following train of thought:

if there are no forced stripes (horizontal or vertical) and no rows or columns have any cell coloured in them (they are not set in place) then
the possible number of colourings is:
Assume there are horizontal stripes, that gives 2^n different colourings.
Assume there are vertical stripes, that gives 2^m different colourings.
But the two cases above share two colourings, which is the checkerboard pattern and the anti-checkerboard pattern, which have to be subtracted from the total.

The second bit of code I couldn't decipher, but it's likely something similar.

OK, I implemented my own version and I think the code is a bit more self-explanatory. If anyone has trouble understanding Roms' implementation (as I did), then maybe looking at mine (129556708) will help.

People used a funky priority_queue based Dijkstra implementation! A very clever approach in my opinion.

Each vertex is a build and each build is a vertex. However, these vertices aren't stored anywhere in memory but rather, they are procedurally generated. Two vertices (builds) are joined by an edge if and only if you get one of the builds by degrading exactly one item in the other build.

Then, just implement a Dijkstra on these builds and remember to skip the neighbours of a vertex if the vertex is not banned, since the neighbours (degraded builds) can only be worse, as noted in the editorial.

As far as I can tell, I think I did it using a traverse of a trie structure without the structure itself. Take a look at my solution if you want to.

129399828

Thanks!

In problem E, we only have to keep track of same-colour cells with an even number of cells between them?

What about differently coloured cells with an odd number of cells between them? Doesn't that force a strip of width two as well?

So assume we have $$$n$$$ knights with strengths $$$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$$$. Now assume that the dragon has defense $$$x$$$ and attack $$$y$$$, and let's say that $$$i$$$ is such, that $$$a_i$$$ is the smallest of the strengths greater or equal to $$$x$$$. Now I will show why we only need to check $$$a_i$$$ and $$$a_{i-1}$$$ (if they exist).

First, we do not have to check any $$$a_j$$$ for $$$j \gt i$$$ because using greater attack than necessary will not give us any advantage, but may cost us defense points, and thus gold. I think this is fairly straight forward.

Second, we do not have to check any $$$a_j$$$ for $$$j \lt i-i$$$ because:
Assume we use $$$a_j$$$. Then, we lose $$$d = a_{i-1} - a_j$$$ attack points, and gain $$$d$$$ defense points. However, since $$$a_{i-1} \lt x$$$, then it is guaranteed, that we must pay an additional $$$d$$$ gold coins to compensate for the attack. Notice now, that however much we had to compensate for the defense if we chose $$$a_{i-1}$$$, we will compensate at most $$$d$$$ less if we choose $$$a_j$$$. Thus, choosing a knight with strength other than $$$a_i$$$ or $$$a_{i-1}$$$ will never be beneficial.

Soon^TM

Yes, std::unordered_set and std::unordered_map are two STL containers one should always keep in mind when dealing with algorithmics. They use hashing to provide constant time access! However, in a very pessimistic scenario one could potentially encounter data which has a lot of collisions and then the access would have linear complexity. But understandably -- that simply doesn't happen.

One another note, std::vector does not have a built-in hashing function, so it's not compatible with the two aforementioned containers straight off the bat. That is why, during the round, I wondered if vectors are compatible with regular sets and that would be if their operator< was built-in. Just like you, I didn't know, but I opened cppreference.com and looked it up.

Another bit of advice: your way of hashing (don't worry, it's pretty much the only popular way of hashing) by taking elements and multiplying them by a constant and then taking the remainder modulo another constant is rather slow, because the modulo operation is slow. So I wouldn't be surprised if using hashing is still slower than using the logarithmic std::set structure. In fact, looking at your newest submission, that is the case, since it still performs around 3 times slower than mine.

Better luck with all this new knowledge next round!

So you used some form of hashing and then stored whatever data you needed on a set either way? At that point I'd use std::unordered_set...

That being said I used a set<vector<int>> (because std::vector by default compares itself lexicographically) and didn't have any problems with time limits.

Does CodeForces compile into 32-bit executables? I'm asking because long longs are slower only in that case. Another competitive programming site changed compilation to 64-bit and now there is no difference besides memory use.

But additional memory use is not something completely unimportant. Usually it doesn't matter, but problems can easily be made to require better memory use. I've seen a problem (not on CodeForces) which actually required the use of short ints!

Also, having templates with a couple of useful things like #define st first may be good (I personally don't use that), having multiple dozen lines of code (more than fits on a screen) as a template is most definitely a bad practice, especially at the lower levels. And it's not like templates help much besides obfuscating your code to protect against potential hacks. You can take a look at the submissions of some of the top people on CodeForces and all of the ones I've seen fit on one screen. Some of them are even a very modest couple of lines. And they most definitely don't have bullshit like #define int long long.

Just add

ios_base::sync_with_stdio(0);
cin.tie(0);

at the beginning of the main function. This boosts iostream, but makes using both iostream and stdio dangerous, as the two are now desynchronised (as the name of the invoked method implies).

The system tests were ran from the very beginning. Notice, how submission status was never "Pretests Passed (3)" or something like that, but straight up "Accepted". I was surprised when I saw that!

Based on how you explained it here, I think I have the same! Pretty interesting to think of it as a trie. Then again, I only "know" trie in theory and never consciously used it.

This would then require a custom comparator, though. Unless you do another funky thing and let the strength be the first (zeroth?) element of the vector.

Yes, because the Quicksort algorithm, while having "quick" in its name is not that quick after all.

Firstly, its O(n log(n)) complexity is just the average case, although admittedly by randomizing the pivot, the only thing stopping your case from being "average" is EXTREME bad luck, so this is negligible. But...

Secondly, std::sort is a wicked hybrid algorithm optimized for all kinds of stuff and well... it's faster.

That would indeed force you to change the comparator and I think it wouldn't be worth it because:

You'd have to recompute the sum of the values every time you need it, which increases the time complexity constant, which isn't good, and

You'd lose time on writing a custom comparator which is not exactly the easiest thing to do and can easily go south, so unless you've already done similar stuff, it's risky, and even if you've got experience with that, it's still a waste of time during the round.

The only "pro" of this approach would be to save some memory, which is negligible. Much more so than the time you would otherwise save.

If you want to keep using cin and cout add these two lines at the beginning of the main function:

ios_base::sync_with_stdio(0);
cin.tie(0);

As far as I can remember these lines desynchronise iostream and stdio and perhaps do something more which makes using both input methods dangerous, but as long as you are using only cin and cout and these two lines, you shouldn't run into any time limit problems caused by input/output.

Hi, so I have a question for the community as well, the answer to which influences your case.

I see that the limits for a solution are the same regardless of the language in which the solution is written. Does that mean, that using Python (without extensive Python optimization knowledge) instead of a much faster (in common use) language like C++ can greatly influence scores on CodeForces?

I am asking this, because this is exactly what happens on another competitive programming website on which I am a regular organiser (instead of participant) and thus, we don't allow Python there.

I took embarrassingly long too! I had it slightly differently.

Yours is better. And, well, you must admit, this is a very simple few lines of code. It's just that problem A was probably not the usual stuff you'd expect and that's why it took so long to think of!

Perhaps you have a logic mistake in your algorithm. I thought I had it too but it turned out that I made a mistake and had to think of a different way to save myself from checking all exponentially many possibilities.

Edit: oh, derp. I misread and thought that the question was about problem D. Sorry!

I am sorry to be "that guy" but I think your question isn't very clear. I'd happily help (I solved D) but I can't if I don't understand the question!

Yes!.. No? Maybe.

Check this solution out!

Oh holy crap this is brilliant. And here I got stuck with some greedy ifological strategy which... I'm reasonably confident would work but I didn't manage to implement it.

This work is O(nlog(n)) though due to the heap! But it's still a fine approach.

Oh I completely misunderstood that comment. I got it now, thanks!

Yes, and?

Doesn't this require sorting, which yields linearithmic time complexity either way?

Using SCC is a bit overkill and definitely a waste of time for this problem.

The goal (when checking if understanding the book is possible) is to check if there is a cycle. We can do that with a DFS (or multiple, in case of a DAG, which we are dealing with here) which, instead of marking a vertex visited, can set two different kinds of flags.

The DFS works as follows:

1. Set flag "in progress" for current vertex
2. Consider all neighbours, for each 2.1. If its flag is "in progress", then a cycle is detected 2.2. If its flag is "unvisited", then run the DFS on the neighbour.
3. Set flag "visited" for current vertex

We can count the result with a DFS too, using dynamic programming on a DAG. Every vertex with no outgoing edges receives value 1, because that chapter will be understood during the first reading of the book. Every other chapter will be understood after all its prerequisite chapters are understood, so the result for the chapter is the maximum of the results for the prerequisite chapters... but slightly modified to account for the order of the chapters in the book.

I'm not the best at explaining so maybe my code will help.

Using multiplies() is probably a very bad idea because it will most likely overflow but yeah, using a function, perhaps a lambda [](const int& a, const int& b){return (a*b) % MOD;} would be nice.

Oh, now this strikes a bell.

So what you are suggesting, is to find the largest square that divides every number in the range, then replace every number in the array by itself, divided by that largest square divisor, and we will be left by the product of primes (with exponent equal to 1), which we are looking for. Darn, simple and elegant.

Then, let's say we are given x and y. Then let x' be x divided by its largest square divisor, similarly define y'. Then, x is adjacent to y if and only if x' = y'. Did I get it right? Brilliant. (And well in the range of my abilities, but oh well...)

It seems we have fallen victim to a minor misunderstanding. I wrote "what you wrote IS TRUE for any x and y".

Which, in that case, says nothing about x and y themselves, when the goal is to determine whether they are adjacent.

There is no counterexample because this works for all x and y.

What you wrote: if k=x*y, then (k/gcd(x,y))^2 is a perfect square. It doesn't even matter what k is. You have written a tautology.

Edit: nevermind, it does matter what k is. But as long as k = x*y, then k/gcd(x,y) = lcm(x,y) is a whole number, so that squared is a perfect square. Still a tautology.

cin.tie(0); cout.tie(0); also helps. One of them does next to nothing but the other one has a significant impact as well, although will make it so that your input flows to the console at the moment that the program comes to an end, which means it's rather bad for debugging. I never remember which one is which.

What you wrote is true for any x and y. You essentially wrote that LCM(x,y)^2 is a perfect square.

The editorial mentions, that LCM(a,b) = a*b/GCD(a,b). This is a well known fact. It is easy to prove, I will assume I do not need to.

What is LCM(a,b)/GCD(a,b) then? Well that is equal to (a*b/GCD(a,b))/GCD(a,b) = (a*b)/GCD(a,b)^2

And the numbers a and b are adjacent if and only if that number is a perfect square, so (a*b)/GCD(a,b)^2 = X^2 for some integer X. Which means, that a*b = GCD(a,b)^2 * X^2 for some X. Now that is true if and only if a*b is a perfect square itself. Then, we can divide that perfect square by GCD(a,b)^2 and we will receive another perfect square, denoted by X^2.

Didn't even read F, got stuck on D and for way too long. The (simple in hindsight) observations took me too long and ultimately I ran out of time, trying to think of how to find a solution in O(nlogA)... which admittedly, I am still searching for, and the editorial mentions it's "simple". Alright then, keep your secrets haha.

It probably is simple though. Apparently I just had one of them bad days.

The example with persons A and B is not an example, but a proof, that the optimal solution does not contain a situation such that a person with higher k_i got a more expensive gift.

I don't know if proof of the correctness of the greedy approach is simple, I for sure, cannot formalize it. But I understand it intuitively. Essentially, by giving the cheapest gift to the person with the greatest k_i, you will be always as well off as in any other situation. Then, you have to repeat the process for the same set of gifts, minus the cheapest gift and the same set of persons, minus the person with the highest k_i

Will this round influence our ratings? If so, then when will the ratings be updated?