Invitation to TheForces Round #13 (Boombastic-Forces)

→ Обратите внимание

Соревнование идет
Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
00:44:45
Зарегистрироваться »

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Invitation to TheForces Round #13 (Boombastic-Forces)

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

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.

Problems were prepared and authored by Amir_Parsa ,E404_Not_Found, Sevawy.
We would like to thank our army of testers: physics0523, Madboly, blxst, O--O, Virendra115, blxst, BallBreaker, ExpensiveAC, aphex, TheOpChicken123, leneza_41, EndlessDreams.
Also we want to thank you for participating in our round.

Discord Server (700+ people)

Contests' archive

Анонс TheForces Round #13 (Boombastic-Forces)

Amir_Parsa
12 месяцев назад
26

Комментарии (26)

Написать комментарий?

BallBreaker

12 месяцев назад, # |

+41

Nice problems. (i didnt tested yet XD)

→ Ответить

O--O

12 месяцев назад, # |

+47

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

→ Ответить

blxst

12 месяцев назад, # |

+18

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

→ Ответить

aphex

12 месяцев назад, # |

+18

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

Spoiler

→ Ответить

E404_Not_Found

12 месяцев назад, # |

+15

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

→ Ответить

VinCenzo___

12 месяцев назад, # |

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

→ Ответить

Amir_Parsa

12 месяцев назад, # ^ |

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.

→ Ответить

VinCenzo___

12 месяцев назад, # ^ |

done!!

→ Ответить

Tima9

12 месяцев назад, # |

→ Ответить

Java_programmer__

12 месяцев назад, # |

+16

Educational-Forces

→ Ответить

vgtcross

12 месяцев назад, # |

← Rev. 3 →

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.

→ Ответить

ShivanshJ

12 месяцев назад, # ^ |

← Rev. 2 →

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?

→ Ответить

Chimpanzee

12 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

ShivanshJ

12 месяцев назад, # ^ |

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.

→ Ответить

Chimpanzee

12 месяцев назад, # ^ |

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

→ Ответить

ShivanshJ

12 месяцев назад, # ^ |

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

→ Ответить

Chimpanzee

12 месяцев назад, # ^ |

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

→ Ответить

vgtcross

12 месяцев назад, # ^ |

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.

→ Ответить

vgtcross

12 месяцев назад, # ^ |

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.

→ Ответить

fun.contest.id

11 месяцев назад, # ^ |

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

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64

int const mod = 1e9 + 7;
int const MX = 511;
int C[MX][MX];
void compute() {
  C[0][0] = 1;
  for(int i = 1; i < MX; i++) {
    C[i][0] = 1;
    for(int j = 1; j <= i; j++) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
      C[i][j] %= mod;
    }
  }
}
int nCk(int n, int k) {
  if(k > n) return 0;
  return C[n][k];
}

void solve() {
  int n; cin >> n;
  vector <int> a(n);
  for(auto&x : a) cin >> x;
  vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
  /*
   *
   * dp(i, j, 0) -> free to choose 
   * dp(i, j, 1) -> must have i and j as endpoints and a[i] > a[j]
   * 
  */
  for(int i = 0; i + 1 < n; i++) {
    if(a[i] > a[i + 1]) {
      dp[i][i + 1][0] = 1;
      dp[i][i + 1][1] = 1;
    }
  }
  auto get = [&](int i, int j, int k) -> int {
    if(i < 0 or j > n) return 0;
    if((j - i + 1) & 1) return 0;
    return dp[i][j][k];
  };

  for(int len = 4; len <= n; len += 2) {
    for(int i = 0; i + len - 1 < n; i++) {
      int j = i + len - 1;
      dp[i][j][1] = (a[i] > a[j]) * get(i + 1, j - 1, 0);
      for(int k = i + 1; k <= j - 2; k++) {
        int l1 = k - i + 1, l2 = j - k;
        if(l1 & 1) continue;
        dp[i][j][0] +=nCk(l1/2 + l2/2, l2/2) * (get(i, k, 1) * get(k + 1, j, 0) % mod) % mod; 
        dp[i][j][0] %= mod;
      } 
      dp[i][j][0] += dp[i][j][1];
      dp[i][j][0] %= mod;
    }
  }
  cout << dp[0][n - 1][0] << "\n";
  
}

constexpr bool multiTests = false;
int32_t main() {
  compute();
  cin.tie(0) -> sync_with_stdio(0);
  int TC = 1; 
  if(multiTests) cin >> TC;
  for(int t = 1; t <= TC; t++) {
    solve();
  }  
}

→ Ответить

cosenza

12 месяцев назад, # ^ |

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

→ Ответить

Java_programmer__

12 месяцев назад, # |

+16

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

→ Ответить

vgtcross

12 месяцев назад, # |

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

→ Ответить

Amir_Parsa

12 месяцев назад, # |

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

→ Ответить

RHEXAOC

12 месяцев назад, # |

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

void solve() {
    int n, i;
    cin >> n;
    vector<int> as(n), bs(n);
    for (i = 0; i < n; i++) cin >> as[i];
    for (i = 0; i < n; i++) cin >> bs[i];
    int a = 0, b = 0;
    while (a < n && b < n) {
        if (as[a] == bs[b]) {
            a++;
            b++;
        } 
        else a++;
    }
    cout << ((n - b) << 1) << endl;
}

It got accepted.

→ Ответить

qtwo

12 месяцев назад, # ^ |

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 04.05.2024 13:50:15 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке