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

Monoxer Programming Contest 2022（AtCoder Beginner Contest 238） Announcement
Автор chokudai, история, 3 года назад, По-английски

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

We are looking forward to your participation!

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

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

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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!

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

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

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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$$$?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I think Ex is the best ABC problem.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

Atcoder Problems:

Spoiler

Ah yes, 16 minutes.

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

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

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить