Hello!
We are glad to announce the start of the sixth edition of FIICode!
The format will remain the same as last year (3 qualifying rounds and the final one). All rounds will be held online on CSAcademy.
Because the final is online, we decided that this year the contest will be national, meaning that only the first 25 Romanian / Moldovan participants will be able to officially participate in the final round and win the prizes. But those who cannot officially compete in the final are of course welcome to participate. Also, the difficulty of the qualifying rounds will be similar to a Div.2 Codeforces contest (slightly easier).
The problems are created and tested by bicsi, Juve45, denis2111, lungualex00, cristian1997, sebi110, vladd, Fanurie, antohir, RazvanPanaite, IulianOleniuc, ApetriiRadu, pauldiac and smoc_georgemarian.
To officially participate you can register here.
The first round takes place Saturday, April 17, 18:05 Romanian time.
LE: First round starts in 1h
The second round takes place Tuesday, May 4, 15:05 Romanian time.
The third round takes place Friday, May 21, 18:05 Romanian time.
LE: Third round starts in 2h
Excited to participate after a long time at CSAcademy.
But the round clashes with TCO21 Algorithm Round 1A. Is it possible to move the contest time an hour early?
We apologize for the overlap, but we think that some of the participants would not know in time if the contest would start an hour earlier so we will not change the time of the contest.
Once every year CSA rises from the dead for FIICode.
Your dp is quite apt for this statement.
Hey, since this is held on CSA I want to bring a few issues into light in hopes that they can be fixed and will not ruin FIICode.
I have done a few virtual contests on CSA lately and noticed the following:
Thanks for the notifications, we are looking to solve them today.
Auto comment: topic has been updated by Fanurie (previous revision, new revision, compare).
Where would the contest link be given? Fanurie
https://csacademy.com/contest/fii-code-2021-round-1/
Auto comment: topic has been updated by Fanurie (previous revision, new revision, compare).
How to solve endgame?
Not sure if this soln was intended.
But for Scrambled Eggs, this assignment problem can be converted into a bipartite graph matching problem with given nos on one side and primes factors on another side. Then it asks for a match of size K. Same nos on the left side can be compressed.
The editorials for all the Round 2 problems have been posted on CSAcademy. We can further discuss solutions here.
I read the editorial of Endgame. Suppose there are segments $$$[0,1], [1,2], [3,4], [4,5]$$$, It seems editorial says $$$\{[0,1],[1,2]\}, \{[3,4],[4,5]\}$$$ are chains. I think this is not true because they are not maximal. $$$\{[0,1],[1,2],[3,4],[4,5]\}$$$ satisfies the condition then this is a chain.
Sorry if I misread the statement.
A chain is a maximal set of intervals with the property that for any interval I in the set, there is an interval J in the set (I \ J) such that their intersection is non-empty or I is the only interval in the set (the intersection is considered non-empty even if the intervals intersect in a single point). This is the definition from the statement.
Thus {[0, 1]} is not really a chain because it is not maximal, we can expand the set by adding [1, 2] to it.
EDIT: your example is not a chain because it is not connected.
It seems there is no restriction for connectivity.
In $$$\{[0,1],[1,2],[3,4],[4,5]\}$$$, when $$$I=[0,1]$$$, there exists $$$J=[1,2]$$$, etc.
It seems you are right. I read the statement again and it looks like the definition does not imply connectivity as I previously thought. When I first read the statement I thought "hmm maximal set of intervals...hmm every interval I has another interval J such that their intersection is non-empty, this must mean that the chains are actually connected components". This is one of the rare problems which in order to solve it you have to read the statement wrong:)
All in all, this looks like an honest mistake on the part of the authors.
We are very sorry for the mistake in problem D of round 2. We should've mentioned that the intervals in a chain must be connected. We hope it affected you as little as possible.
I've solved Endgame with another approach. Instead of segment tree I've use stacks, and made two passes (one from left to right, and one from right to left). While iterating from left to right standing at position $$$x$$$ we need to know what is the maximum number of chains can be made from the segments that have both ends strictly to the left from position $$$x$$$. We can keep all those chains in stack (actually, we need to save only rightmost point of each chain). Similar for right-to-left pass.
Auto comment: topic has been updated by Fanurie (previous revision, new revision, compare).
Auto comment: topic has been updated by Fanurie (previous revision, new revision, compare).