Hello, Codeforces ( ^_^)/
Warm and friendly greetings from FooBar (Competitive Programming Club), IIIT-Delhi.
We have a variety of coding events hosted under our annual technical Fest — Esya'23 and are glad to extend an invitation for your participation.
The details for the events are as follows:
- ProTrio [Registration Link]:
- ICPC-style coding contest
- Eligibility: College Students | Team Size: 1-3 members (same college)
- Stages: preliminary (online) and final round (on-site)
- Prizes: worth ₹40,000
- ProCon Junior [Registration Link]:
- IOI-style coding contest
- Eligibility: High School Students | Team Size: Individual
- Stages: preliminary (online) and final round (on-site)
- Prizes: Multiple Bonus Points for IIIT-D admissions (each point ≡ 1 percentile jump in the JEE Main Score)
- ProSort Euler [Registration Link]:
- Math-based coding contest
- Eligibility: Open to all | Team Size: 1-2 members
- Stages: one final round (online)
- Prizes: worth ₹25,000
Important Dates:
Registration deadlines:
ProTrio: 18th August 2023, 23:59 IST
ProCon Junior: 19th August 2023, 12:00 IST
ProSort Euler: 24th August 2023, 23:59 IST
Contest timings:
ProTrio
- Preliminary round: 19th August 2023, 20:00 to 22:00 IST (Online)
- Final round: 26th August 2023 (On-Site)
ProCon Junior
- Preliminary round: 19th August 2023, 18:30 to 21:00 IST (Online)
- Final round: 25th August 2023 (On-Site)
ProSort Euler Finals: 25th August 2023 (Online)
Note:
Further details can be found here.
Contest links will be shared with your registered email IDs.
Problems in these events are collectively authored and tested by kunalsrv20, Artemistic, shiv_codegen, deepcpp, BlackPanther112358, haajihaa2508, ojus_single and me.
Good luck, and hope you enjoy the contests! (。◕‿◕。)
Updates:
- Preliminary rounds for ProTrio and ProCon Jr. will be held on Codedrills. Contest links will be shared on the registered email addresses. Late registration requests will be difficult to deal with so please make sure you've registered on Unstop before the due date.
- ProTrio-Prelims-Contest-Link & ProCon-Jr-Contest-Link both contests are public.
- ProTrio-Prelims-Editorial
ProTrio Prize Distribution for the Preliminary round:
Rank | Team Name | University | Prize Distribution |
---|---|---|---|
1 | skillIssu | IIT Delhi | Rs. 2500/- |
2 | 728752-UC6313NG | IIIT Hyderabad | Rs. 1500/- |
3 | fightFight | IIIT Hyderabad | Rs. 1500/- |
4 | 728752-UZP479L8 | IIT Delhi | Rs. 1000/- |
5 | 728752-URN708B7 | IIT BHU | Rs. 1000/- |
- Top 51 teams have been invited on-site for the final round of ProTrio, where the top 5 teams will receive cash prizes, and the next 5 teams will receive goodies. (Invite emails have been sent)
Auto comment: topic has been updated by mohit_jx64 (previous revision, new revision, compare).
Saying as a setter and a tester, you will enjoy the contest └(・。・)┘
why is there discrimination against droppers in procon junior? downvoted every one of u
As a setter and tester, I'm definitely sure that you'll AKA the contest. :))
As a setter, the problemsets were fun to work on and I'm sure you will enjoy the events :) Good luck!
As somebody who has both participated and organised Prosorts and other events at Foobar, I can say that you should definitely give it a try.
As a setter and tester, it is highly likely that you will enjoy the Bugaboos :)
mohit_jx64 orz!
mohit_jx64 orz!
mohit_jx64 orz!
mohit_jx64 orz!
mohit_jx64 orz!
mohit_jx64 orz!
mohit_jx64 orz!
ProSort Euler doesn't allow students from different colleges?
ProSort Euler does not have any such constraints. It is open to all.
On Unstop it's not allowing to do so :(
Fixed, should work now.
I'm not sure if I'm doing something wrong but it still says that we should be from same organization.
Hey! Will the prelims be on codeforces? Also, can you provide us with the old archives?
ProTrio and ProCon Jr. will most likely be held on Codedrills. I will release an update for Prosort Euler. As for archives here are some:
Procon Jr 2019
Procon Jr 2018
Prosort 2018
Prosort 2017
Prosort Elysium
can I join protrio solo? I don't have friends who know programming (even syntax ... forget about logic)
Yes, you can.
Auto comment: topic has been updated by mohit_jx64 (previous revision, new revision, compare).
Auto comment: topic has been updated by mohit_jx64 (previous revision, new revision, compare).
mohit_jx64 On the coderills page for the protrio contest it says Please make sure you login and verify your team before the contest .. So how to do this step ???
You don't need to do anything. We will be registering your team from our end and you'll receive contest invitation.
okk thanks got it
pardon me if its a dumb question.
i am participating first time in any online team coding contest
can you tell . if there are any rules about how the team should collaborate
No rules, You are free to discuss and search on internet!
Free to discuss *(with your team members only) XD
Auto comment: topic has been updated by mohit_jx64 (previous revision, new revision, compare).
As a setter and tester, you will solve all problems in first try :)
How to find the sizes of connected components in xor 3?
click
The concept is that of traversing in inverse graph. Here is a cf blog explaining this trick. The basic idea is that you maintain a global array of unvisited vertices, and then to traverse you start with an unvisited node and try to move to other unvisited vertices from the current vertex. If you do so, you encounter non-edges only O(m) times.
Common nor W — Traversing the complement graph in linear/near-linear time in multiple ways
can anyone tell the logic for Typewriter Game ..
Google "Optimal Cache Replacement Policy"
Yes, that was the main intuition of the greedy.
but will the time limit not be O(n*k) in that case also
Maintain your cache (aka keyboard in problem's words) as a set of pairs $$$(\text{next occurrence of value}, \text{value})$$$, you need to make $$$O(1)$$$ changes to this set every step. Submission Link
Ya now i got it thanks it was a nice problem
The greedy idea is to keep filling up your 'cache' with characters until you hit size $$$k$$$. Now when you need to remove something from your cache you remove the character who's next occurrence is the furthest away from your current position.
You can pre-process the next occurrence of every character in $$$O(n)$$$, and you can maintain the current state of the cache in a set, say pair
{next_occurrence, a[i]}
. Simulating the entire sequence is now $$$O(nlog(k))$$$.How many team will be selected for the onsite round?
Good question
It will be revealed latest by tomorrow. You will get a confirmation mail for the same.
Updated in the blog
We cheesed typewriter with an unintended solution. I wrote a greedy which always chooses to replace the least frequent character. My teammate wrote a greedy which always chooses the furthest character. Both of these individually give WA. But taking the min of the answers produced by both greeds passed
Taking min frequency will give you WA. We have a test case for that. The intended solution is to take the farthest one.
Yaa I wrote the min one and get wrong answer at testcase 10
it is indeed the optimal solution
Farthest character should work. Typical OS page fault minimisation algorithm.
What were the intended solutions for A and second part of C? I have a feeling mine were different.
For A, I maintained a frequency table (stored as an
std::map<int, int>
) for each paranthesis depth. When opening a parenthesis of depth $$$d$$$ just add its color to the $$$d$$$-th frequency table.When closing a parenthesis of depth $$$d$$$,
By using small-to-large merging you can do merges in $$$O(n \log^2 n)$$$.
For C, I just spammed FWHT thrice. Was the intended solution to use that there are at most $$$\sqrt n$$$ distinct values?
A was intended to be solved using small-to-large merging, by constructing a tree from the parentheses. Although A could also be solved by mo's algorithm in $$$O(n \sqrt n)$$$.
And yes for C the intended solution was to use $$$\sqrt n$$$ distinct values, so the final complexity would be $$$O(n \sqrt n)$$$. I'm not familiar with FWHT though...
And here I was trying to use recursion, when will you upload editorial?
Will post it soon, most probably in the comment section of this blog.
A can be done using segment tree also. Iterate over the indices of the string, maintain the first index after current index for every color. Then the problem reduces down to range sum, index update queries for a total of O(nlogn) time.
I solved with MO's :)
Auto comment: topic has been updated by mohit_jx64 (previous revision, new revision, compare).
will there be no prizes for the offlne onsite round of pro trio??
I'm not sure what prizes you are talking about! But it's mentioned in the blog that top 5 teams in the finals will receive cash prize and next 5 will receive goodies. The prizes for preliminary round and final round are separate.
But among top 50, only 11 team are from delhi.
aren't 11 teams too less. considering its IIIT delhi and there were 250+ teams registered.
( or I don't know maybe you guys have travel arrangement for outside delhi team, in that case my bad)
Can you check why our solution was giving runtime error on test case 4.
Submission link: https://codedrills.io/submissions/749386
Hi Quick-One, thanks for pointing this out. We checked your submission and found there was a slight error with the test case due to which Python and Java codes can give runtime error on 4th testcase. We have rectified the same and re-judged all the submissions for the Problem : GCD Faceoff. Updated standings are also now visible here.
There were 2 teams who faced this issue including you. I want to sincerely apologize for any inconvenience and frustration this may have caused you. To accommodate these changes in the standings, Top 51 teams will be now invited on-site for the final round of ProTrio, where the top 5 teams will receive cash prizes, and the next 5 teams will receive goodies.
If you still have any concerns or questions, please do not hesitate to reach out to us. Thank you for your understanding, and we appreciate your support.
Editorial plzz Mohit bhaya
ProTrio Preliminary Contest Editorial
Problem A Colorful Parenthesis
Author: kunalsrv20
Well, the first observation you can note is, you can break a balanced parenthesis in the form of a tree, for example:
We can assume the parenthesis at each level as node. Now, let's assign the colors to each node, the color of root node will be the color of first bracket, the color of node 2 will be the color of first bracket of it. Similarly, the color of each node will be the color of the first bracket of it. Now the problem reduces to finding the number of distinct colors in each subtree of the tree formed and outputting the answer in the asked format. This task can be done by using small-to-large merging. So, the overall complexity will be $$$O(n\log^2(n))$$$.
One can also answer the number of distinct elements within a range using either MO's algorithm (in $$$O(n \sqrt{n})$$$) or using segment tree approach in $$$O(n \log(n))$$$.
Problem B GCD FaceOff
Author: haajihaa2508
The first key observation is Alice can never win since Bob can always make the GCD equal 1 by adding 1 to the array on his turn which leads to a draw.
Analyzing the possible cases when Alice removes an element. Let gcd of the remaining n-1 elements be x with prime factorization of the form $$$a1^{p1}*a2^{p2}....aN^{pN}$$$, where a1..aN are prime numbers and p1..pN are non-negative integers.
Case 1: p1+p2+...pN is even Bob can add the current GCD to maintain the same GCD with an even exponent sum, leading to his victory.
Case 2: p1+p2+...pN is odd (>1) Bob can add something x of the form $$$a1^{(p1-1)}*a2^{p2}....aN^{pN}$$$. So the new gcd will be now x which leads to Bob victory since p1+p2+..pN — 1 will be even.
Case 3: p1+p2+...pN is odd (=1) ie. x is a prime number Here Bob cannot force a win. Therefore, he will aim for a draw by adding 1.
Case 4: x = 1 Bob cannot force a win in this case and can only aim for a draw.
Analyzing the four cases, it becomes evident that Alice's optimal strategy involves removing an element from the array, resulting in a GCD that is either a prime number (Case 3) or equal to 1 (Case 4). This specific approach ensures that the game concludes in a draw. Any other outcome would invariably lead to Alice's defeat.
So to determine whether removing any element from the original array enables us to achieve a GCD that is either prime or 1 efficiently, we can employ a two-step approach:
Prefix and Suffix GCD Arrays: Firstly, we create both prefix and suffix GCD arrays. This will help us to compute the GCD of the remaining elements efficiently after each element removal.
With the computed GCD value at hand, we need to check whether it is a prime number or equals 1. To accomplish this, we utilize a sieve algorithm to precompute prime numbers.
So the total time complexity will be $$$O(A\log(\log(A)))$$$ where A is the largest element possible in array ie 10^6 for sieve algorithm and rest all computations can be done in $$$O(N\log(A))$$$ per test case.
Problem C XOR 3
Author: mohit_jx64
First, we need to get the connected components of the graph. This is straightforward when edges are provided, we can simply run a DFS to get component sizes. In the case of non-edges, we have what is called an inverse graph. The basic idea is that you maintain a global array of unvisited vertices, and then to traverse you start with an unvisited node and try to move to other unvisited vertices from the current vertex. If you do so, you encounter non-edges only O(m) times. Here is a detailed blog explaining this process: cf blog.
Once we have the sizes of the connected components, we can reach the optimal value either by removing none, one, two, or three components. A thing to note is that there will exist an optimal answer where we never remove two components of the same size as that has the same effect as removing no component. Similarly, we will never have three components of the same size, as removing them has the same effect as removing just one component of that size. Therefore one of the optimal solutions will remove components with distinct sizes.
The sum of the sizes of connected components is n. Therefore the number of distinct sizes is $$$O(\sqrt{n})$$$. We can brute force the components that can be removed for each case (no removal, one component removal, ..., three component removal). For the worst case scenario of removal of three components, the brute force iteration will take $$$O(n*\sqrt{n})$$$.
To get the xor of the component after the removal of an element, we can simply xor the xor-score with the component size we need to remove.
Problem D A Grid is a Grid is a Grid
Author: ojus_single
It can be shown using mathematical induction that there will always be a path covering all N*N cells of the grid for an NxN grid when N is even. (Proof Sketch: Create a path that always ends at i = N or j = N for N = 2, then extend that path for N = N + 2)
For an NxN grid when N is odd, let (i, j) be the coordinates of the source cell. It can similarly be shown that there will always be a path covering all cells when i + j is even, and a path covering N * N — 1 cells when i + j is odd.
We can prove that no path covering all cells exists for a source cell with odd N and odd i + j, by painting all cells with even i + j Black(B) and all others White(W). Note that we can only go from B to W and from W to B (cannot go B to B or W to W). So all paths look like WBWBW... Now there are (N*N+1)/2 B cells and (N*N-1)/2 W cells. Since we have more B cells than W cells, there can't be a path like WBWBW... that covers moth B cells that W cells, hence there can't be a path covering N*N cells.
Problem E Typewriter Game
Author: shiv_codegen
For the first k distinct keys, we will add it directly to our typewriter. Now when the next distinct key arrives and we have already marked all the k keys available on the typewriter, it is always optimal to remove the key from our typewriter that will not occur for the longest time in our array from the current position. This is in accordance with optimal cache replacement policy.
We can get the key that will not occur for the longest time using a set sorted based on the next occurence of the character in $$$O(\log(k))$$$, therefore this problem can be solved in $$$O(n*\log(k))$$$.
Any editorial for Onsite Round Problems?