Now that the contest has ended, how many did your team do?
Does anybody have a link where we can try to up solve the problems.
Also, any hints for D and E.
Now that the contest has ended, how many did your team do?
Does anybody have a link where we can try to up solve the problems.
Also, any hints for D and E.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
This was one of the worst prelims ever.
At least there was no cheating in our college..... Considering that I don't think this was worst prelims......
For E, try to think of the strategy to minimise operation 2 for a given labeled tree. You will realise that all the edges labeled upto c must be part of straight line. After that its just a bit of combinatorics. Hope that helps!
That first part was easy for me to realise that only a straight line will matter. just bit of combinatorics is what i am missing
D:
Divide indices by
for example the identity permutation has $$$[1,n/2]$$$ in $$$A$$$ and $$$[n/2+1,n] $$$ in $$$C$$$.
If you swap something in $$$A$$$ and something in $$$C$$$, they move to $$$D$$$ and $$$B$$$ respectively. This also holds vice versa. As $$$|A|=|C|=n/2$$$ and $$$|B|=|D|=0$$$ hold for identity, $$$|A|=|C|$$$ and $$$|B|=|D|$$$ hold for all p.
So perform operation on $$$A+C$$$ and on $$$B+D$$$ (or only one of them if the other is empty)
Is there any trick in solving c??
I won't call this a trick but there is a simple (it took time to get this obviously) observation:
choose a = c, which simplifies the problem:
a ^ c + b ^ c = lcm(a,c) + lcm(b,c) since a == c, a ^ c = 0 and lcm(a,c) = c which gives us:
b ^ c = c + lcm(b,c).
Now find b such that b ^ c = b + c and lcm(b,c) = b.
For this i just left shifted all the bits of c by msb(c) + 1 i.e., (c << (msb + 1))
observation: c is 1e7 so the maximum bits it will have are about 23 or so (took log2(c)) and a,b can be atmost 1e17 which can have atmost 56 bits. So we can shift all the bits of c to the left easily.
Our final answer: (c,c << (msb(c) + 1)).
Shit we got stuck because of the test cases, Basically, we were trying to fix a = 1 and then find a possible value for b, which wasted a lot of time
Can't blame you, the intuition hit randomly.
How shifting will ensure correct answer
Suppose
a = candb = c << ksuch thatb & c = 0, i.e.,bandchave no common bits. Now,a ^ c = 0andb ^ c = b + c, andlcm(a, c) = c,lcm(b, c) = b(asb = c * pow(2, k)). The sum on both sides comes out to beb + c.Example: c: 7 (000111).
Choose a = 7 so a ^ c = 0.
Choose b = c << (msb + 1) = 56 (111000)
a ^ c + b ^ c = 0 + 63 lcm(a,c) + lcm(b,c) = 7 + 56 = 63.
Left shift by 1 is basically multiply by 2 so b will always be a multiple of c
So you have to make lcm(b,c) = b and a^c = b
what we can do is count the no of bits(l) in c and make a = (c<<l) and b = (c<<l)+c then you will be able to prove that this the answer
i have no way to verify this , so if anyone could find corner case to this code. E is pretty easy maths, D was little tough to verify but still not sure by 100%. if its correct.
statement if anyone needed: statement link
but this are the codes for D and E
E : https://ideone.com/8ryr8P
D : https://ideone.com/4tQrdu
Let $$$n=2m$$$. Divide the elements into two sets: Small $$$S = {1, 2, \dots, m}$$$ and Large $$$L = {m+1, \dots, n}$$$.
The operation conditions can be reinterpreted using these sets:
Type 1: $$$\max(t_1 \dots t_k) \lt \min(t_{k+1} \dots t_{2k})$$$. This is satisfied if we pick $$$k$$$ elements from $$$S$$$ appearing before $$$k$$$ elements from $$$L$$$.
Type 2: $$$\min(t_1 \dots t_k) \gt \max(t_{k+1} \dots t_{2k})$$$. This is satisfied if we pick $$$k$$$ elements from $$$L$$$ appearing before $$$k$$$ elements from $$$S$$$.
Claim: The minimum number of operations is always 1 or 2.
Case 1: 1 Operation, If all elements of $$$S$$$ appear before all elements of $$$L$$$ in $$$p$$$, we can remove the entire permutation in one Type 1 operation.If all elements of $$$L$$$ appear before all elements of $$$S$$$ in $$$p$$$, we can remove it all in one Type 2 operation.
Case 2: 2 Operations,If elements of $$$S$$$ and $$$L$$$ are interleaved, we need 2 operations.
Type 1: Find a split point $$$i$$$ that maximizes $$$k = \min(\text{count}(S \text{ in } p[1\dots i]), \text{count}(L \text{ in } p[i+1\dots n]))$$$. Let $$$A$$$ be the $$$k$$$ elements of $$$S$$$ from the prefix, and $$$B$$$ be the $$$k$$$ elements of $$$L$$$ from the suffix. Remove $$$A \cup B$$$.
Type 2: The remaining elements are $$$L$$$ values from the prefix and $$$S$$$ values from the suffix. By definition, all these remaining $$$L$$$ values appear before all remaining $$$S$$$ values, allowing them to be removed in a single Type 2 operation.
E: A key insight is that we are forced to increment $$$x$$$ from $$$k$$$ to $$$k+1$$$ if and only if the edges labeled $$$1, \dots, k$$$ form a chain starting from the root, and are ordered specifically along this chain to block traversal at each step.Let $$$N(k)$$$ be the number of permutations where the cost is at least $$$k$$$ (i.e., we are forced to increment $$$x$$$ at least $$$k$$$ times).
The number of permutations with exact cost $$$c$$$ is $$$N(c) - N(c+1)$$$.For a fixed chain of $$$k$$$ edges starting from the root, there are $$$2^{k-1}$$$ ways to assign the labels $$${1, \dots, k}$$$ to these edges such that they force $$$k$$$ increments.To find the number of such chains, observe that for a fixed node $$$v$$$, the unique path from the root to $$$v$$$ contains $$$dep[v]$$$ edges. Any subset of $$$k$$$ edges from this path that includes the edge $$$e=(parent(v), v)$$$ forms a valid chain ending at $$$v$$$.
The number of such chains ending specifically at $$$v$$$ is $$$\binom{dep[v]-1}{k-1}$$$.Summing over all nodes $$$v \neq 1$$$ gives $$$W_k$$$, the total number of ways to choose a chain of length $$$k$$$ starting from the root:$$$W_k = \sum_{v=2}^n \binom{dep[v]-1}{k-1}$$$The total number of such permutations $$$N(k)$$$ is the product of choosing the chain ($$$W_k$$$), assigning valid labels $$$1 \dots k$$$ to it ($$$2^{k-1}$$$), and assigning the remaining $$$n-1-k$$$ labels arbitrarily:
$$$N(k) = W_k \times 2^{k-1} \times (n-1-k)! \pmod{998244353}$$$
Your solution for E is not correct.
The correct expression is $$$N(k) = W_k \cdot 2^{k - 1} \cdot (n -1 - k)!$$$, if I understood your definitions correctly.
I'll post the editorial in a few hours.
When the standings will be made public ?
yeah i guess you are correct!! corrected it !!
btw do you solution for F
Problems like A should not be in an ICPC round and D shouldn’t be positioned at D, especially when you are not even letting the problem count or standings public. Expected much better but this is just ridiculous that newbies have better hopes of making it to regionals. Maybe it’s just a rant, maybe it isn’t. I will let this one be here.
wait standings was not public ? this is very unprofessional for cp contest.
also what is A lol , just remove it instead !!
btw you should not complain about relative ordering, because in past there was no fixed order relative to difficulty !!
“D shouldn’t be positioned at D” can be translated to 4th easiest problem shouldn’t have been such a stupid leakable/guessforces problem but yeah like I said it might just be a personal rant at this point. Although am sure a good chunk of strong teams who suffered would find rationality in what I say.
What does leakable even mean in this context? Also have you ever heard of constructive problems? This sounds like someone ranting for underperforming in the contest and trying to find an excuse for the same.
I agree about problem A, but i found problem D pretty decent, it was quite better than problem C, i found problem C also quite decent, i guess the intuition that if c=1101 then a can be 11010000 and b can be 11011101 was enough....it took me some time to get this construction but i found c,d quite interesting, in all it was a nice contest.....if u ask me :)
Problems like A are only added to boost participation numbers, they have nothing to do with selection. Also, when I tested D, I found it quite interesting, so the problem wasn’t bad, it was a skill issue on your end :)
I disagree with your statement regarding A , there is difference between cakewalk/easy difficulty and tasks like this. you can set a cakewalk difficulty task to boost participation. but current A should not be a task.
As far as I know, seats for the World Finals are allocated using a points system that also takes into account how many people correctly solved atleast one problem in the prelims. That could be why they do this.
DeletedThere was lot of cheating in our college(NIT xxxxxx), i just want the organizers to know about it, and ask our college coach(which is common to all teams) for clg lab recording to remove cheaters. Participants are moving to washroom and cheating and some of them are using gpt in labs too. Our clg coach does not came for evaluation(since its saturday holiday) instead he sends his phds for it and those phds just literally don't care and know the importance of icpc and they didn't stop cheating. I don't think our coach will be interested(or have time for appealing for us) in removing cheaters. So, is there a way to report this incident to organizers ?
Report to Telegram ICPC group admins
I just reported them to admins. Also, i don't think that our clg teams will get plagged since they understands logic from ai or telegram and code it on their own, and since problems till D are only main logic based, coding them is not a big stuff and there is no chance of getting plagged on those small codes.
We did 3 questions.
They have made the contest public so you can upsolve at CC Link
Live Solved A — E.
Checkout my Stream.
https://www.youtube.com/watch?v=a_HwaoPE0Vs&t=6424s
My team did 4, which was great considering this is our first icpc :) also what would be the estimated rating of the problems?
Can anyone give a hint for F? We thought that it was a combinatorics problem. Like swapping elements can lead upto n! different permutations. So to find the number of ways, we could just subtract the permutations which were invalid (for which F(a)=1). But I cannot figure out how to count the number of invalid permutations. Can anyone help, or do we need to think of something different?
First think about how to find minimum number of operations and then which elements matter, after that its just counting and edge cases.
can we report a team if we find their code sus?
Report to Telegram ICPC group admins
Just hate reservation atp.
Teams with lower ranking will get selected because of the 5 Cap.
Anyways cant complain have to be better imagine being in top 150 and getting rejected.
Feeling sad with 100 others :)
Chances for a 1300 ranked team to get selected ? Solved a, b, c. We are the only team from our college...
Same Question, We are Rank 1 from our College, but it Depends on the Value of 'k' which is Set by organizers such as atleast K Problems should be solved by a team to Qualify. Since more than 600+ teams have Solved 4 Questions, the chances are very very less for rank 1300 to get selected
Fun contest!
Personally, really liked the geometric interpretation of D; my teammates' favourite problems are C and E though.
whats the geometric interpretation ? can u brief plz
Consider points $$$(i, p_i)$$$ in 2D. For an operation of type 1, we will have some point $$$(x,y)$$$ such that all points in the left half of the subsequence $$$t$$$ will be below it, to the left of it, and all points in the right half will be above it, to the right.
For the array $$$\left[2,\ 3,\ 6,\ 1,\ 5,\ 4\right]$$$, it looks something like this
We shift the origin to this point. Now in our first operation we clear quadrants $$$I$$$ and $$$III$$$ which have (say) $$$a$$$ elements each, and in our second operation we clear quadrants $$$II$$$ and $$$IV$$$ which have (say) $$$b$$$ elements each. Then observe that the number of points to the left of the Y-axis is $$$a+b$$$ and so is the number of points above the X-axis. Also, $$$a+b = n/2$$$.
So the resulting code is:
The same idea is used in this problem: 2122C - Manhattan Pairs
Is there any chance for a team with rank 132 getting selected?
If 5 teams from your college are above you then no chance...
we are top 2 in our clg(top 1 team is not in our region),chennai region and our rank is 860,is there any chances? :(
Very low chance tbh, most teams would fill up the seats before 860.
Then regionals will always be a dream :( as it's my last chance
bhai come to my clg for masters together we will make that happen !!lol
How can we report the cheaters..!
Report to Telegram ICPC group admins
Is the sort by Institution Name working in the published Codechef ranklist ? Couldn't apply that filter.
Use this -> https://indiaicpc.in/ranklist.html to filter by institution
Yeah got it ! Thanks !
the contest was fun however , i hope satyam343 u knew about the rule for solving the just 1 problem ... the first problem was just nothing so the better colleges would suffer from this ... our team managed to solve 4 problems with decent penalty but because of our college we are mostly not qualifying (we are almost 10-15th in our college) . To further elaborate about the 1 qn rule ... anyone who does just one question and is able to sit for prelims just because they are first in their college is dumb
How would better colleges suffer because of 1qn rule? Your team probably would not have been selected even if one question rule wasn't there, as per college max number of teams is fixed.
yes i would say we wouldn't have qual anyways but imagine a team who did 4 .. they are 6-8th in their college or something like that ... they would have gone with the general stuff they would have qual but due to the selection of the first team from each college first many of them wouldn't get that chance
My Team did 3
To everyone who want to report cheating.... https://forms.gle/AXquoXf7atw6TMyE7
in deep guilt for not being able to do D even though it was such an easy problem. Thought of segment tree and stuff but now i realise this was one of the adhocs which validates the statment that "adhocs are provable" .
My final intuition with D: the best case for which ans will be 1 is [1,2,3,4,5,.....n] can be broken into two halves where 1st half has all the values <=n/2 and other half have all the values >n/2 or vice versa
the other cases are basically an upgrade of this case only where some values in first and second halves are swapped
So first we may take all the values>n/2 in the first half and all the values <=n/2 in the second half and next we may take all the values<=n/2 in the first half and all the values>n/2 in the second half.
thank you
We did A-E :D
does anyone know when'll the final results of the teams selected for regionals be published ?
Update from the organizers (Telegram Group): "Plagiarism checks are currently in progress, and we aim to publish the final ranklist by Sunday, 16th November."
Can you please tell what is the status of the final ranklists, if you have any info from the organizers?
Several cheating cases have been identified, and the team is manually reviewing each recording and submission, which is taking time. The next update will be provided on Tuesday.
Thanks for the update..
Any update about result?? Is there any telegram group for update??If there can you send the link??
Can someone tell what was the value of K (i.e the maximum number of teams selected for amritapuri, other than the top 25, from a college) was? Or The maximum teams that can get selected if there is no team under 50 and quite a few from 100 to 300 from the same college?? 18o3
Agreed with the typo in Selection Criteria 2. I believe it should be 5 for Selection Criteria 2 since it was mentioned that 5 teams per college would be allowed, but it is showing 4. Let's hope that this would be rectified soon.
5 is when atleast 5 teams from a college are in top 25 I think
Yes. I wanted to know how many other than top 25 can qualify from a college, as it is mentioned k<=4 and will be decided after the contest?
Previously, communications indicated that 350+ teams would be selected, with a limit of 5 teams per college. However, the current rules now state a total of 320 teams will be accepted, with the 5-team-per-college limit applying only to the top 25.
This sudden adjustment is a bit concerning. What feels particularly concerning is that this new, two-tiered system was never mentioned. If there was always an intention to apply a different, more restrictive limit (e.g., 4 teams) to colleges outside the top 25, that should have been specified from the start.
Our team got a rank < 400 and we are the institute toppers. But our video recording ourselves was corrupted after 1 hour into the contest. I swear we haven't cheated and we still have our voice and screen recording. What should we do?
Do we get the regionals qualified mail to the team members or to the coach only? We got <150 rank, we(students) haven't received the mail. So, incase we were wrongfully flagged, what do we do ?
I think flagged teams already got mail (I know some teams who received mails for not having proper recording or those who didn't run script before starting contest).
Coaches didn't get any mail so far.
So the msg in telegram is not for qualified teams rather for the ppl who got flagged
Which telegram channel are you talking about?? Can you send the link!!