Hello Codeforces!!
We're honored to invite you to TheForces Round #17 (AOE-Forces) which will take place on Jun/17/2023 18:05 (Moscow time).
The registration is open now! please don't forget the time.
You will have 2 hours and 15 minutes to solve 6 problems.
Problems were prepared and authored by: noomaK, Amir_Parsa and lakshya7878.
Also huge thanks to our army of testers: Bucketsmith, __jk__, Little_Sheep_Yawn, Alfeh, milind0110, tyr0Whiz, wuhudsm, k1r1t0, blxst, Airths, adventofcode, random.cpp, yazan_istatiyeh, iiand, BallBreaker, DARK-N, Banis and EndlessDreams.
- Also we want to thank You for participating in our rounds.
Discord Server (1000+ people, join for a cookie)
Nice round! Neat problems! Hope you'll enjoy!
As a tester, I can confirm to you that the round is great and all the problems are interesting. Good luck in the round!
As a Friend of the tester. Please give him contribution because he deserves it.
As a tester, I remind you to join the Discord server!
As a participants i am in
Excited for this
AOE2 is my favorite game in my childhood! I still play it now. However every time when I play this game before a CF contest my performance would be a disaster...
As a tester, I can assure that everyone will have a non-negative delta in this round.
Also non-positive.
As a tester, problems are interesting, hope you can enjoy them!
As an author, give me contribution ;)
TheForces Orz!
My favorite RTS game! Wow!
OMG AOE-Forces Round :)
excited
As a tester, I like playing as holy roman empire in aoe4.
wanna play mirror HRE?
as a tester, u will enjoy solving the problems:)
I'm excited for this Thanks for your efforts guys
Warrior Scouts are the best!! ILALUUUUUUU
I'm coming with the mangudai
I hate them! They're so fast and always kill my eco lol
As a participant,I shall play as english
I wish I won't go with the late game choice Xd
As a tester, You will enjoy balanced problemset ;)
I think it's time for real eltihab my friend
Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).
Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).
For problem D, I have a complexity of O(n * 2^k * k). The author's solution seems to have the same complexity. But my solution keeps getting TLE. Can anyone tell me where I am going wrong? Link to Submission: Link. Thanks in advance.
Note that you are using
__gcd()
too. So your complexity is not $$$O(n \cdot 2^k \cdot k)$$$.But in the editorial there is also a line checking if __gcd(a[i], a[j]) is 1. I think the solution in the editorial also uses O(n * 2^k * k) other than the __gcd() check.
Order of loops matter too. Look at the editorial code carefully. They are checking
gcd
for each possible pairs only once.Got it. Thank you!
I nuked $$$D$$$ with the Micali-Vazirani (MV) algorithm. See:
An $$$O(|E|\sqrt{|V|})$$$ algorithm for finding maximum matching in general graphs, Silvio Micali and Vijay V. Vazirani, 21st Annual Symposium on Foundations of Computer Science, 1980.
It is a very advanced algorithm. Note that the complexity of the Edmonds blossom algorithm is $$$O(|E||V|^2)$$$, which is not sufficiently fast! For the MV algorithm, I adapted a code from a github repository. Its code quality is reliable.
My final code:
Overall complexity:
Part1: Calculating the gcd and constructing the graph: $$$O(nklogmaxa_i)$$$.
Part2: There are $$$|V|=n$$$ vertices and at most $$$|E|=nk$$$ edges in this graph. Thefore, the complexity of the matching process is: $$$O(n^{\frac{3}{2}}k)$$$. In practice, there is an additional log, i.e., $$$O(n^{\frac{3}{2}}k logn)$$$.
Therefore the overall complexity is:
$$$O(nk(logmaxa_i + \sqrt{n}logn))$$$, which can pass this problem easily. Also, MV algorithm is not a randomized algorithm, so the complexity is guaranteed no matter what the test data are.