O--O's blog

By O--O, history, 21 month(s) ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Exicited!

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Cool

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Yeah, Here we go again!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Postponed 5 min?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Latex doesn't show for me.

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Missed the contest :(, came 1 hr late.

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    legend sir

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro could u explain me F

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Did you avoid overflows? I made 3 wrong submission for that as lcm can be more than 1e18.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, i forgot about it :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 month(s) ago, # |
Rev. 3   Vote: I like it -20 Vote: I do not like it

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

Spoiler
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    put it under spoiler like this..

    Spoiler
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check, that if s = 1 and n > 1, the answer is -1 too.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But this problem does not say that leading zeros are invalid?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E based on Inclusion — Exclusion principle?

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

E is similar to this problem

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    agree, I inspired from this problem

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Interesting.I am the author of this problem and we solved each other's problems today :)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

btw where can I find the editorials?
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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.