Monoxer Programming Contest 2022（AtCoder Beginner Contest 238） Announcement

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

Автор chokudai, история, 2 года назад, По-английски

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

Contest URL: https://atcoder.jp/contests/abc238
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220205T2100&p1=248
Duration: 100 minutes
Number of Tasks: 8
Writer:kyopro_friends,penguinman,physics0523,YoshikaMiyafuji
Tester:Kodaman,leaf1415
Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

chokudai
2 года назад
21

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

Показать архивные | Написать комментарий?

ExplodingFreeze

2 года назад, # |

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

→ Ответить

OleschY

2 года назад, # ^ |

+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!

→ Ответить

focusO_o

2 года назад, # ^ |

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

→ Ответить

tiasmondal

2 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

aryanc403

2 года назад, # ^ |

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

→ Ответить

tenzen

2 года назад, # |

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

→ Ответить

madlogic

2 года назад, # ^ |

MOD 998244353

→ Ответить

tenzen

2 года назад, # ^ |

It is still showing SIGTERM when I ran it for testcase 3

→ Ответить

BeruboIV

2 года назад, # |

← Rev. 2 →

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

→ Ответить

ExplodingFreeze

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

→ Ответить

BeruboIV

2 года назад, # ^ |

Thanks!

→ Ответить

lin7xu

2 года назад, # |

I think Ex is the best ABC problem.

→ Ответить

EasonCookie197

2 года назад, # |

+34

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

Atcoder Problems:

Spoiler

Ah yes, 16 minutes.

→ Ответить

wraith_11

2 года назад, # |

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

→ Ответить

BARBARIANNNNN

2 года назад, # |

← Rev. 2 →

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

→ Ответить

aryanverma2621

2 года назад, # |

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

→ Ответить

WaterColor2037

2 года назад, # ^ |

Here is the official announcement that includes the link to the source code zip. But actually the code is stored and maintained in GitHub, which includes some bugfixes.

→ Ответить

spookywooky

2 года назад, # ^ |

There is a script included, expander.py It can be used to create a source file with the atcoder includes actually included, so the result (combined.cc) can be submitted on all other judges. See https://atcoder.github.io/ac-library/production/document_en/appendix.html

If you integrate the script into your standard compile command it simply works. I use it regularly.

→ Ответить

bashem

2 года назад, # |

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?

→ Ответить