Round 4 will be held on 31st March 1430 IST.

Round 3 will be held on 30th March 1430 IST. If there are conflicts with your schedule, Kindly inform organizers or ankurdua15 well in time.

We apologize for the mistakes in statements of Round 2 (Div 1/ Div 2). We missed things because of blind spots in problem statements which can be easily caught by fresh eyes.

Note: There will be SYSTEM TESTS.

Div 2/3 Editorial

Problems were not too hard, ask your seniors from pre-final or final year.

Div 1 Editorial

A. Count Sentences

There is a difference between concatenating strings and concatenating words. Consider words as "a","b","ab". Sentences are "ab a b" or "a b ab". String concatencation will result in only "abab" which is logical error.

Use multinomial theorem to calculate distinct sentences.

B. Hard Modular Function

Finding a cycle in linked list is a very well known problem. Thus we can reduce the given problem into this idea. How? Consider when we are dealing with linked list.

C. Exponential Roots

There can be many possible answers but simplest can be found by A₁ = A₂ = ... = A_n - 1 = 1 and then A₀ can be found by using searching technique called meet-in-the-middle and baby-step giant-step steps.

Time complexity: .

D. Subarrays Frequency

For each element evaluate whether . Then convert the array into a binary array where each element is 0 or 1. Find prefix sum array S[0... n] of the resulting array where S₀ = 0 and . Now we can consider a polynomial p(x) out of this array where

For example, in sample test case we can get binary array as0 1 0 1. Taking prefix sum we get array S as 0 0 1 1 2(Note first element 0). We get polynomial as: p(x) = 2 + 2x + x². Consider another polynomial: q(x) = p(x^- 1) = 2 + 2x^- 1 + x^- 2.

Now finding B_i is easy as we can find coefficient of xⁱ in p(x)q(x). Handle the case B₀ separately. Polynomial can be multiplied fast using FFT.

Time complexity:

E. A Very Easy Problem

First consider a slightly simpler problem, given an array A, find the maximum value of in the range where l ≤ i ≤ r. This problem can be solved by augmenting a persistent 0-1 trie such that each node contains the index of the largest element which passes through that node. Now to answer a query on a given range l... r apply the standard algorithm of xor maximization on trie with version after inserting first r numbers but also keeping in mind that you can enter a node only if the largest index which passes through that node is at least l. Now for query on paths in tree use heavy-light decomposition and for query on subtree use euler tour array. Both of these can be done by performing the euler tour in a special way. For more details refer to This.

F. Maximize The Sum

Analyze the given function, you will realize that the answer will be maximum when you take all the numbers in increasing order. But you also have to minimize the number of elements chosen. Now assume that you choose say k numbers from the array, for maximizing the given function, these should be the highest k numbers of the array(i.e these should be suffix of size k if the given array is sorted in increasing order). It is easy to see that the value of the functions is non decreasing with increasing k so apply binary search on k and find its minimum value.

Time complexity: .

Round 2 will start at 18.45 IST today (11th March 2019). There will be 3 separate divisions.

Kindly participate in the respective division in order to be eligible for prizes.

Problems will be sorted by difficulty in Div 3 and Div 2 only. Div 1 problems are not sorted by difficulty.

Contest Link

Every participant must require to fill up this form before giving Round 2 of Code Marathon 5.0

https://docs.google.com/forms/d/e/1FAIpQLSei_7WBkYJD8rsv_zHKJkOTeC9sEGt14P0gqzxsLThlwGIWEQ/viewform

1. "Ask a Question" Button

Whenever you feel that any problem needs some explanation, you can use the "Ask a question" button as highlighted by oval labeled 1 in the picture. Please don't ask us anything related to Test Case, this type of this queries will be ignored.

2. Announcements

If there is a need for explanation in a question, then you will be notified by announcements. Announcements are first visible as browser popups and then on Dashboard as shown in the image in the box labeled 2.

Before solving a problem please head over to the dashboard to see any announcements related to it.

1. You need to register for the round before entering.
2. Make sure you update your name and institute (" IIT(ISM) DHANBAD " only and none other variant) on your profile.
3. You need to participate in all rounds in order to be eligible for prizes(even a wrong submission on any problem is considered participation).
4. Plagiarism is a big NO-NO.
5. Prizes will be available only to students participating in their "respective" divisions:

• Div 1 (3rd year/ Final year B.Tech. UG students / PG students / Alumni)
• Div 2 (2nd year B.Tech.)
• Div 3 (1st year B.Tech.)

Hello Everyone!

Code Marathon 5.0 (Round 1) will be held this Tuesday from 21:00 to 00::00 IST. There will be three separate divisions 3, 2 and 1 for 1st years, 2nd years and rest, respectively.

Problems were prepared by dam0n, madhur4127 and me(ankurdua15). As the round authors, we would like to thank MikeMirzayanov for the incredible Codeforces and Polygon platforms.

Each of divisions 1 and 2 will have 6 tasks and division 3 will have 5 tasks, and 3 hours to solve them. Scoring will be ACM ICPC style. We wish you the greenest verdicts and hope that you’ll enjoy the tasks. You will meet a very interesting character in this round so make sure that you do not miss it.

Good luck!

UPD: Dummy Contest "Try Codeforces" has been added to get familiarity with the contest environment.