Hello, Codeforces!
The Competitive Programming Club of IIIT Lucknow is happy to invite you to participate in Dream In Code '24 which will be held on Thursday, April 11, 2024 at 20:00 IST (UTC+5.5).
You will have 2 hours to solve 8 problems (one of the problems has 2 subtasks), the round will be held as a Codeforces gym contest and will therefore be unrated.
The problems have been prepared by members of the club, atharv_tiwari, AnikateKoul, akshitnandan, saavrm and Ankit_102.
The prizes for the winners are as follows:
1st place: 5,000 INR
2nd place: 3,000 INR
3rd place: 2,000 INR
(Prizes for international winners will be transferred via crypto)
Thanks to MikeMirzayanov for the great platforms Codeforces and Polygon which allowed us to setup the contest easily.
You can access the contest using this link.
Good luck and have fun!
The Dream in Code series is part of Equinox, the Annual Techno-Cultural fest of IIIT Lucknow. The contest is open for everyone and we would love to see your participation in the contest.
As a setter, the problems are really interesting and I recommend everyone to participate.
Excited>>>
No Prizes?
We were awaiting confirmation from a couple places, hence the delay. The prizes will soon be updated in the blog now
The registration is now live!!
Auto comment: topic has been updated by AlphaGaurav (previous revision, new revision, compare).
Late announcement
Super excited for the contest !
Nice PFP
Will there be editorial or PCD?
Hey! If you have any doubts about the questions, you can message me or any of the writers. We will assist you directly. If you feel a more general discussion would be better, you can comment your idea or doubt under this blog :)
Sure posted my query!
Nice contest,i implemented Matrix Exponentiation for the first time today.
Which problem?
H1
Can anyone explain E and F.
For E, you can maintain two sorted multisets $$$m_1$$$ and $$$m_2$$$: $$$m_1$$$ holds all the current elements of $$$a$$$, and $$$m_2$$$ stores the differences between consecutive elements of $$$m_1$$$. Now to make an update:
For F, you can maintain a 2D DP array where $$$dp_{i, x}$$$ stores the maximum coop value among the first $$$i$$$ groups only at most $$$x$$$ people can be used from group $$$i$$$. To calculate this, let $$$c_{i, x}$$$ be the maximum coop value we can get in the first $$$i$$$ groups if exactly $$$\min(a_{i-1}, x)$$$ people are used from group $$$i$$$. This can be calculated simply: $$$c_{i, x} = \min(P_i, P_{i-1})\times\min(a_{i-1}, x) + dp_{i-1, P_{i-1} - \min(x, P_{i-1})}$$$. Once $$$c$$$ is calculated, $$$dp_{i, x} = \max_{0\leq j\leq x}(c_{i, j})$$$, which can be done efficiently by taking prefix maximums. The answer will just be $$$dp_{n, a_n}$$$.
Thats a clever solution. I was thinking about segment tree or bit..
For F:
The intuition is that you will decide for a group $$$i$$$ that some $$$j$$$ people that will cooperate with some $$$j$$$ people from group $$$i - 1$$$. This will leave maximum $$$count[i - 1] - j$$$ people to cooperate with the $$$i - 2$$$ group if it exists. This should give you an idea of using a 2D array to store at what group you are going to work at are and how many people from that group to choose.
This code does the same. [submission:256149281].
Since the constraint mentions that the total number of people and groups $$$\le 10^5$$$. Therefore looping over all the people in group is possible as the total iterations are $$$n + \sum_i^n count_i$$$. Also we are only considering $$$i$$$ and $$$i - 1$$$ at any iteration. Therefore, we only use $$$dp$$$ with first dimension 2.
At the end of each iteration of the outer loop($$$i$$$) we copy all elements changed(updation of $$$dp[1]$$$) in the inner loop($$$j$$$) to $$$dp[0]$$$.
For A How would we solve it for A[i] ^ A[j] == 1 and we need to find the largest A[i] * A[j]?
Just a alternate problem which I thought of while solving the problem.
just check consecutive numbers where the first number is even
Can you elaborate.
A[i] ^ A[j] won't result in 1 for all even odd pairs right.
Since 15 ^ 16 = 31.
the smaller number should be even, it is always true in that case
Its saying that A[i] ^ A[j] 's first bit should be 1, i.e. any of the odd-even pair will suffice this condition. Reread the question again, its taking & with 1.
I was thinking of a alternate similar problem.
Oh, then A[i]^A[j] can be 1 iff they both have all the same bits except the bit at 0th position, so they must be a n and n^1 pair. You can hash the whole array and search for n^1 for every other number, if it exists.
you can maintain set and iterate form 1 to n , for each index find the (1^a[i]) in set if it exist update the answer
What's the intended solution for problem G?
Can someone tell me why this code gives RTE Problem D : [submission:256406705]