### chokudai's blog

By chokudai, history, 5 weeks ago,

We will hold AtCoder Beginner Contest 258.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

• +65

 » 5 weeks ago, # |   +37 G is a well-known problem, see https://youtu.be/BJhzd_VG61k?t=3841
•  » » 5 weeks ago, # ^ |   -14 just knew it was some standard bs
•  » » 5 weeks ago, # ^ |   +10 You can use bitsets too. It's much more easier to implement.
•  » » 5 weeks ago, # ^ |   +25 Well, this solution has complexity $O(M*sqrt(M))$ where $M$ can be $N^2$. Thus, I don't think this solution with $O(N^3)$ complexity will work.
•  » » » 5 weeks ago, # ^ |   +5 Just noticed many $O(N^3)$ solutions passed.Example
 » 5 weeks ago, # |   +19 Atcoder Implementation contest :/
•  » » 5 weeks ago, # ^ |   0 Yes, ABC will be AIC.
 » 5 weeks ago, # |   0 LoL dude I took a class Big Data Processing and learned counting triangles this spring semester.And I solved G today.
 » 5 weeks ago, # |   0 G can be solved using bitset Code#include using namespace std; typedef long long int lli; typedef long double ld; #define plli pair #define pb push_back #define fir first #define sec second #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); lli mod=(1000*1000*1ll*1000)+7; constexpr lli inf=4ll*(((1000*1000*1ll*1000)*(1000*1000*1ll*1000))+50); constexpr lli N=3010; bitset b[N]; using blli = bitset; int main() { fastio lli T,i,j; T=1; // cin>>T; while(T--) { lli n; cin>>n; vector s(n); vector val(n); for(i=0;i>s[i]; for(j=0;j
 » 5 weeks ago, # |   +6 Thanks for the contest, Problem E was great :) even couldn't solve it in the contest due to a small bug in my code but I enjoyed solving it :)
•  » » 5 weeks ago, # ^ |   0 how to solve E ?
•  » » » 5 weeks ago, # ^ |   +1 You can precompute the number of potatoes in a box if you start with the $i$'th potato, and then use binary lifting to quickly find which potato the $K$'th box starts with.
•  » » » » 5 weeks ago, # ^ |   0 Can you share the link to your code , I want to see how to use binary lifting for this case .
•  » » » » » 5 weeks ago, # ^ |   0
•  » » » » » » 5 weeks ago, # ^ |   0 I forgot to put the ll in (1ll<
•  » » » » 5 weeks ago, # ^ |   +9 You don't really need binary lifting to figure out the starting point, there will be a few initial starting points, and after that, we will get a cycle so we can simply find out the starting point based on k%cycleSize.
•  » » » » 5 weeks ago, # ^ |   0 can you please explain a bit more? can't properly grasp what's happening
•  » » » 5 weeks ago, # ^ |   +5 Notice that there can be atmost N start points across all boxes , so you will get a cycle of length almost N so now , for each N cycles you can find the no. Of gifts(or whatever it was) in that box in LogN time. And during query print the answer corresponding to that box.
•  » » » 5 weeks ago, # ^ |   +2 Taking the sample test case : 3 2 5 3 4 1 1 2 ordering of filling would be : (0 + 1), (2 + 0 + 1), (2 + 0 + 1), (2 + 0 + 1), ...If we observe that the order filling of potatoes in the boxes would repeat after a period. Here the order of filling started repeating after 2nd box.so, we would need to find the index from the order, start repeating, and the size of the cycle.And for answering the query in O(1) we can precompute the order of filling till the cycle.Here is my solution.
 » 5 weeks ago, # |   +8
 » 5 weeks ago, # |   0 What is the observation or logic behind problem F? I even don't know how to start the first step to analyze this problem :(
 » 5 weeks ago, # |   0 Is there a solution to G — Triangle without using bitset?
•  » » 5 weeks ago, # ^ |   0
•  » » » 5 weeks ago, # ^ |   0 See this comment
•  » » 5 weeks ago, # ^ |   0 There're some variations on A@A*A/6 for python with numpy matrix operations.
 » 5 weeks ago, # | ← Rev. 2 →   0 For problem G — Triangle. I was trying to solve it using bitset. Can any one explain why Code 1 is giving correct output while code 2 is giving wrong output? Code 1const int N=3001; vt> edge(N); void solve() { int n; cin>>n; For(i, 0, n) { string s; cin>>s; For(j, 0, n) { if(s[j]=='1') { edge[i][j]=1; } } } int ans=0; For(i, 0, n) { For(j, i+1, n) { if(edge[i][j]) { ans+=(edge[i]&edge[j]).count(); } } } cout<> edge(N); void solve() { int n; cin>>n; For(i, 0, n) { ST s; cin>>s; edge[i]=bitset(s); } int ans=0; For(i, 0, n) { For(j, i+1, n) { if(edge[i][j]) { ans+=(edge[i]&edge[j]).count(); } } } cout<
 » 5 weeks ago, # |   0 Anybody can help me with the B problem. I couldn't figure it out till the end.
•  » » 5 weeks ago, # ^ |   0 Since the grid is fairly small we can solve the problem by brute force. Just check each direction starting at each position, which runs foreach direction in $O(N^3)$
 » 5 weeks ago, # |   +1 Can somebody tell what is the approach used in E to find the k th box's weight
•  » » 5 weeks ago, # ^ |   0 In E we need to observe that the potato sizes $w[]$ define a linked list, where each element points to the first potato of the next box. Find the number of each box by binary searh in $O(logn)$With this linked list, the problem asks basically for the $(K-1)$-th successor of the first element. This can be solved by binary liftingAn alternative solution instead of binary lifting can also be construct. We see that starting from first element the linked list leads into a circle at some time. So, there is kind of a tail of size $y$ leading into a circle of size $x$.If $K<=y$ then answer is the K-th vertex in the tail, else it is the $((K-y)\%x)$-th vertex of the circle.
•  » » » 5 weeks ago, # ^ |   0 Can you please explain why you have used the parent of initial j th element as distance from start but not the size of the box having x weight starting from i?
•  » » » » 5 weeks ago, # ^ |   0 I think it is the same. The linked list points at each position i to the first potato j of the next box if i was the first potato in the box.So j=i+size, but also j is the absolute distance from the first potato.
 » 5 weeks ago, # |   0 Will the test cases for recent abc's not get added to the dropbox?
 » 5 weeks ago, # |   +17 How to solve H?
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +3 Firstly, lets think about the corner case: $N = 0$.We need to split $S$ into odd terms. Define $f(n)$ — number of "odd" splits of n.We can calculate $f(n)$ using DP (fix first term): $f(n)=f(n-1)+f(n-3)+\ldots$ $f(n-2) = f(n-3)+f(n-5) + \ldots$ $\Rightarrow f(n)=f(n-1)+f(n-2)$Ok, these are just Fibonacci numbers, we can calculate them using the standard matrice approach in $O(\log X)$. Now, we can image this problem as in the picture below:We need to select a few available positions of prefix sums for our array (maybe 0) and make sure that the difference of the neighboring ones (these are exactly the elements of the array) is odd. Firstly, insert $0$ and $X$ into $A$.We can calculate $dp[i][j]$ — number of ways to select free positions $0 < p_1 < p_2 < \ldots < p_k < A_i$ and1. $p_i - p_{i-1} \equiv 1 \mod 2$2. $A_i - p_k \equiv j \mod 2$.Then, $dp[N][1]$ is answer. To recalculate $dp[i+1]$, in fact, we need to solve this task with $N=0$. This is quite simple to do using the comments above. It may be necessary to consider several cases, but they are essentially the same.Sample code
 » 5 weeks ago, # |   0 Hey can someone help me out with problem E, I am not able to understand where I am going wrong, this is my Submission, any counter case will also help.
•  » » 5 weeks ago, # ^ |   +8 Input2 1 1001 11 your output101 correct output100
•  » » » 5 weeks ago, # ^ |   0 thanks, I will see what I am doing wrong
•  » » » 5 weeks ago, # ^ |   0 thanks man, found out my mistake and got it accepted