chokudai's blog

Monoxer Programming Contest 2022（AtCoder Beginner Contest 238） Announcement
By chokudai, history, 2 years ago, In English

We will hold Monoxer Programming Contest 2022（AtCoder Beginner Contest 238）.

We are looking forward to your participation!

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

Comments Comments (19)
| Write comment?
»
2 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Problem E is really cool. I guess it might be standard for some, but it really was a wow moment for me when I realized it could be transformed into a reachability problem.

Also, Problem G. Just store freq modulo 3 instead of 2 obviously.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Yes! That was exactly my reaction. At first I tried really hard working with the segments. Subtracting them from each other to create atomar segments so it would be easy to check. And I wasn't able to create something subquadratic.

    But then suddenly the penny dropped. It has been DFS all along!

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

      Can you please tell me if this could be solved by DP. In my states, there was cycles, hence DP wasnt possible. I was wondering if there is such state.

      My state was that dp[ind]stores one if this is possible to reach from ind to n (final position).

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

        It is similar to bfs or dfs. If you are at the current node, then see if any node reachable from this node is possible or not. If at least 1 node reachable from this node is possible, then this node is also possible. If this node is possible, then all nodes reachable from this node are also possible and this way you recur for all children and update their values to possible. The only trick is if a node is already reachable then you don't visit this again, as this node would have already updated its children, just like normal dfs.

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

    G Cubic? $$$\equiv$$$ G. Three Occurrences

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with the problem C: Problem C I have tried an approach but it gives WA with numbers > 2^63-1 MY ATTEMPT:

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll int n, ans = 0; cin>>n;
    ll int i = 1;
    while((i * 10) <= n)
        i *= 10;
    for(int j = 1; j<n; j*=10){
        if(j==i) break;
        else ans+=(9*j)*(9*j+1)/2;
    }
    ans+=(n-i+1)*(n-i+2)/2;
    cout<<ans;
    return 0;
}

Please help

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

For Problem D, I referred this link.

So, the equation changed to $$$s - 2 * a = x \oplus y$$$. Then we can find non-negative integers $$$x, y$$$ as long as $$$s - 2 * a >= 0$$$.
(We can say $$$x = s - 2 * a,$$$ $$$y = 0$$$)

But this is giving me a wrong answer. Why is this condition not enough to find $$$x$$$ and $$$y$$$?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    It isn't always possible even if $$$s \geq 2 \cdot a$$$. Consider $$$a = 1, s = 3$$$.

    In this case, we will have to have the zero bit enabled in both $$$x$$$ and $$$y$$$, but there is now no way to get the remaining $$$1$$$ required.

    If a bit isn't on in $$$a$$$, it can only be enabled in at most one of $$$x$$$ or $$$y$$$. So the only way to satisfy the remaining bits of $$$s$$$ is we can enable each of them in exactly one of $$$x$$$ or $$$y$$$.

    So we also need to check that among the bits enabled in $$$s - 2 \cdot a$$$, none are enabled in $$$a$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think Ex is the best ABC problem.

→ Reply
»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Me coming up with literally nothing after 3 hours of thinking problem E, a cyan problem:

Atcoder Problems:

Spoiler

Ah yes, 16 minutes.

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

If anyone is looking for video editorials in English for problems A to E link

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Why in problem G using #pragma GCC optimize("Ofast") can make my code 2000ms faster?

Before: https://atcoder.jp/contests/abc238/submissions/29115540

After: https://atcoder.jp/contests/abc238/submissions/29119386

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to use atcoder libraries for local ? for practise purpose?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G: Solved using mos algorithm without using any pragma 29153484 — 1351 ms : For this one I am finding prime factors for each Ai. In next submission I tried to optimized it by not finding prime factors if I already have prime factor of same number. It takes more space as instead of initializing with global array of 2e5 , I am initializing global array of size 1e6 for storing prime factors but time increase is not that much as lowest time taken is 20ms. But instead of being faster it is 2s slower and gets TLE. 29153511 — 3309 ms. Is it because first one gets some weird compiler optimization or I am missing something?

→ Reply