### chokudai's blog

By chokudai, history, 2 years ago, We will hold AtCoder Beginner Contest 204.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation! Comments (61)
| Write comment?
 » Similarly to the "Discuss" tab linking respective CF blogs for regular rounds, could you please consider adding one for beginner rounds as well?
 » It's very unfortunate that AtCoder beginner contests are happening on the same days as Codeforces contests with only ~1 hour gap between. Last week I tried to participate in AtCoder beginner contest 203 for the first time and this made me skip Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2). I maybe could have taken part in both contests if I didn't try to upsolve problems from the AtCoder contest after it ended, but instead opted to take a rest and eat something. By the time when the Codeforces contest was about to start, I was hungry and somewhat tired and still thinking about the problems from the other contest.Today it's the same situation and I need to choose between AtCoder and Codeforces contests again. Or maybe try to take part in both. What do the others do about it?
•  » » Take path in both and upsolve both later :)
 » 2 years ago, # | ← Rev. 2 →   How to solve E? I was trying to find the connection between the time cost and the basic inequality ($x+y\geq 2\sqrt{xy}$) but failed.
•  » » I thought of using dijkstra.For every road at time t most optimal time of starting is sqrt(d)-1 if t is already greater than this then go ahead otherwise make t = sqrt(d)-1 and calculate the ans.this approach passes for 30 testcases and gives wa on 5.https://atcoder.jp/contests/ABC204/submissions/23252742this is my submission can someone tell what is wrong with my approach.
•  » » » You should check sqrt(d) too, since sqrt(d) might not be integer. For example, in case of d = 3, 1 + floor(3 / 2) < 0 + floor(3 / 1).
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   that's why i have checked it in range sqrt + [-5,+5]
•  » » » » » Oh, I see. Sorry, when I reply I haven't read your code yet. Just read your idea in the comment. For WA, you get because you set the upper bound as 1e9, which isn't enough, imagine you walk through 2 edges with C = 1e9. For TLE, I'm not quite sure, but I think it's because you use set. I recommend you try PQ instead.
•  » » » » » » Ah shit!My disappointment is immeasurable and my day is ruined.BTW thank you
•  » » 2 years ago, # ^ | ← Rev. 7 →   Imagine we wait for $k$ seconds. Then time of arrival will be $t+k+c+\frac{d}{t+k+1}$. We want to minimise this term. We take the derivative to $k$ and obtain $1-\frac{d}{(t+k+1)^2}$. We set this 0 and solving for $k$ yields $k=\sqrt{d}-t-1$ (Or the final time $t_{arrive}=t+k=\sqrt{d}-1$). $k$ must be 0 or bigger, so we clamp it to 0. (also I checked all values $k \pm 2$ to find the minimum and ignore rounding errors)The rest is just dijkstra then.
•  » » » But this is just what your taking in moving only one step. Our path may consists of several edges too.Why are we not adding them all? And then how can we find derivative?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   The calculation is: If we are at time $t$ and node $A$ and want to use an edge with $C$ and $D$ to node $B$, then how long should we wait to minimize the cost. This minimum cost is the real cost of the edges. We can do this for all edges at all times. Then we can use Dijkstra. For the derivative I recommend you search for "Chain rule" and "Derive Polynomial". Alternativly you can use Ternary Search to find the minimum time. I think this should still fit into the time limit, I didn't try though.
•  » » » » 2 years ago, # ^ | ← Rev. 4 →   The fact is you don't need to, just use the simple inequality I mentioned before: $x+y \geq 2\sqrt{xy}$ (which is simply $A_n \geq G_n$)Proof: $x+y \ge 2 \sqrt{xy} \Leftrightarrow x-2\sqrt{xy}+y \ge 0 \Leftrightarrow (\sqrt{x} - \sqrt{y})^2 \ge 0$So, applying this, we get $t+k+c+\dfrac{d}{t+k+1} = (t+k+1+\dfrac{d}{t+k+1})-1+c \geq 2\sqrt{d}-1+c$The equality holds when $(t+k+1)^2=d$, so $k=\sqrt{d}-t-1$Fun fact: We call this function $f(x)=x+\dfrac{t}x$ the "Nike function" in some place in China because it looks like the Nike logo.
•  » » 2 years ago, # ^ | ← Rev. 2 →   The solution is using Dijkstra's with a minor twist. The wait time at each city can be decided by minimizing the function:f(x) = t+x+c+d/(t+x+1), where t is the time we reached the node and x is the amount of stay/wait time at that node.We can solve for the derivate f'(x). And that gives, x = sqrt(d)-t-1. Also, x>=0We can check for both ceil(x) and floor(x) and take the one which minimizes the total time f(x).
•  » » E is in first place dijkstra.But of course we cannt check all possible waiting times at each vertex.We can optimze this by finding the optimal time to start to use edge i is sqrt(D[i]), (or sqrt(D[i])+1). So, whenever we start to traverse an edge we check if current time is less that the optimal start time.Submission
•  » » My incorrect solution of ternary search passed, in that I used r-l>500 and it worked may due to weak tests
•  » » normal dijkstra , when you arrive at node v and want to traverse through edge i to node u , total cost is c[i] + (D[i] / (t+1)) + t we want to minimize (D[i]/(t+1)) + t , minimum is achieved at t = sqrt(D[i]).So now if current time when you arrive at v is t ,let x = max(t,sqrt(D[i]) we update u's time as C[i] + (D[i]/(x+1)) + x
•  » » Why can't we solve E question using ternary search? I tried solving using ternary search but 6 tc were failing. In editorial also it is written that we cannot solve it using ternary search but no reason is given.
•  » » » Hi,Did you figure out how to do it with ternary search?
•  » » » » YES
 » D was a harder version of this
•  » » 2 years ago, # ^ | ← Rev. 4 →   Easy D Solution#include #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);} int main(void){ fast; int n; cin>>n; int t[n],sum=0; for(int i=0;i>t[i]; sum+=t[i]; } bool dp[sum+1]={false}; dp=true; for(int i=0;i=0;j--){ if(dp[j]){ dp[j+t[i]]=true; } } } int i,ans=sum; for(i=1;i<=sum;i++){ if(dp[i]) ans=min(ans,max(i,sum-i)); } cout<
 » 2 years ago, # | ← Rev. 2 →   How to solve F ?I am sure we somehow have to utilize matrix exponentiation, but I am not sure how to build the matrix. It works somehow that we combine patters of the current column with possible following patterns (all submasks or the like), and then put somehow all pieces together.Somebody explain?
 » 2 years ago, # | ← Rev. 2 →   For F I wrote a dp for first 2 columns and then used matrix expo. Can anyone tell me what should I change in this code to make this work or is this approach itself is CODE (doesn't even pass the samples)// #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // using namespace __gnu_pbds; // template using oset =tree, rb_tree_tag,tree_order_statistics_node_update> ; using namespace std; // #pragma GCC optimize("Ofast") // #pragma GCC target("avx,avx2,fma") // #pragma GCC optimization ("unroll-loops") typedef long long ll ; typedef pair pii; typedef pair pll; #define CS custom_hash #define vt vector #define F first #define S second #define pb push_back #define em emplace_back #define stoi stoll #define all(v) (v).begin(),(v).end() #define mems(x, y) memset(x, y, sizeof(x)) #define sz(x) (int)(x).size() #define ar array #define endl "\n" #define PI acos(-1) #define umap unordered_map #define gmap gp_hash_table #define ld long double #define seb(n) __builtin_popcountll(n) #define LB lower_bound #define UB upper_bound // debugger credits: https://codeforces.com/blog/entry/68809 void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template void __print(const pair &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} template void mdebug(map>m){ for(auto x:m){ cerr << x.first << " : [ " ; for(auto c:x.second) cerr << c << " "; cerr << "]"<<'\n' ; } } #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // #pragma GCC optimize "trapv" //template credits :William Lin(tmwilliamlin168) #define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s)) #define F_OR1(e) F_OR(i, 0, e, 1) #define F_OR2(i, e) F_OR(i, 0, e, 1) #define F_OR3(i, b, e) F_OR(i, b, e, 1) #define F_OR4(i, b, e, s) F_OR(i, b, e, s) #define GET5(a, b, c, d, e, ...) e #define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1) #define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__) #define EACH(x, a) for (auto& x: a) template bool umin(T& a, const T& b) { return b bool umax(T& a, const T& b) { return a void read(vt& v); template void read(ar& a); template void read(T& x) { cin >> x; } void read(double& d) { string t; read(t); d=stod(t); } void read(long double& d) { string t; read(t); d=stold(t); } template void read(H& h, T&... t) { read(h); read(t...); } template void read(vt& x) { EACH(a, x) read(a); } template void read(array& x) { EACH(a, x) read(a); } string to_string(char c) { return string(1, c); } string to_string(bool b) { return b?"true":"false"; } string to_string(const char* s) { return string(s); } string to_string(string s) { return s; } string to_string(vt v) { string res; FOR(sz(v)) res+=char('0'+v[i]); return res; } template string to_string(bitset b) { string res; FOR(S) res+=char('0'+b[i]); return res; } template string to_string(T v) { bool f=1; string res; EACH(x, v) { if(!f) res+=' '; f=0; res+=to_string(x); } return res; } template void pff(A x) { cout << to_string(x); } template void pff(const H& h, const T&... t) { pff(h); pff(t...); } void print() { pff("\n"); } template void print(const H& h, const T&... t) { pff(h); if(sizeof...(t)) pff(' '); print(t...); } struct PH{ size_t operator()(const pair&x)const{ size_t ans=0; for(int i=0;i> 30)) * 0xbf58476d1ce4e5b9; // x = (x ^ (x >> 27)) * 0x94d049bb133111eb; // return x ^ (x >> 31); // } // size_t operator()(uint64_t x) const { // static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // return splitmix64(x + FIXED_RANDOM); // } // }; // void DBG() { // cerr << "]" << endl; // } // template void DBG(H h, T... t) { // cerr << to_string(h); // if(sizeof...(t)) // cerr << ", "; // DBG(t...); // } // // #ifdef _DEBUG // #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) // // #else // // #define dbg(...) 0 // // #endif template void offset(ll o, T& x) { x+=o; } template void offset(ll o, vt& x) { EACH(a, x) offset(o, a); } template void offset(ll o, ar& x) { EACH(a, x) offset(o, a); } template void fk(T a) { print(a) ; exit(0) ; } #define pf(n) return print(n) #define int ll long const M=998244353 ; const ll INF =1e18; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). //Syntax to create a min heap for priority queue // priority_queue , greater>pq ; //make sure to clear the adjacency list for every test case // check mxN size //check if numbers are big use powl,sqrtl,builtin_popcountll()...... const int mxN=1e5,di={1,0,-1,0},dj={0,-1,0,1}; int dp,dp1 ; ll mat,aux ; void multiply(ll a,ll b){ FOR(i,2)FOR(j,2)aux[i][j]=0; FOR(i,2)FOR(j,2)FOR(k,2)aux[i][j]=(aux[i][j]+(a[i][k]%M*b[k][j]%M)%M)%M; FOR(i,2)FOR(j,2)a[i][j]=aux[i][j] ; } ll P,OP,F ; void mat_pow(ll N){ if(N==1) return; mat_pow(N/2); multiply(P,P); if(N&1) multiply(P,OP); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m ;read(n,m) ; dp=1 ; dp=2 ; FOR(i,3,20) dp[i]=(dp[i-1]+dp[i-2])%M ; dp1=2 ; dp1=7 ; dp1=1 ; FOR(i,3,20){ dp1[i]=(2*dp1[i-1]%M+dp1[i-2])%M ; for(int j=i-2;~j;--j) (dp1[i]+=2*dp1[j]%M)%=M ; } int A = dp[n] ; int B = dp1[n]-A*A ; debug(A) ; debug(B) ; P=A%M;P=B%M;P=1;P=0 ; F=m%M ;F=0 ; FOR(i,2)FOR(j,2)OP[i][j]=P[i][j] ; mat_pow(m-2) ; print((P*dp1[n]+P*dp[n])%M) ; debug(dp1) ; } wrong?
 » 2 years ago, # | ← Rev. 3 →   How to solve F? I only know the naive DP Bitmask O(2^n*m)UPD: I just learnt that such a DP can be optimised using matrix multiplication and binary exponentiation. What a pity that this is the first time I learn this trick and only after the contest :(This naive solution can be optimised to this
•  » » you can use matrix exponentiation to reduce m term to log(m)
 » 2 years ago, # | ← Rev. 2 →   Why in E have to wait in city until nearly sort(d) time?And how to solve F?
•  » » My approach was to use differentiation. Let T to be the time arrived at a vertex, and t to be the waiting time. Then to move onto the next vertex, it will take f(t) = t+ C + D/(T+t+1). If you see this as a function of t, then we find the first derivative which would be 1 — D/(T+t+1)^2, and when the first derivative is zero, the original function would be minimum. Hence, t = sqrt(D) -1-T.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   We have to minimise total time right from 1 to N. So, let it start from 1 at T and let t,t[x],.... t[N] be waiting time on every vertex from 1 to N path which will give answer optimally.then we have to minimise T + (t + C+ d/(T+1)) + (t+C+ d/(T + (t + C+ d/(T+1)))) .... and so on.Isn't it? Why we are using Greedy instead of DP type solution?
•  » » » » I think it is because that as long as you arrive at a vertex early, then you can simply wait it out until the cost function is minimized. So the greedy approach (dijkstra) works.
•  » » » » » Let's say t1, t2 are the times to reach some node A st, t1 sqrt(di). Then how will you prove that t1 will be optimal to choose?
•  » » » » » » Then it should be t1 because the first derivative will be always positive when t is greater than sqrt(di), so the cost function would be increasing,hence the minimal time should be optimal
•  » » » » » » » Agreed. Thanks for the explanation
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   May be at first, we see that the states are node and time t at which we start our journey from here. But for all t < sqrt(di), it is always optimal to go to next node at sqrt(Di) (or some plus or minus 1 from this) as that will give the minimum time to reach the next node through this node. If t > sqrt(di) (where it had been optimal to arrive at next node), then we can do no good other than to directly go to next node as waiting will further increase the time to reach next node. So, it is good for us to directly maintain minimum time to reach each node as if that minimum time is greater than sqrt(Di) for a edge, we can do not good than this to reach next node through present node.
•  » » 2 years ago, # ^ | ← Rev. 2 →   The short explanation is, that before t=sqrt(D[i]) each second waiting gives back 1 or more second less travel time, and after t=sqrt(D[i]) each second waiting gives back only 1 or less second.
 » I think berlekamp massey can be used in F, am i right??
•  » » Yes, I used a 4 state dp to generate 144 terms for each width, and depending on which width is given, I used Berlekamp Massey. My code is a bit ugly though: https://atcoder.jp/contests/abc204/submissions/23248639Here is the dp code I used to generate the terms : https://www.ideone.com/48ZQxf
•  » » » Nice, I had the exact same idea but for small values I was stupidly using backtracking, should have gone for bitmask dp. thanks btw.
 » I realized today a strong weakness of binary and ternary searches on non-strict convex functions. Tried so hard to get E pass, but couldn't get past 26 AC :(
 » Can somebody explain that why didn't ternary search work in finding the best time to move in E ?
•  » » Yes, because the function was not strictly decreasing and then strictly increasing. For instance, I tried this predicate f(mid) > f(mid + 1), which is not monotonous when the function is like a staircase, as in for eg: decrease — stays constant, decrease, increase — stay constant, increase.
•  » » 2 years ago, # ^ | ← Rev. 2 →   For me, the ternary search only passed ~ 20 cases. I think ternary search is not working since the floor of the division is not monotonous. For example 6/4 = 6/5 = 6/6. Hence increasing the denominator from 4 to 6 kept the floor of the division the same.
•  » » It actually does work if you don't floor the second summand in the expression. My submission.
•  » » » That is genius in a way. Why didn't I think of doing that of all weird things I was doing. Ah, excellent problem anyway.
 » Can anyone explain Task E's approach ???can anyone recommend me a similar type of (graph)/(shortest path) problems?
 » I found someone else's solution using greedy for problem D.https://atcoder.jp/contests/abc204/submissions/23253738
•  » » Why is this solution wrong?https://atcoder.jp/contests/ABC204/submissions/23234922
•  » » » 8 16 14 13 13 12 10 9 3 Correct answer is 45, while your code outputs 48.
•  » » Weak Tests Counter test for this submission3 9 4 3 Actual solution : 9Solution that this submission prints : 8
•  » » » Nope, this solution also gives 9
•  » » » » Oh, I think there is some misunderstanding, I am replying to alwyn
 » how to solve C?
•  » » make every city as starting point (start dfs from every city) and see how many cities you can visit for that starting point.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   Or if you are in mood of mememing around, you can do scc + dag condensation + bitsets (ironically which I did)
 » Does anyone know why this solution fails on 3 tests? -> https://atcoder.jp/contests/abc204/submissions/23262102
•  » » Because your define int long long is not before typedef pair pii, which will lead to overflow.
•  » » » Great work :D
 » Here's a problem similar to E in terms of the minimizing the function, since the proof part in the AtCoder isn't up yet, you can refer to the editorial of this problem for the proof. 1288A - Deadline
 » While solving F, I got dp with broken profile vibes. But the state mapping was simpler.
 » 2 years ago, # | ← Rev. 4 →   My code for E — Rush Hour 2 is getting TLE on one case. This is my code-Submission Can somebody point out the error please?Edit 1: The same solution with set instead of Priority Queue is giving AC. Submission I can't understand the reason.Edit 2: I understood the reason