atcoder_official's blog

Monoxer Programming Contest 2024（AtCoder Beginner Contest 345） Announcement
By atcoder_official, history, 8 months ago, In English

We will hold Monoxer Programming Contest 2024（AtCoder Beginner Contest 345）.

We are looking forward to your participation!

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

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

Good luck to everyone!

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

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

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

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

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

ABC345? Increasing sequence?

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

contest questions are in japanese language?

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

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

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

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.

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

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)

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

How C

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

      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?

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

        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.

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

      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;

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

Problems were more difficult than usual today.

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

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);
    }
    ...
}
...
→ Reply
»
8 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Top 200 EZ

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

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

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

How to prune D?

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

    with ‌Backtracking.

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

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

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

      Never mind

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

    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

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

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

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

    was E dp+segment tree?

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

      To be honest, I don't know. I have an $$$O(n \cdot k)$$$ dp but its getting 5xWA and I'm still not sure where my logic is incorrect.

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

      I ended up creating a video editorial for this problem. Here

      Do take some pauses before jumping between chapters. Each chapter adds one optimisation to move one step closer.

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

F was easier than D :)

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

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;
     }
}
→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

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

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

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

upd:Got it

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

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].

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

Why A is giving WA?

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

Atcoder, where are the testcases of abc344 & abc345?

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

where are the test cases atcoder_official

→ Reply