Amir_Parsa's blog

By Amir_Parsa, history, 18 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

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

Nice problems. (i didnt tested yet XD)

»
18 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.

»
18 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

»
18 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
»
18 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).

»
18 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

  • »
    »
    18 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.

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

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

Educational-Forces

»
18 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.

  • »
    »
    18 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?

    • »
      »
      »
      18 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

      • »
        »
        »
        »
        18 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.

        • »
          »
          »
          »
          »
          18 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

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

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

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                18 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.

            • »
              »
              »
              »
              »
              »
              »
              18 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.

    • »
      »
      »
      18 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

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it
»
18 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).

»
18 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.

  • »
    »
    18 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