Hello, Codeforces!
We are happy to invite you to TheForces Round #6 (NewForces), which will take place on [contest_time:428154]
You will have 2 hours to solve 6 problems
Problems were prepared by O--O, and E404_Not_Found
Would like to thank our testers: merlin_ , tolbi, sreesh_56 , k1r1t0, aayush_chhabra, nolimiya.
- Also we want to thank you for participating in our round
Thanks for participating.
Winners:
2. siganai
3. nifeshe
4. Svyat
5. wuhudsm
Exicited!
Cool
Yeah, Here we go again!
Postponed 5 min?
Hi, Latex doesn't show for me.
Missed the contest :(, came 1 hr late.
Came in rainboy mode and could solve only $$$E$$$ and $$$F$$$.
legend sir
bro could u explain me F
Sure!
We can simplify this problem as say we have $$$n$$$ black blocks with some size as $$$a_i$$$ and we have some other $$$m$$$ white blocks of size as $$$1$$$ which we want to place such that none of $$$n$$$ blocks touchs each other.
So minimum required white boxes are $$${n - 1}$$$ (as if we place one white block in between $$$2$$$ black boxes). So if $$${m < n - 1}$$$ no way to fulfill the condition. So if we have placed $$${n - 1}$$$ white blocks already so now we have to place remaining $$${m - n + 1}$$$ white boxes. And we also can rearrange black boxes, which can be done in $$${n! / (p! * q! ....)}$$$ where $$$p$$$, $$$q$$$ ... are simply occurrences of each distinct block. (A simple 10th grade maths). Now we can place remaining (m — n + 1) white boxes in $$${(n + m - n + 1) \choose (m - n + 1)}$$$ or $$${m + 1 \choose n}$$$ ways. which is simply Stars And Bars theorem.
My Submission
Is E O(n*(2^n)). If yes, please anyone check my last sumbission, what i am doing wrong? Thanks if anyone answer!
Did you avoid overflows? I made 3 wrong submission for that as lcm can be more than 1e18.
Thanks, i forgot about it :)
For me, A >>>>>>> (B,C,E,F). How to solve A?
Well, I just made some observations on
n = 12
.So, if you notice, there are 13 numbers between 0 and 12, so total pairs (why all pairs? well because
a & b
, wherea <= n
&&b <= n
will always be<= n
) would be13 * (13 - 1) / 2 = 78
. Now just adding 13 to this number again, gave me the answer (I could not find what the other 13 pairs were and just solved it by guessing).Sum of first n natural number is n * (n + 1) / 2 So, if you do 13 * (13 + 1) / 2 = 91
This code for problem F does not pass in Python. Gives TLE on test 2, I am using PyRival factorial template
Is there any way to optimize this ? Still TLEs after taking out the hash table (by sorting) and precomputing.
Actually, the real problem is that you used Fast Exponentiation to calculate the inverse element of factorial, which makes the time complexity $$$\mathcal{O}(nlogM)$$$ $$$(M=998244353)$$$.
But actually, it can be solved in $$$\mathcal{O}(n)$$$ like this:
It actually uses $$$\frac{1}{n!}=\frac{1}{(n+1)!}*(n+1)$$$
Thanks
Would you please review this code? I get WA on test2 9 times...
put it under spoiler like this..
...
check, that if s = 1 and n > 1, the answer is -1 too.
But this problem does not say that leading zeros are invalid?
Is E based on Inclusion — Exclusion principle?
yes
What do you think could be the rating of E?
Most Probably $$$1700 - 1800$$$
Got it just after contest, I was taking mutliplication instead of LCM. Damn me!
D's problem statement was very very poorly written, not properly defined number of digits
E is similar to this problem
agree, I inspired from this problem
Interesting.I am the author of this problem and we solved each other's problems today :)
loved this contest, particularly E ,but forgot about avoiding the integer overflow :(
this time, no editorials, you can see solutions and try to understand
I recommend seeing ventusliberum solution of E. Nicely done, V. From my point of view. In particular:
r/(a*b/g)<1
~b/g>r/a
(I'm not covering real/natural division), helps to stay in long integer type. As well as:g = gcd(LCM[i & -i], LCM[i & i - 1])
, calculating value of larger set from two subsets instead of naive O(bit_width). For those who don't know, negation-
in machine is implemented as executing supplement~
and then executing plus one++
. That is-i==~i+1
.I just found an anti-test for my solution to one of the problems. The tests in this contest are not very good in my opinion.