Greetings Codeforces Community!
I would like to invite you all to participate in the Exun 2019 Programming Prelims. The contest will be 2.5 hours long and will contain 6 problems. All the problems will be from IOI Syllabus.
The contest is rated for everyone.
The problems are prepared by Tarrus, AwakeAnay and me. I would also like to thank taran_1407, arjunarul and the rest of the CodeChef team for helping with testing and reviewing the problems.
Contest Details:-
- Start Date and Time : 11th October 2019 (19:30 hrs) to 11th October 2019 (22:00 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
- Registration: You just need to have a CodeChef handle to participate. All those who are interested and do not have a CodeChef handle are requested to register in order to participate.
- Registration for Onsite Finals : All Indian School Students are eligible for the onsite finals at Delhi Public School R.K. Puram, you can register here and then fill this form.
- Prizes: Top 10 performers in the Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies.Other than that, five random participants and the first user to solve each problem will also get CodeChef laddus.
- The ranklist will be IOI style.
Good Luck!
Hope you enjoy solving the problems!
Looking forward to the contest! Thank you for taking this initiative at such a young age, a true living legend!
Auto comment: topic has been updated by SleepyShashwat (previous revision, new revision, compare).
How to solve the second last problem Anay and Polynomial?
The answer is the sum of all $$$2^n$$$ possible $$$p(x_1,x_2,x_3,....,x_n)$$$ where $$$x_i$$$ is either 1 or -1.It can be computed by counting the number of times k+a comes and the multiplying by its value. This value is divided by $$$2^n$$$.
Find the value of $$$P$$$ for all tuples $$$(x_1, ... , x_n)$$$ such that $$$x_i = 1, -1$$$. If you add all of them then the only term that will remain are the coefficients with even power for all $$$x_i$$$'s and each is counted $$$2^n$$$ times.
Here's my solution with proof:
Let's first solve the problem for $$$n = 1$$$. We can divide the terms of the polynomial in $$$2$$$ categories, terms with even powers and terms with odd powers. We observe that $$$P(1)$$$ is the sum of all coefficients of terms of the polynomial and $$$P(-1)$$$ is the sum of coefficients of terms with even powers subtracted by the sum of coefficients of terms with odd powers. Thus the required sum will be:
Now let's try to generalise this for any $$$n$$$. Say we divide the terms of the polynomial in $$$2^n$$$ categories according to the parities of the powers of the $$$n$$$ variables.
For a particular value of $$$P(x_1,x_2,\ldots,x_n)$$$ where $$$x_i \in {1,-1}$$$, we see that terms of a particular category are either added or subtracted depending on whether the number of variables having odd power in the term and having value $$$= -1$$$ are even or odd respectively.
Consider the sum $$$S$$$ of all $$$2^n$$$ values of $$$P(x_1,x_2,\ldots,x_n)$$$ where $$$x_i \in {1,-1}$$$. Observe that the terms with even powers in all the variables will always be added. Thus, they will appear $$$2^n$$$ times. For terms of any other category, say a category with $$$i > 0$$$ variables having odd powers, the terms will be added if $$$j$$$ of these $$$i$$$ terms have value $$$-1$$$ where $$$j$$$ is a even number. Thus, the terms will be added $$$A$$$ times where,
And the terms will be subtracted $B$ times where,
But we know
This has various proofs.
Thus, these terms will be added and subtracted equal number of times and the final sum $S$ will just be equal to $$$2^n$$$ times the sum of coefficients of all terms with even powers in all the variables. Our required sum will then be $$$\frac{S}{2^n}$$$.
We can find $$$S$$$ in $$$O(n \log{m})$$$ by observing that the value $$$(k + n - 2i)^{m}$$$ appears $$${n}\choose{i}$$$ times.
Code
Btw, this was my first time setting a problem, so I hope you enjoyed it.
Can you explain why $$$A = B$$$?
"This has various proofs."
$$$A, B$$$ are number of even and odd elements subsets of $$$[1, 2, 3, .. n]$$$.
Let $$$S$$$ be number of subsets of $$$[1, 2, .. n - 1]$$$ respectively.
Consider $$$A$$$ : if the subset contains $$$n$$$ then we map the subset to an odd element subset of $$$[1, 2,.. n - 1]$$$ containing all its elements but $$$n$$$, otherwise we map it to itself. Thus, $$$A = S$$$.
Similarly, consider B : if the subset contains $$$n$$$ then we map the subset to an even element subset of $$$[1, 2,.. n - 1]$$$ containing all its elements but $$$n$$$, otherwise we map it to itself. Thus, $$$B = S$$$.
Therefore, $$$A = S = B$$$
I just understood your solution and I really enjoyed and loved your solution. I initially thought that it would be too advanced but after going through it, I managed to understand the entire solution !
The main idea is to get the $$$P(1)$$$ and $$$P(-1)$$$ and generalise it to a tuple.
Unfortunately, I couldn't solve some of the problems during the contest but came up with the solution afterwards. How do I submit the solutions now and upsolve them ? I can't find the problems in the Problem Section.
UPDATE — The problems have now been added to the Practice Section and I can make submissions to the problems now :)
Also, I liked the questions and am open to discussing them. Here are my solutions to the contest
$$$A$$$ — Observation and Mathematics. How to solve $$$A$$$ if the uniqueness constraint was removed ?
$$$B$$$ — Observation and Construction — While this was easy, it was not obvious on sight. Had a good time coming up with this.
$$$C$$$ — Segment Trees and Binary Search on Prefix Sum — I kept an auxiliary array where $$$A_i = 1$$$, if the $$$i$$$ th element is not a multiple of the $$$(i — 1)$$$th element. I found this easier than $$$D$$$ , even though I see $$$D$$$ had far more successful submissions.
$$$D$$$ — DFS
I look forward to discussing $$$E$$$ and $$$F$$$!
During contest, I wrote an overkill solution for C using lazy propagation but after the contest, I realized by looking at other people submission's that there is an easier solution wherein you can simply maintain the starting point of every range of elements using a set. Code
Ah so just insert the beginning of all segments into a set and do binary search on every query ? Interesting idea ! Fantastic !
Yes. For an update at the ith index, there are a few cases, firstly check to see if there is a change between the ith and the (i+1)st index.
If a[i] used to divide a[i+1] earlier, but now it does not, a new segment starts at index (i+1). So, insert (i+1) into the set.
If a[i] did not divide a[i+1] earlier, but now it does, the segment for (i+1) must be merged with the previous segment by just simply erasing (i+1) from the set.
Similar cases must be handled for a[i] and a[i-1].
And for a query simply output the largest index in the set <= i.
BTW, your comment above is showing "Unable to parse markup [type=CF_MATHJAX]"
Regarding your solution for Problem C: The complexity of your solution is $$$O((lg N)^2)$$$ per query since you perform a binary search and also a prefix query at every step using the segment tree. There exists a very neat trick to optimize the complexity of this thing to $$$O(lg N)$$$ per query.
The idea is to perform a dfs on the segment tree. You start at the root node of the segment tree. If
(left == right), you have found the index that we needed as the answer. Otherwise, consider the value at the left child (the sum of the elements in the left half). If this is <= sum (the required value), move towards the left child. Otherwise, move towards the right child and reduce sum by the value by the value at the left child node. Modified CodeOh wow !
Thanks for taking the time to read my code and provide a new idea to optimise it by going through the Segment Tree intelligently.
When will the rating be updated for this contest? After long challenge ends or before it?
"The ratings for this contest will be calculated once October Long Challenge gets over."
-From the announcement section.
Don't forget to update scoreboard before rating recalculation. Currently, it doesn't count few AC submissions sent in last seconds and processed after contest ends.
Seriously!!
Some proof of your claim that scoreboard is not updated please? Some usernames of affected people?
Me, obviously. Username: gultai4uk_r
Last AC solution has been submitted 10 seconds before contest ends.
Scoreboard correctly shows my points for each problem but the sum is wrong (it doesn't count my last submission).
It also affected spellstaker with last AC submitted 12 seconds before contest ends and singhanuj123 with last AC submitted 7 seconds before contest ends.
Create a blog on cc discuss tagging @admin and @vijju123 asking for updatation of the rank list along with these screenshots. Nobody will take cognizance from a comment here. In case you don't create blog nobody will update rank list and ratings will be calculated without these corrections.
The best contest that I have taken part in lately!
Any idea as to why are the problems showing up as partially accepted in the practice section, while my submissions showed up as 100 points.
Screenshot:
When will the ratings be updated?