Hello, Codeforces!
NJACK — the Computer Science Club of IIT Patna is excited to invite you to ByteRace 2023 — Codeforces Round 845 (Div. 2) and ByteRace 2023 under Celesta — the annual Techno-Management Fest of IIT Patna.
The contest will take place on Jan/21/2023 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.
Many thanks to all the people who made this round possible:
- The problems were authored and prepared by me, quantau, mayankfrost, ShivanshJ, Crocuta and AwakeAnay.
- irkstepanov and KAN for coordinating the round!
- jenishmonpara, 100gods and V_S_M for their guidance throughout the process.
- VIP testers: YashPant and Newtech66 <3
- Shoutout to AwakeAnay for doing absolutely nothing.
- dorijanlendvaj, Golovanov399, nor, defnotmee and ilya151098 for testing and providing detailed feedback that improved the quality and balance of the round significantly.
- Our lord and saviour MikeMirzayanov for great systems Codeforces and Polygon.
You will have 2 hours to solve 6 problems.
The scoring distribution will be updated later.
UPD: Scoring distribution: $$$500-1000-1500-2000-2250-2750$$$
UPD: Editorial
UPD: Congratulations to the winners!
Official winners:
Unofficial winners:
First solves:
A: noimi at 00:00
B: neal at 00:02
C: noimi at 00:06
D: noimi at 00:09
E: noimi at 00:15
F: sjc061031 at 00:13
PRIZES: 30 hoodies (customizable with name) will be given to:
- Top 20 Indian participants
- Random 10 from top 100 (rank 21-100) Indian participants
Note: we will identify Indian participants through their flags and they may be asked for address proofs later.
See you all in the standings!
UPD: Here is the list of people who won hoodies. We will contact you all soon. Congrats!
Top 20 Indian participants
- socho
- aryanc403
- JrNTR
- Kira_1234
- KDVinit
- IceKnight1093
- Everule
- kshitij_sodani
- shiven
- mexomerf
- 18o3
- abhidot
- used-fft
- towrist
- udhavvarma03
- Suri429
- _akasi
- Phantom_Deluxe
- ghoul932
- shadow9236
Random 10 from top 100 (rank 21 — 100) Indian participants
- ShlokG
- Harsha221B
- Pandemonium2024
- YPK
- BeastCode
- abhi_atg
- ShubhamAvasthi
- rohit2593
- karthikeya09
- Abhishek_Srivastava
About Celesta
Celesta is the annual Techno-Management Fest of IIT Patna. Celesta conducts a variety of events in various technical domains. Some of these are open and free for all, with exciting prizes and goodies for the winners!
You can head over to our website and check it out for yourself!
Good luck!
Auto comment: topic has been updated by TimeWarp101 (previous revision, new revision, compare).
As a VIP tester, I VIP-tested. Hope you enjoy the round!
Thanks Celeste for the contest! I appreciate it.
As a problem setter I set problems.
शुभकामनाएं
omg Spring Festival Eve round
omg Spring Festival Eve round
omg Spring Festival Eve round
omg Spring Festival Eve round
omg spring festivl eve round
omg sprin festivl ev rond
Get a life
A1: probably shipping issues A2: xd
omg new year eve round
Omg the round i tested is tomorrow. Hope you guys have fun!
Wtf with this indian rasism? Why all indian contests give prizes only to indian participats?
They are Indian setters. They can't send prizes to other countries because it costs too much.
Bla bla bla. You (indians) are the only one in this world, who are doing this. What a shame.
I am not Indian and I'm not saying whether they are right or wrong. I'm just saying what setters say in their comments usually.
Well code ton also gives prizes here and there.
Its only for indians that it cost so much.
stop talking Abito
Ton rounds give crypto currencies. This is different. I am not defending them nor am I attacking them. I am only stating what setters say when someone asks them about this. Please stop.
An Indian round without an Indian-rascism-shitposting thread is like a river without water. Sun Tzu | The Art of War
I am not sure why you are so invigorated by this. In this round, 2 packages were given to two participants in Vietnam and the contest organiser was Vietnamese.
Please understand that this contest (including most of the Indian contests I assume you were referring about and the Vietnamese contest I mentioned above) are not sponsored, so they are giving prizes from their own money. Shipping costs are a lot, so the prizes are confined to the contest's country.
Also, Codeforces is meant to be a rich and diverse platform for coding, not a way to get prizes. If that is your goal, I have a list of excellent gift stores I am sure you would like.
I was part of organising similar events in previous years, generally sending prizes requires approval from college professors and they denied to approve the transactions for overseas participants since it was "costing too much". Too much pain to convince them for anything. Later on we did send amazon gift cards to overseas winners but couldn't get approval for some prizes :(
I would have been top1 in this contest but unfortunately wont be able to participate.
As a problem setter, I discovered that, upon giving this contest, your IQ will increase $$$555$$$ times.
PS: The problems are super fun. Hope you all will enjoy solving them! Don't forget to read them all :)
My current IQ is ZERO, Do something for me as well
My IQ did increase thanks to this contest. (Hopefully the same happens for rating too XD)
Clashing with Leetcode round :/
Why yall downvoting? It is clashing
cuz codeforces>>>>leetcode
Setters are from my college, so excited. Best of luck people!
I need pants!
And so shall you have me.
Then i will prefer hoodie :)
Hype overload!!
Good luck to everyone participating! Hope you enjoy the problems.
Nobody wants to watch the boring Spring Festival Gala.A CF round is much better compared to the bad shows.
all the best everyone . have a good and learning contest for all.
As floormate of the problem setters, I can confirm that this round will be really interesting.
What prizes do u have for Belarus people?
Appreciations.
I need expert back.
Edit: It's done
omg Spring Festival Eve round
omg Spring Festival Eve round
Want to hear AwakeAnay side story.
#845 is about to begin and there's no official editorial for #844
I have a bad feeling about this round
What's the scoring distribution? It's still not updated.
I sincerely wish people all over the world a happy Spring Festival! In the new year, I hope you can achieve everything you want, be healthy and have good luck.
Great to take part in a Codeforces Round while watching the boring Spring Gala! Wish everyone and I have a great positive rating delta as well as a great new year!
Congratulations to participants for participating on Chinese New Year Eve.
I am having issue with submission of problem B. When running it on my local machine it is giving right answer but when I submitted the code it is printing different output. Please look into this..
You should try it in custom test and check if you are having the same output as your local machine or not.
Congratulations to yzc2005 for making submission 190000000 (link won't work until after contest).
Trash Indian rounds with very standard problems. Bad E and F.
i do not see issue with standard problems, earlier codeforces used to give standard problem variations only if you pickup few age old problems. It is just since recent 4-6 years that more constructive and math problems are coming and i do not see any issue in both standard/adhoc as they both enhance problem solving/approaching skill.
Again Downvotes with no explanation.
Problem C is interesting.
And how to approach D?
tree dp
How exactly?
The answer is 2^(n-1)*sum(the max depth of the subtree with root i) where i iterate among all vertexs. (the depth of leaves is 1, the depth of parents of 1-depth vertexs is 2, and so on)
I guessed this solution after an hour of doing random stuff on the sample case :/
I explained it like this: If at least of the children has a possibility to be a 1, that possibility has to be 50%.
Any number of XORing 50% possibility of 1 still gives 50%, so as long as one child could have a 1 in the previous round, we got a 50% chance of getting a 1.
For leaves it's just 50% one time, then they become 0. For a node one above that, once all children are 0, it also becomes 0 the next round. So if e.g. the longest child chain has 2 children, we have to take 50% chance 3 times, 1 for the start, and 2 for the 0 to trickle up through the length 2 children line.
Try to find the solution for every pair of nodes and times and then you'll soon realize that they are all the same before becoming zero.
...Try to think as a game of probability. At a single node, at any time
t, how likely is it that it is 1? How likely for it to be 0? Example: For all leaf nodes, at time0, there are 50% chance to be 0, 50% to be 1; at time 1, 100% 0.... A XOR 0 = A. Combine that with the previous hint about probability to calculate easier!
...For each node, there is a 50% chance that it is 1 on time
0toheight - 1, and 0% chance to be 1 from timeheighton. Therefore, for each node, the total amount of times it will be 1 for all possibilities is2 ^ n * (height + 1) * (1/2). The solution is the2 ^ (n-1) * (total height of all nodes + n)Did you solve C? What was your approach?
Sliding window
IS there any good article on two pointers and sliding window method?
Competitive programmers handbook
Thank you for the appreciation, it means alot. 🧡
Lol, problem F seems to be standard
I didn't do as well as I wanted but I enjoyed the contest, thanks setters ! :)
Problem D can be solved by tree dfs(we need to find the maximal path from every vertex to it's childs), and we can solve E with any template for finding strong components (we just need to add an negative weight edge v--(-w)-->u for every u--(w)-->v, representing the edge can be reversed if cost>=w, and binary search for cost), but I could not solve C.
Problem C is just two pointers :)
any hints of problems c ?
Check out the editorial, we have provided hints as well!
I don't think D was that trivial as it was pretty hard for me to see the idea. Or maybe it's just a skill issue on my part.
same... C took me 1 hour and a half ( I didn't see that I WA'd B cuz I didn't check submissions) ☠️ but D took me like 3 minutes to think of the solution and 10 minutes to code (though this was after the contest already ended so I can't submit.)
edf107ca33a984cc636ecf6ea4a24eb7f93fa527d4f10e0387f4eb4dad5958f5
How to prove Problem B solution?
n!*n*(n-1)
see below for my attempt to prove
I did the same thing. I saw that each permutation gave the same answer.
For the proof,
1 2 2 1consider the permutation, if you put3in to anywhere1 2 3 3 2 11 3 2 2 3 1...
it will increase the inversion count by
(3-1) * 2Because if for the left half its inversion count is
j, for the right half it will be3-1-j, plus all elements on the right half have inversion with the left3, overall it will bej+3-1-j + (3-1)inversion. Form, it willm-1+m-1 = (m-1)*2inversions. Summing this for allm <= ngivesn * (n-1)Suppose $$$p_i,p_j$$$ such that $$$1\le i<j\le n$$$ are distinct elements of the permutation. Their reflections are $$$p_i',p_j'$$$, respectively. If $$$p_i<p_j$$$, then they contribute only $$$2$$$ inversions because $$$p_j>p_i'$$$ and $$$p_j'>p_i'$$$. If $$$p_i>p_j$$$, then they also contribute only $$$2$$$ inversions because $$$p_i>p_j$$$ and $$$p_i>p_j'$$$. Thus, for every pair of distinct indices $$$i,j$$$, they contribute $$$2$$$ inversions. There are $$$n\choose2$$$ ways to choose pairs of indexes. So, the answer is $$$n!\cdot{n\choose2}\cdot2$$$.
Consider a specific permutation of size $$$n$$$. For any two different indices $$$i$$$ and $$$j$$$, either they form an inversion in the original array OR they form an inversion in the reverse array. Each such pair will contribute exactly one such inversion (note that there are no duplicates in the original array, since it is a permutation). There are $$$\frac{n(n - 1)}{2}$$$ pairs of indices.
This will already count all inversions that are between indices that are either both in the original array or both in the reverse array. All that's left is to count inversions where one index is in the original array and the other index is in the reverse array. Because both the original and reverse arrays are permutations, it's easy to count them: the value $$$k + 1$$$ in the original array will have $$$k$$$ values smaller than it which are present in the reverse array. Thus, the total number of such indices is $$$\sum_{k = 1}^{n - 1} k = \frac{n(n - 1)}{2}$$$.
Add them up and we have exactly $$$n (n - 1)$$$ such inversions. This is for a single specific permutation, without actually depending on what the permutation is. Since there are $$$n!$$$ permutations, the required answer is $$$n! n (n - 1) \bmod (10^9 + 6)$$$
Consider any pair of numbers $$$i$$$ and $$$j$$$, such that $$$i$$$ is to the left of $$$j$$$.
In the final array you will have ... $$$i$$$ ... $$$j$$$ ... $$$j$$$ ... $$$i$$$ ...
You can see that no matter which value is higher, each pair will give 2 inversions.
There are $$$ \frac{n(n - 1)}{2} $$$ pairs, each will contribute $$$2$$$ inversions per permutation and there are $$$n!$$$ permutations
how to solve problem C?
Sort the input array $$$v$$$. Keep track of 2 pointers $$$left$$$ and $$$right$$$, initially both at the 1st position of the array, and keep a map that stores the frequency of all the divisors from $$$v[left]$$$ to $$$v[right]$$$. If the size of the map is not equal to $$$m$$$, then increase $$$right$$$ and update the map, otherwise increase $$$left$$$ and update the map. Keep track of the minimum difference between max and min while iterating.
Due to Codeforces not loading properly near the start of the contest, some participants may have accidentally submitted the same code multiple times. In my case, for example, I used the main site to submit and got a 502 Bad Gateway, so I switched to one of the lightweight versions (m1, m2, or m3, not sure exactly which one) and submitted over there instead, not realizing that my first submission actually went through. This was treated as a resubmission and I lost 50 points because of it.
Is it possible to make any adjustments such that these kinds of duplicate resubmissions are not penalized? Note that the main site normally blocks the user from submitting an identical code twice, so I think it would be perfectly justified to remove such identical codes that did manage to get through (due to using the lightweight site, which implies technical issues that the participant should not be punished for experiencing).
Here are my submissions: 189973808 189973881.
Tagging MikeMirzayanov because I think this should be applied universally across Codeforces contests, if possible.
this issue happened to me too and It made my submission for problem A later about 1 minute:(
Was stuck in problem C for a long time, any intuition on how to solve it?
If you've found a suitable difference between the max and min in some subset, it's optimal to include as many students in that subset as possible
i swear there is like no other solution for problem C other than annoying brute force and also to make the execution somehow fast
Read the problem statement for E as the minimum weight of edge reversal weight so that every node is reachable from one another. IMO this version seems cooler (and harder) than the original one.
It's as simple as the original problem (both versions need to check strong components). The original is checking "whether there is only one component with 0 in-degree", and your version is checking "whether there is only one strong component".
Why did 189996915 not pass? I thought since
indandfac[n]are moddedMalready,ind,fac[n]<=1e9+6. and(1e9+6)^2<=max ll??But subtraction modulo M may give a negative number, so you also need to add M and take modulo again.
Is d tree dp? I couldn't really think of a solution, how do you solve D?
No, it's math. For each node to be equal to 1, calculate total no. of arrays for which it is possible. Also find its relation with its height.
The TL on F is stupidly high, a simple $$$O(n^2)$$$ passed: 190000292
Maybe there's larger test in system testing…
Also there's possibility that the problem setter forgot to disable O(n^2) solutions for Div2F.
I hacked it, the system tests are too weak
Anyone knows why simple dfs from first vertex in topological sort works in E? (for checking the condition)
As far as I know, topological sort only works for graphs without cycles
If you think about it, the first vertex after the topological sort is the one which will always belong to the first SCC (i.e. a SCC with 0 indegree). So, just checking whether all the other nodes are reachable from this vertex is enough for the problem.
I didn't see the constraint on n (problem D) carefully and set 100000 for the arrays. However, instead of getting RE, it got TLE ??? Just changing it from 100005 to 200005 made the program pass...
I liked problem D. It had such a simple solution (after thinking it through). Missed the submission by a few seconds tho ^^
Yeah, D was quite frankly hard to think about.
Can someone please look into my profile and suggest something, I don't know but cannot perform well for the last 7-8 contests. Please do recommend anything. It would be a great help. Thank you!!
it could be that you took a break and you need a little bit of time to de-rust..
Can't believe I screwed up the contest by not precomputing the divisor array globally as I did the question by finding out the divisor of elements for every array as I thought what's the harm, finding divisor is sqrt(a[i]) time complexity anyway --> worst mistake. What a sad feeling it gives when you could've solved the question but lack of knowledge or stupidity comes in the way. PS: 1. Learned something new 2. Won't be forgetting it ever again
Problem E is a template of Tarjan.
How to solve C?
Essentially what you want to find first is a subarray of numbers such that the number of factors of all numbers in that subarray is exactly $$$m$$$. Once you have done that, all we want to do now is to minimize the difference between the maximum and the minimum numbers in that subarray. You can do this by having $$$2$$$ pointers, and incrementing the $$$1st$$$ pointer towards the right while making sure that the number of factors remain $$$m$$$
Can someone help me find, what might be the issue with this submission for problem D?
190024130
Idea is to find the depth of each node and sum them. Finally multiple that by
pow(2, n-1).You forgot to set
ans = 0insolvefunction beforedfscall.Thanks man!
-_-
Hints for D please?
Check out the editorial, we have provided hints as well!
system test when ?
Waiting for systests too, bit odd its so late. It annoys my I can't check all the pretests before system testing finishes...
I legitemately think they forgot.
I thought it was automated
Even forgetfulness is automated. Welcome to AI.
Here goes how solved A-F today in brief.
Upd: Add all problems now.
for those who need help with C,D you can find the video editorial here — https://www.youtube.com/@grindcoding. Happy coding!
When will the System testing start? I have to cry myself to sleep also.
Us
why is it taking so long for system testing
Main test? MikeMirzayanov
Speedforces
can't wait to upsolve.System testing :(.
Don't upsolve such bad problems
anyone solved C with binary search
can you explain your solution with binary search? I got WA with binary search.
First I used seive to get the factors of all the numbers and used them in a map and I observed that the number of factors would not be more 125.
Then I sorted the array.
Then I binary searched on 0 to 1e18 (I took the upper bound randomly high) where for every mid I used sliding window to check if the given mid is possible or not .
Then shifted the window accordingly.
thanks. I did a binary search for the length, but it turned out to be wrong.
why am i getting WA on pretest 2 for problem c : 190021791
Nice Contest
Please watch the rule first.
my submission is not tested on main tests please look into it 190002478 TimeWarp101
Rating also updated,still not tested.MikeMirzayanov.
Why this solution:190038867 for problem A is giving WA. Thanks.
cout before cin
In the case of N = 1 for some testcase, you do not cin >> A[i] for the vector A. Thus, you return before you have read input for the current testcase
In D, I was memsetting a bool array of size 2*10^5 every single test case, which could have been 10^5 times. I'm surprised it got accepted. Is memset really that fast? Is it doing something magic in the background? https://codeforces.com/contest/1777/submission/190020821
when will be ratings updated?
to me, C is too hard and D is too easy, I'm stupid
i don't want to offend you but the datamaker of F have no brain?
to me: D was easier than C
my friend got 8000th standing, and i got 6600th, yet he still got more rating, i got my rating reduced he had his 9th contest this round and this was my 7th :/
I got WA in Problem-C
My submission: https://codeforces.com/contest/1777/submission/190090177
Check this test case n=4,m=5,a=[8 9 10 20]
Hey I find this Round has become unrated.Does anyone know why?
Temporary rating rollbacks are common. Generally, they need to recalculate rating changes (e.g., after identifying a significant set of cheaters). It should be updated soon afterwards.
It's also possible that this contest was decided to be unrated due to some serious issues, but there was no announcement about this, nor did I see anyone discuss any such issue, so I think this is extremely unlikely. The contest should be rated; please be patient.
Now it has been rated again.Thanks for your explanation!
What the hell man...one more codeforces round that got unrated...i just noticed that the ratings have been withdrawn..this sucks man..it absolutely sucks
why the rating of this contest rolled back?
please update problem ratings
For the record, I was supposed to receive a hoodie but I didn't and the contest organizers refuse to reply.
Hey, the hoodie should reach you soon, probably within 1-2 weeks. My apologies if we were unresponsive.
It did not reach and I have not received any communication about the progress after your comment.
TimeWarp101, still no updates.
I will continue posting every few months if I don't receive any updates.