Amir_Parsa's blog

Invitation to TheForces Round #13 (Boombastic-Forces)
By Amir_Parsa, history, 12 months ago, In English

Hello, Codeforces!

We are happy to invite you to TheForces Round #13 (Boombastic-Forces), which will take place on May/07/2023 18:10 (Moscow time)

What is TheForces Round?

Editorial

You will have 120 minutes to solve 7 problems.

We strongly recommend you to read all problems.

Discord Server (700+ people)

Contests' archive

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

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

Nice problems. (i didnt tested yet XD)

→ Reply
»
12 months ago, # |
  Vote: I like it +47 Vote: I do not like it

As a tester, I will test round while listening the Mr. Boombastic song.

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

As a tester, I will test this round after writing this comment

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

As a tester, this is my first "As a tester" comment.

Spoiler
→ Reply
»
12 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I can't register in this contest.What's the issue it is saying that you cannot participate in group contest

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If you're seeing this contest from TheForces group then you should join as a "participant" in the group to be able to register, Otherwise you can register for the round from GYM.

    → Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

→ Reply
»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Educational-Forces

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

C was purely just annoying implementation (or knowledge about some standard functions).

I don't know how to solve D or E. I just recognised that both were standard problems (that I don't completely know how to solve) and just copied a solution from the internet.

F and G were nice though.

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    G was just standered $$$O(n^3)$$$ dp right? $$$dp[i][j]$$$ denotes no. of ways to remove the subarray $$$[i..j]$$$.
    Transitions were $$$dp[i][j] = dp[i+1][j-1]*(a[i]>a[j]) + \sum\limits_{w=i+1}^{j-1}(2*dp[i][w]*dp[w+1][j])$$$

    Where am I wrong?

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Wait why is it 2*dp[i][w]*dp[w+1][j]? Wouldn't the coefficient of this term be factorial(L1/2+L2/2)*(factorial(L1/2)*factorial(L2/2))? Because we can choose the order in which we perform delete operations on these two subarrays

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

        Aaah got it! Thanks! Yeah you are right, the two subarrays are "independent", we can freely choose the order of the operations performed inside them.

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

          I didn't get AC though :( idk what's wrong with my approach

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

            Now I also updated the transitions, still getting WA :(

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Maybe setter's solution is incorrect (baby don't hurt me)

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

                You should try the following test case. I tried some of your submissions and they all gave wrong (and different) answers to this:

                Input:
10
2 1 4 3 6 5 8 7 10 9

Output:
120

                Explanation: You need to clear the following pairs (nothing else is possible):

                [2, 1]
[4, 3]
[6, 5]
[8, 7]
[10, 9]

                All of them are also independent meaning that you get $$$5! = 120$$$ removal sequences.

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

              Here is a test case where your code fails:

              Input:
10
2 1 4 3 6 5 8 7 10 9

Correct Output:
120

Your Output:
224

              Explanation: You need to clear the following pairs (nothing else is possible):

              [2, 1]
[4, 3]
[6, 5]
[8, 7]
[10, 9]

              All of them are also independent meaning that you get $$$5! = 120$$$ removal sequences.

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

            When considering this approach, i noticed double counting occurs after considering certain examples,so to avoid that we need to create another state k such that k = 1, means we need to fix end points i, j of the subarray in the last operation and $$$a[i] > a[j]$$$ and k = 0 means we can freely do the operations.

            So the transitions will be

            $$$dp(i, j, 1) = (a[i] > a[j]) * dp(i + 1, j - 1, 0)$$$
            $$$dp(i, j, 0) = dp(i, j, 1) + \displaystyle \sum_{k=i+1}^{j-2} C \left(\frac{l_1+l_2}{2},\frac{l_2}{2}\right) * dp(i, k, 1) * dp(k + 1, j, 0)$$$
            my code for reference
            → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      check this out: https://usaco.guide/problems/cses-1080-empty-string/solution
      it's pretty much the same problem

      → Reply
»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

For D task https://codeforces.com/blog/entry/99907

→ Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Solution to E: https://codeforces.com/blog/entry/90035

→ Reply
»
12 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).

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The tests are strange? Are there any? Well, I like the problem, the rest is not important, for me. But I assume feedback to the round is ok.

I look at the code of problem D of 40th position at standings.

code

It got accepted.

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

    If that code really got accepted, then the test of that problem is kinda weak. A simple test like this will make the code fail:

    3
1 2 3
3 1 2
    → Reply