Блог пользователя O--O

Автор O--O, история, 21 месяц назад, По-английски

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

Thanks for participating.

Winners:

1. Little_Sheep_Yawn

2. siganai

3. nifeshe

4. Svyat

5. wuhudsm

Discord Group

Contests' archive

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Exicited!

»
21 месяц назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Cool

»
21 месяц назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Yeah, Here we go again!

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Postponed 5 min?

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, Latex doesn't show for me.

»
21 месяц назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Missed the contest :(, came 1 hr late.

Came in rainboy mode and could solve only $$$E$$$ and $$$F$$$.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    legend sir

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    bro could u explain me F

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is E O(n*(2^n)). If yes, please anyone check my last sumbission, what i am doing wrong? Thanks if anyone answer!

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For me, A >>>>>>> (B,C,E,F). How to solve A?

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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, where a <= n && b <= n will always be <= n) would be 13 * (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).

    • »
      »
      »
      21 месяц назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Sum of first n natural number is n * (n + 1) / 2 So, if you do 13 * (13 + 1) / 2 = 91

»
21 месяц назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

This code for problem F does not pass in Python. Gives TLE on test 2, I am using PyRival factorial template

Code

Is there any way to optimize this ? Still TLEs after taking out the hash table (by sorting) and precomputing.

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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:

    Python Code

    It actually uses $$$\frac{1}{n!}=\frac{1}{(n+1)!}*(n+1)$$$

»
21 месяц назад, # |
Rev. 3   Проголосовать: нравится -20 Проголосовать: не нравится

Would you please review this code? I get WA on test2 9 times...

Spoiler
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is E based on Inclusion — Exclusion principle?

»
21 месяц назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

D's problem statement was very very poorly written, not properly defined number of digits

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

E is similar to this problem

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

loved this contest, particularly E ,but forgot about avoiding the integer overflow :(

btw where can I find the editorials?
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    this time, no editorials, you can see solutions and try to understand

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
21 месяц назад, # |
  Проголосовать: нравится +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.