Hi Codeforces,
ICPC Kanpur 2023 Regionals Round will happen this Saturday on CodeDrills.
Live commentary: We will be live on codedrills youtube channel. We will start once the contest starts.
- Contest Link — https://icpc.codedrills.io/contests/icpc-kanpur-2023-regional-round
- Ranklist — https://icpc.codedrills.io/contests/icpc-kanpur-2023-regional-round/scoreboard
- Date & Time — 23 Dec 2023, Saturday, 10:00 IST
- Duration — 5 Hours
- There will be 1 to 20 problems to solve
- Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)
- The questions may not be sorted by difficulty
P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.
The first person to correctly predict the team with the first AC of the contest will get a shoutout during the stream.
Team SkillIssue from IIT Delhi.
Team Buriburizaemon from IIT Roorkee.
Team FacelessMan3.0 IIT Kanpur
Team "lite lo" from BITS Pilani!
This was the closest prediction. "Lite lo" got second AC.
In a regional competition, if two teams from the same institute and same region secure slots for Asia West, do both teams qualify, or does only the top one go forward?
Are there total 20 problems ? Like really ?
I am interested to know how much BCCI and the Illuminati pay the codedrills problemsetting team to push their cricket propaganda through problem statements and corrupt the minds of innocent cp'ers.
This one is so weird.
Any Online Mirror for the contest?
Is the editorial available ?
Does anyone know about the qualifying criteria for Asia-West?
It should be made clear before the regionals but it never is...
Asia Pacific has listed down rules, and pre-covid Asia West was used to clarify it before regionals.
I agree, but unfortunately, I have no say in this matter. I will pass on the feedback tho.
If only we had $$$0$$$-based indexing for $$$V_i$$$ in this... (´。＿。｀)
Is there any discussion or editorial?
We do not have written editorials, but some of the problems and solutions were discussed in the stream.
If you want soln of specific problem, you can ask about them. Someone from the panel might share their solutions here.
cc binary_bae
Generalized Collatz Conjecture this one and also wanted to know whether it's possible to solve Mod Messages in better than O($$$qlog^{2}nlog(a_{i}max)$$$) without HLD.
The intended time complexity of Mod Messages is $$$O(q*log(n)*log(max a_i))$$$
Let's do it offline. The problem reduces to solving 2q queries of form -
Find the node with maximum (or minimum) height and value <= X, on the path from U to V. Either U is the ancestor of V, or V is the ancestor of U.
For this part, your soln might be O(log^2N), but it is possible to do it in O(logN).
If we run dfs and put values of all ancestors of U in a segment tree (and remove them when we exit subtree of U), then we can binary search on this segment tree to find the required maximum (or minimum) height. This part is similar to last year's Knockout Miracles
The last part of binary searching on this segment tree can be done in O(logN) instead of O(log^2N). min_left and max_right of atcoder segment tree does this.
My implementation
thanks, nice problem and solution.
Any editorial for Generalized Collatz Conjecture
I will ask the author to publish it.
aryanc403 can you please share the solution for problem I:Swirly Sort?
K=1Slope Trick $$$O(N*logN)$$$K=NsolveK=1forNpossible cyclic permutations $$$O(N*N*logN)$$$K=evenanswer is0K=oddand no of inversions are even, answer is0K=oddand all values are distinct and no of inversions are odd, answer isminimum absolute difference between given nosSubmission
K=1(andK=N) is a classical problem.K=odd, notice that the parity of no of inversions does not change with each operation. So you will have to make 2 nos equal, if no of inversions are odd and all nos are distinct.1 2 3 4 ... K-1 Kto3 2 4 ... K-1 K 1(chose first K+1 index except 2 and cyclic shift)3 2 4 ... K-1 K 1to3 1 2 4 .... K-1 K(chose first K+1 index except 3 and cyclic shift)In short, we can chose three index, move them to front, then do a cyclic shift on the first 3 index, and then move them back to their correct position. Using operations like this we change reach any permutation when
K=even(and the same parity permutations whenK=odd).aryanc403 can you please share the solution for problem Slothful Secretary
Click 1
Click 2
Submission
please set contests keeping in mind that you are setting Indian icpc regionals, not an entire ucup prime contest by yourself.
How to get the editorials of kanpur regionals?