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

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

We will hold Monoxer Programming Contest 2024(AtCoder Beginner Contest 345).

We are looking forward to your participation!

  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck to everyone!

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The contest cover page is in Japanese language even though my atcoder account is in English. Is that a contest registration issue or is it going to be in Japanese? Thanks, Rafael

»
8 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

ABC 345... Time for me to practice arithmetic series to prepare for this contest.

»
8 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

ABC345? Increasing sequence?

»
8 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

contest questions are in japanese language?

»
8 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Does the contest provide problem statements in English or only in Japanese?

»
8 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Please tell us if you only provide Japanese problem statements.

Although I'm a Chinese, I know that there're some differences between Chinese and Japanese, so it may cause ambiguity.

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

To those who are confused

All previous rated ABC have Japanese and English statements. I don't know this time, but I guess it's the same since no special announcement was made.(I'm not an official)

»
8 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

How C

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    hint
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I actually tried implementing the same thing but I got WA x13

      #include <bits/stdc++.h>
      
      using namespace std;
      #define int long long
      typedef long double ld;
      #define all(x) x.begin(), x.end()
      #define pb push_back
      
      signed main(){
      	string s;
      	cin >> s;
      	set<char> a;
      	int n = s.size();
      	vector<int> suffix(n);
      	suffix[n-1] = 0;
      	a.insert(s[n-1]);
      	for(int i = (n - 2); i >= 0; i--){
      		if(!a.count(s[i])) suffix[i] = a.size();
      		else suffix[i] = a.size() - 1;
      		a.insert(s[i]);
      	}
      	int ans = 0;
      	for(int i = 0; i < n; i++){
      		ans += suffix[i];
      	}
      	cout << max(ans, 1LL) << endl;
      }
      
      

      What could I be missing in my logic?

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I could not understand your logic, but I think you are doing the same mistake I made yesterday.

        I figured it out now, if we can generate the original string again then it would count as well in the final result, that would happen only if the frequency of any character is $$$>1$$$, so make $$$ans = 1$$$ when you see that, then iterate over the string to calculate the remaining answer.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why ain't this working , pls can you help me out

      string s; cin>>s; int n=s.size(); map<char,int>mp;

      for(int i=0; i<n;++i){ ++mp[s[i]]; } vectorv; for (auto it:mp ) { /* code */ v.push_back(it.second); }

      int sum=0;

      for (int i = 0; i < v.size(); i++) { /* code */

      for (int j = i+1; j < v.size(); j++)
      {
          /* code */
          sum+=(v[i]*v[j]);
      }

      } for (auto it:v) { /* code */ if(it>1){ ++sum; break; } }

      cout<<sum<<endl;

»
8 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Problems were more difficult than usual today.

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Atcoder Rand Contest.

This code passed Problem D. (Even though I tried 5 times)

...
bool dfs(int x) {
    if (clock() >= CLOCKS_PER_SEC * 1.95) {
        mt19937 rnd(random_device{}());
        cout << ((rnd() & 1) ? "Yes" : "No") << endl;
        exit(0);
    }
    ...
}
...
»
8 месяцев назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

Top 200 EZ

»
8 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Don't know if it was intended or not, but I guess the time limit is too loose for G. My $$$O(n^2/k)$$$ solution with a fast mod managed to squeeze into the time limit. XD

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to prune D?

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

    with ‌Backtracking.

    You can first solve this problem for learning backtrack. Eight queens puzzle

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well it turned out I shouldn't sort the tiles by increasing area. I should sort them in decrease

      Never mind

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 5   Проголосовать: нравится +9 Проголосовать: не нравится

    You don't really need to, there is a $$$O(n! \cdot 2^n \cdot H \cdot W)$$$ brute which fits into the time limit pretty easily.

    Basically, for all possible orders of the tiles, try all combinations of both possible orientations (initial or rotate 90) among all tiles and for each of them try to fit the grid using the following pseudocode:

    for i in [1, H]:
        for j in [1, W]:
            if (i, j) is not covered:
                try to place the next tile with its top left corner at (i, j)
    

    Code — 51308848

»
8 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Toughest ABC I've seen in a while, problem E feels tougher to me than most CF Div2E problems @_@.

»
8 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

F was easier than D :)

»
8 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

if you get wrong in c this because if there is a repetition of the letter, when you make a switch between the same letter, the resulting string calculates a new string just once. aab -> aab , baa , aba so the answer is 3 not 2 just do it before your code

for(int i = 0;i < s.size();i++){
    if(mp[s[i]] > 1){
        sum++;
        break;
     }
}
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for B ,why int(x/10) is wrong for negative ?

def solve(): x=int(input()) if x<=0: print(int(x/10)) else: if x%10!=0: print(x//10+1) else: print(x // 10)

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the test case of A should add "<=<=>=>".Almost all the solutions didn't conside this.

»
8 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

why can't we print Yes for this string in A "><==>"?

upd:Got it

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E is fantastic, and I spend about two hours and finally get it accepted. My idea is to use dpmax[j][0] = pair<color0, value0>, and dpmax[j][1] = pair<color1, value1> to denote that, until now, if we remove j balls, the optimal two values with color0 and color1 as the rightmost ball. Besides, we use dp[i][j] to denote the optimal value that we can get, if we consider the first i balls and remove j of them. dp[i][j] can be computed simply by using dpmax[j][0] and dpmax[j][1], and then we should update dpmax[j][0] and dpmax[j][1].

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why A is giving WA?

my code
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Atcoder, where are the testcases of abc344 & abc345?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where are the test cases atcoder_official