Amir_Parsa's blog

By Amir_Parsa, history, 18 months ago, In English

Hello Codeforces!!

We're honored to invite you to TheForces Round #14 (Cool-Forces) which will take place on May/23/2023 18:05 (Moscow time).

What is a TheForces Round? (If you don't know, you must read it)

You will have $$$135$$$ minutes to solve $$$7$$$ problems.

Please don't forget the time. Registration is open now.

Discord Server (800+ people, join for a cookie )

Contests' archive

Editorial

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

| Write comment?
»
18 months ago, # |
  Vote: I like it -102 Vote: I do not like it

As a problemsetter give me negative contribution.

»
18 months ago, # |
  Vote: I like it +66 Vote: I do not like it

As a problemsetter, this round has a plethora of interesting problems. Everyone would love it!

»
18 months ago, # |
  Vote: I like it +74 Vote: I do not like it

As a tester, this is the best contest I have seen so far in the Forces Rounds! It is worth spending time over in this type of contest. PS: Enjoyed testing this round a lot ;)

»
18 months ago, # |
  Vote: I like it +51 Vote: I do not like it

As a tester and co-founder of theforces, give me some contribution please

»
18 months ago, # |
  Vote: I like it -38 Vote: I do not like it

is it rated?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    Did you read this : What is TheForces Round? (If you don't know, you must read it)?

»
18 months ago, # |
  Vote: I like it +46 Vote: I do not like it

First time tested a coding round. Thank you. Problems are awesome. Enjoy Problem-solving.

»
18 months ago, # |
  Vote: I like it +38 Vote: I do not like it

As a tester, I want to say that this contest will make you happy if you want to solve many topics, this will give you that, and it will make your mind explode

»
18 months ago, # |
  Vote: I like it +35 Vote: I do not like it

TheForces again Orz!

»
18 months ago, # |
  Vote: I like it +34 Vote: I do not like it

As a tester, these guys are more creative than Da Vinci.

»
18 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).

»
18 months ago, # |
  Vote: I like it +18 Vote: I do not like it

As a tester, I recommend you to definitely give a try.
The contest has amazing problems.

»
17 months ago, # |
  Vote: I like it +37 Vote: I do not like it

As a tester, i can say the descriptions of problems in this round are pretty neat and easy to read. And I like each problem a lot. Don't forget to read some of the interesting titles and hope you'll have fun!

»
17 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

So the round's difficulty is like div.3 rounds or div.2 rounds?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I think it could be more like div2

»
17 months ago, # |
  Vote: I like it +8 Vote: I do not like it

E is beautiful

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you have a good solution which isnt just bitmask dp? if not, i would have to disagree with you

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I solved it using SOS dp in $$$O(n \cdot 2^m \cdot m)$$$ and 31 ms runtime, I'm not sure if this is what you're talking about.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        even this version does still not very interesting to me (just one more standard trick), i just bruteforced transitions in 3^m * n

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          I get what you mean and yes, that the idea is quite standard. I just haven't seen many problems that use the idea and I was slightly surprised when I realized that it worked, guess I should just solve more problems then

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

problem feedback :

A : fine for A

B : standard problem so dont like, who are you fooling with a[i] — i — x instead of a[i] — x

C : it wud be ok problem, but its quite obviously the edu F ripoff (wtf is the point of a 10^18 size array)

D : fine problem

E : standard dp problem

F : its fine, but i believe this idea is over used, have seen it before

G : no comments

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to do F? I can only think of O(n^3) which gets timeout.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maintain a prefix sum of dp states and use segment tree to find the range sum.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    just bruteforce i, j and add the number of subsequences where s[i], s[j] would need to be equal if they are not already equal

  • »
    »
    17 months ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    O(n^3) solution is good enough to pass F.

    If a[i] != a[j], then all f(x) that contains both i and j as corresponding characters should increase by 1. And there are $$$(\sum_{x=0}^{min(i-1,n-j)}C(i - 1, x) * C(n - j, x)) * 2^{j - i - 1}$$$ such subsequences. Since $$$min(i-1,n-j) \le n / 2$$$, pre-calculate every $$$\sum_{x=0}^{min(i-1,n-j)}C(i - 1, x) * C(n - j, x)$$$ for each distinct $$$(i-1, n-j)$$$ pair takes $$$O(n^3 / 8)$$$ time complexity. My solutions works within 300ms.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This solution came to my mind and I already coded it during the contest and I spent the remaining time trying to optimize it, after reading your reply I just submitted my code and it passed and didn't get TLE. Thank god it's not a rated codeforces round otherwise I wouldn't have forgiven myself

»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Tutorial for F/G

Let's consider every pair $$$\displaystyle(i, j)$$$ in the array, and find out $$$\displaystyle f(i, j)$$$ which is how many subsequences will include both $$$\displaystyle i$$$, $$$\displaystyle j$$$ as a mirrored pair.

The answer to the problem should be $$$\displaystyle\sum_{i=1}^{i=n} \sum_{j=i+1}^{j=n} f(i, j)*(arr_i != arr_j)$$$.

If we find a way to calculate $$$\displaystyle f(i, j)$$$ in $$$\displaystyle O(1)$$$, this should be good enough to get solution for easy version in $$$\displaystyle O(n^2)$$$.


Calculating f(i, j)

Optimising for hard version - Hint 1

Optimising for hard version - Hint 2

Optimising for hard version - Hint 3
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Actually if you implement it better, the time complexity is $$$\mathcal{O(n\sqrt{n\log n}})$$$ as the complexity in different parts are different and only one contains $$$\log$$$.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).