### chokudai's blog

By chokudai, history, 18 months ago, We will hold AtCoder Beginner Contest 196.

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

We are looking forward to your participation! Comments (52)
 » I can't believe I travelled into past !! Round 186.
•  » » fixed. thanks!
 » Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
•  » » How to solve D with BONUS: Solve for HW ≤ 200!?
•  » » » maybe you can solve it by bit dp
 » Only one color in the first AC :D » 18 months ago, # | ← Rev. 3 →   How to solve D ? I am getting WA in 5 cases . submission My approach was to brute forces all possible arrangements . In each function call i traversed the matrix row wise and i called next function as soon as i can fill some 2*1,1*2 or 1*1 tile. Could someone please provide a counter case ?
•  » » Not sure, but I think it is wrong because you count the ways you can lay the tiles, but asked is the number of different outcomes.
•  » » » Procedure was correct,I unnecessary printer $0$ when $a=0$. Most people have similar solution .We can prove that it won't over count .valid arrangement will have unique path (If we visualize the recursion as tree) reaching to it.
•  » »
•  » » » Thanks a lot Nots0fast ! . I thought that answer in that case would be 0 but it will be 1.
•  » » » can u please explain it little bit?
 » What's the expected solution for problem D? I wrote an $O(4^{2 \times min(H, W)} \times H ^ 2 \times W ^ 2)$ dp soln, but looking at the solve count I'm certain that it was totally overkill and I missed some easy approach.
•  » » D can be solved in O((3^(HW))*HW).
•  » » 18 months ago, # ^ | ← Rev. 2 →   Yeah it is !!I just wrote a plain brute force recursive solution and it passed in 6ms.Its complexity is O(3^(H.W)).
•  » » » do u need to fill 1*1,i guess just 2*1 is enough right
•  » » » » Yes, filling 2x1 matrix is enough. The remaining place will be filled by 1x1 dominos because of 2A+B=HW constraint.
•  » » I just wrote a most brute-force brute force which I don't know the complexity, and it passed.
•  » » I used recursion, numbered all cells and placed dominoes on them in strictly increasing order. This works very fast. solve(A, Map[][], Last): if A=0: res++ else while: find_cell_at_which_we_can_place_dominoe_2x1_starting_from(Last) place_dominoe() solve(A+1, NewMap[], NewLast) remove_dominoe() 
 » Problem F : https://www.codechef.com/problems/TASTRMAT
•  » » i used this blog https://codeforces.com/blog/entry/59386
 » How to solve E?
•  » » 18 months ago, # ^ | ← Rev. 2 →   Try to plot the graphs of some compositions, you can then prove that the final graph would either be a constant or something like this: $g(x) = \begin{cases} m*a + c & x\leq a \\ m*x + c & a\leq x\leq b \\ m*b + c & b\leq x \end{cases}$Next you know the maximum and minimum values of $g(x)$(values at $10^{18}$ and $-10^{18}$), then find $a$ and $b$ using binary search and finally $m$ and $c$. Answer queries in $O(1)$.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   Instead of using binary search we could also traverse the functions in reverse order (from n to 1) and maintain the the values of a(highest value of a[i] where t[i]=2) and b(lowest value of a[i] where t[I]=3). Code
•  » » » Can you explain how to apply binary search here.
•  » » » » We can apply binary search twice to find the upper lim and lower lim if they exist. For example to find upper limit, if cost_of_mid < upper limit , we increase l or else we decrease r in binary search. Here is an implementation
•  » » » In the editorial of F we have took -inf to inf value of x and also took the value of x as zero, and then processing further is this right or I am wrong here?also at the end of the solution in editorial how can we add value of x[i] to the value x(after processing)
•  » » » and in your solution above, what is m?how can we answer queries.. what to write?
•  » » We can notice a truth that if we sort the array by ascending, now assume we process an operation $t_i=2$($t_i=3$ is the same), all the elements less than $a_i$ will become $a_i$. So we can take all the elements less than $a_i$ from some data structure and union them with a new element, which's value is $a_i$. After that, we can put the new element into the data structure.So we can solve this problem off-line. We just need a set to restore all values and a data structure to union some elements. Because every element will be put into and taken out the set at most once, the total time complexity is $O(nlogn)$.See code for more details.
•  » » 18 months ago, # ^ | ← Rev. 4 →   My solution is similar to editorial, so I might explain the intuition. First observe that max(a + b, a + c) = a + max(b ,c). same holds for min Now we can convert each query to the form t[i] = 2 or t[i] = 3. Observe these queries are simple map of some range to some other so we start with L= -inf and R = inf and get the final mapping, add take care of extra addend. My submission https://atcoder.jp/contests/abc196/submissions/21104621Complexity for each query in online mode is O(1) .
 » Am I the only one that hard-coded a segment tree and used some binary search for solving E?(fortunately I didn't have bugs and got it:))
•  » » check this solution:solBy storing "max value" and "second max value" we can handle the query that need to min($a_i$,x) for every one $a_i$ and same for max($a_i$,x) query. It's called "势能线段树“ in Chinese but I don't know what's in English :/.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   I think it's Segment Tree Beats but I am not sure because I didn't learn it(I have a different solution).
•  » » » » Exactly this name I think.Thank you:)
•  » » I did a similar thing too, by storing range sum, max, and min — link
•  » »
 » How to Solve Problem C ? My code got TLE verdict during the round. My Code#include using namespace std; #define int int64_t #define mp make_pair #define pb push_back #define mod 1000000007 #define inf 1e18 #define N 20000007 int arr[N]; int32_t main() { int t; t=1; //cin>>t; while(t--) { int n; cin>>n; int count = 0; for(int i=10;i<=n;i++) { string str = to_string(i); if(str.length()%2!=0){ i=i*10; continue; } else{ string a,b; for(int i=0;i
•  » » Your approach will definitely timeout. N is very big and your solution is O(n). An O(|n|) solution passes. Where |n| is the length of the number (or string) n. Pick the largest digit that matches the condition(s) and is not greater than n. The answer is the first half.
•  » » » Can you please explain why |n| is efficient, I can see it is more efficient but just can't get the logic of taking only the largest digit lesser than n.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   For numbers with odd length, we would just make it even by using the greatest number less than n with even length. This is typically '9' in odd length-1 places.Now considering only cases with even length. We know that the left half must equal the right half. We also know that the left half concatenated with the right half must not exceed n. We must count all the numbers from 1 that when used as the left half and concatenated with itself, does not exceed nYou can refer to any video recap made by a high-rated participant if you still don't get it
•  » » » » » I got the logic now . Thanks for help
•  » » » » » check this code pls, I can't debug it.https://atcoder.jp/contests/abc196/submissions/21094340
 » Problem F: Substring 2Can someone tell me why a solution with O((n-m+1)m) complexity would not pass, rather get TLE, given that, m <= n <= 10^6 Time limit: 3 seconds
•  » » If m = n/2, the brute force complexity is n^2/4
•  » » » Aahhh, got it, thanks.Again, VLamarca, had it been 10^5 instead of 10^6, only then, this approach would fit inside the TL, am I right?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   I dont think so. The complexity would still be 2.5*10^9 But in this case you would probably be able to use bitset.
 » opps!
 » 18 months ago, # | ← Rev. 2 →   can anyone explain how to solve problem c?
 » Remember to use long long in problem E!
 » 18 months ago, # | ← Rev. 3 →   Can someone please give proof/reason of why the dfs for D will not count any possible arrangement(rotation or reflection) more than once?I guess most people are thinking that there is a unique path to each possible arrangement but I really don't get it, why it won't count a combination of reflection and rotation more than once. I figured out the dfs approach but I didn't did ans++, instead, I then try creating all 8 possible arrangements of each valid dfs leaf and create a set out of it and then insert it in a set of sets, finally size of set of sets is our answer. But it's too complicated and I couldn't finish coding it.Thanks!EDIT: sorry, I didn't read statement properly.
•  » » Here rotations and reflections are considered different arrangements and we should count them separately, so basic recursion will work.
•  » » » 18 months ago, # ^ | ← Rev. 3 →   Fuck! Thanks man!two ways are distinguished if they match only after rotation, reflection, or bothI read this as undistinguished :-(