We invite you to participate in CodeChef’s October Long Challenge, this Friday, 2nd October, from 15:00 IST onwards. The contest will be open for 10 days i.e. until 12th October.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Joining me on the problem setting panel are:
- Setters: Ildar 300iq Gainullin, Aleksandr enoone Abelyan, Ivan isaf27 Safonov, Chaithanya Dragonado Shyam, John Smith, Md. Reyad Fiction Hossain
- Admin: Ildar 300iq Gainullin
- Editorialist: Jelmer Firet, Srikkanth srikkanthr
- Tester: Radoslav radoslav11 Dimitrov
- Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Mani manijuana Tyagi, Divesh divesh2201 Thakker
- Statement Verifier: Jakub Xellos Safin
- Mandarin Translator: Hanlin Ioser Ren
- Vietnamese Translator: Team VNOI
- Russian Translator: Fedor Mediocrity Korobeinikov
- Bengali Translator: Mohammad solaimanope Solaiman
- Hindi Translator: Akash Shrivastava
Prizes:
P.S: For October Long Challenge, we won't be having any tie-break Challenge problem. So, instead of giving the usual cash prizes to the top-ranked users, we will give laddus, which help in the fair distribution of reward. For the Indian rank list, we'll distribute 5000 laddus amongst all the top-scorers. For the Global rank list, we'll distribute 13000 laddus amongst all the top-scorers. The top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here
Good Luck!
Hope to see you participating!
...
So mail Codechef, don't post a link to it publicly -_-
ROOTMST was very interesting!
If the underlying MST is a line, then the problem is similar to $$$k$$$-maxsum problem, which can be solved by augmenting-path like greedy. Now here I don't have proof, but you can simply turn the MST into a line as in this trick.
It seems there are many different approaches to this problem. I think mine is the easiest to implement, but I like other solutions as well.
Was that an intentional decision or just a lack of good problem?
300iq orz. Great contest!
how to INVSMOD2?
Unfortunately there's a simple formula for it, found by googling.
Theorem 1.4 in https://www.researchgate.net/publication/45900393_The_number_of_permutations_with_k_inversions
$$$C(n,r)\%2$$$ is $$$1$$$ iff $$$r$$$ is a submask of $$$n$$$ (Lucas Theorem)
It's $$$O(sqrt(n))$$$ overall.
It would be very useful if someone shares the proof of that formula.
Yes, I think it was intended to be tougher problem as it was not included in div2 but most participants(including me) solved it by finding similar problems upon googling.
Lol it was in TAOCP... Well known for Knuth...
How will $$$O(n*sqrt(n))$$$ pass?
It was O(sqrt(n)). Changed. Thank you!
Proof
Actually, I proposed for this long contest long time ago, and it is removed because of duplication: https://www.hackerearth.com/problem/algorithm/perfect-permutations-september-clash/description/.
https://codeforces.net/blog/entry/77551 you can find the O(sqrt(k)) answer in the solution of perfect permutation.
I AM NOT ASKING FOR SOLUTION NOR TELLING ANSWER.
in the 3rd ques. it is giving TLE just for printing array(i was using java)??? why so?
Can anyone explain D-Dimensional MST, editorial is not written properly for that question?
Both, DDIMMST https://discuss.codechef.com/t/ddimmst-editorial/79385 and ADDSQURE https://discuss.codechef.com/t/addsqure-editorial/79023 are badly understandable.
In DDIMMST the key is to find a fast way (faster than O(n^2)) to identify edges with the biggest distance among a group of edges. The tutorial explains a way to "somehow" do this with masks.
I think that editorials are well-written. If you have any questions, ask the exact question in the editorial blog.
I think this comment explains the key point.
It refers to the tutorial of 1093G - Multidimensional Queries
Can you pls explain i couldn't understand , i have the similar doubt as that author ? What i don't understand is if i query max for all the ci's then i need to sure that that max is actually present in the original segment ?
I will try to explain with my words, but I am not sure about it.
We create $$$2^d-1$$$ vectors of numbers. In each vector j we calculate for each point i a value p[i][j]. That value is calculated as the sum of the coordinates of that point. But some are added, some are subtracted. Since we do this for each of the $$$2^d-1$$$ masks, the vectors include all possible combinations of add and subtract.
Let $$$\tilde{}$$$ be the bitwise not operation. ie, if we add a dimension $$$d_x$$$ in vector $$$j$$$, then we subtract that dimension in vector $$$\tilde{}j$$$
Then we sort all the vectors, and foreach vector we calculate the difference between the first (ie the biggest) value of that vector, and the smallest value of the "bitwise opposite" vector, which is $$$abs(p[0][j] - p[i-1][\tilde{}j])$$$
The biggest of these differences is the biggest distance of two of the i points. And the two points are those where we found that value.
Actually we can directly search for min and max value in the vectors instead of sorting, with O(n) complexity instead of O(logn)