### chokudai's blog

By chokudai, history, 3 years 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!

• +48

| Write comment?
 » 3 years ago, # |   +20 I can't believe I travelled into past !! Round 186.
•  » » 3 years ago, # ^ |   +13 fixed. thanks!
 » 3 years ago, # |   +8 Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
•  » » 3 years ago, # ^ |   +4 How to solve D with BONUS: Solve for HW ≤ 200!?
•  » » » 3 years ago, # ^ |   0 maybe you can solve it by bit dp
 » 3 years ago, # |   +7 Only one color in the first AC :D
 » 3 years ago, # | ← Rev. 3 →   +1 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 ?
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ |   +3
•  » » » 3 years ago, # ^ |   0 Thanks a lot Nots0fast ! . I thought that answer in that case would be 0 but it will be 1.
•  » » » 3 years ago, # ^ |   +1 can u please explain it little bit?
 » 3 years ago, # |   +3 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.
•  » » 3 years ago, # ^ |   +3 D can be solved in O((3^(HW))*HW).
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Yeah it is !!I just wrote a plain brute force recursive solution and it passed in 6ms.Its complexity is O(3^(H.W)).
•  » » » 3 years ago, # ^ |   0 do u need to fill 1*1,i guess just 2*1 is enough right
•  » » » » 3 years ago, # ^ |   0 Yes, filling 2x1 matrix is enough. The remaining place will be filled by 1x1 dominos because of 2A+B=HW constraint.
•  » » 3 years ago, # ^ |   +4 I just wrote a most brute-force brute force which I don't know the complexity, and it passed.
•  » » 3 years ago, # ^ |   0 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() 
 » 3 years ago, # |   +3 Problem F : https://www.codechef.com/problems/TASTRMAT
•  » » 3 years ago, # ^ |   +8 i used this blog https://codeforces.com/blog/entry/59386
 » 3 years ago, # |   0 How to solve E?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +15 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)$.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » 3 years ago, # ^ |   0 Can you explain how to apply binary search here.
•  » » » » 3 years ago, # ^ |   0 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
•  » » 3 years ago, # ^ |   +4 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.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +3 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) .
 » 3 years ago, # |   +3 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:))
•  » » 3 years ago, # ^ |   +6 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 :/.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 I think it's Segment Tree Beats but I am not sure because I didn't learn it(I have a different solution).
•  » » » » 3 years ago, # ^ |   +3 Exactly this name I think.Thank you:)
•  » » 3 years ago, # ^ |   +3 I did a similar thing too, by storing range sum, max, and min — link
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 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.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 3 years ago, # ^ |   0 check this code pls, I can't debug it.https://atcoder.jp/contests/abc196/submissions/21094340
 » 3 years ago, # |   -10 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
•  » » 3 years ago, # ^ |   +4 If m = n/2, the brute force complexity is n^2/4
•  » » » 3 years ago, # ^ |   0 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?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 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.
 » 3 years ago, # |   0 opps!
 » 3 years ago, # | ← Rev. 3 →   +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.
•  » » 3 years ago, # ^ |   +1 Here rotations and reflections are considered different arrangements and we should count them separately, so basic recursion will work.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +3 Fuck! Thanks man!two ways are distinguished if they match only after rotation, reflection, or bothI read this as undistinguished :-(