Greetings Codeforces Community!
Hope you are doing well, practicing social distancing and are continuing to learn during this time.
The CodeChef April Long Challenge will begin soon! That means 10 days of intense non-stop coding where you can learn while competing in a contest.
The contest will be live from 3rd April till 13th April. So code, learn and don't forget to become a part of this exceptional race to the top of the leaderboard.
The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese.
Also if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here.
Code against Programmers from all over the globe in this thrilling contest! Accompanying me on the problem setting panel are:
- Setters: Kritagya Agarwal, hackslash_123 (Raj Khandor), dvyn01 (Divyanshu Pandey), BohdanPastuschak (Bohdan Pastuschak), pieguy (David Stolp), 300iq (Ildar Gainullin), Dragonado (Chaithanya Shyam), Ashish Lal
- Tester: fmota (Felipe Mota)
- Editorialist: taran_1407 (Taranpreet Singh)
- Statement Verifier: Xellos (Jakub Safin)
- Admin: Alex_2oo8 (Alexey Zayakin)
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Vietnamese Translator: Team VNOI
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava
- Mandarin Translator: Ioser (Hanlin Ren)
Contest Details:
Time: 3rd April 2020 (1500 hrs) to 13th April 2020 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://bit.ly/APRIL20-Codeforces
Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes: Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/
Good Luck! Hope to see you participating! Happy Programming!
Just wondering
Is it not possible for setters of the round to make alternate accounts and win and claim the prize?
Big brain!
Hi all,
The editorials for all except TRIPWAYS and LLLGRAPH are posted at discuss.codechef.com Sharing brief hints for last two problems here.
The number of ways to reach city $$$N$$$ in $$$D$$$ days can be basically written as a linear recurrence, with its transition matrix being same as adjacency matrix for positions not on main diagonal elements and $$$L_i$$$ for position $$$(i, i)$$$ in matrix. We can use matrix exponentiation to solve in $$$O(N^3+Q*N^2*log(D)$$$ by precomputing powers of transition matrix.
One way is to use Berlekamp-Massey Algorithm along with FFT as mentioned here but this might have too high constant factor, so do as the setter says. The best setter notes i ever saw. Thanks to @pieguy
Jordan decomposition solution (Setter's solution) Since Chef only moves from lower numbered cities to higher numbered cities, the adjacency matrix is triangular. It follows that the eigenvalues (let's call them E_i) are the values on the diagonal, and therefore a Jordan decomposition exists.
Denote m_i to be the multiplicity of a given eigenvalue — 0 for the first occurrence, 1 for the next, and so on. The existence of a Jordan decomposition implies constants $$$C_{j,i}$$$ exist such that the number of ways to reach city j in D days is given by $$$\sum_{i = 1}^N((^DC_{m_i})E_i^{D-m_i} * C_{j,i})$$$. We only need to compute these constants. Complexity: $$$O(N * M + N * Q * log(MAXD))$$$
For 30 points, the max independent set of L(G) is the size of maximum matching in general graph, which can be found via Edmond Karp/Blossom algorithm.
For full solution, solve for each connected component independently. So $$$k \leq 6$$$ and we need to find the max matching. Let's simulate and find the first line graph, calling it $$$H$$$. Now the Number of nodes in graph is up to $$$M$$$ and number of edges up to $$$M^2$$$. $$$k \leq 5$$$ on graph $$$H$$$ would work.
Fact: The size of maximum matching in line graph is just the number of vertices in L(G)/2, which is same as the number of edges/2 in $$$G$$$. So, we need to find the number of vertices in $$$L^5(H)$$$ which is same as number of edges in $$$L^4(H)$$$
We can use the fact that number of edges in a graph is $$$\sum d_i(d_i-1)/2$$$ and casework to solve the rest.
Hope you all had a nice contest. In case i made any mistake, do let me know.
For TRIPWAYS, I tried modifying Berlekamp-Massey to use FFT but it is unclear how can lines 69-72 in the mull function be computed using FFT. Any pointers on that?
This part is polynomial mod polynomial and it can be computed by polynomial division.
When will the rating be updated??