We will hold AtCoder Beginner Contest 196.

- Contest URL: https://atcoder.jp/contests/abc196
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210320T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: beet, evima, kyopro_friends, QCFium, tatyam
- Rated range: ~ 1999

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

We are looking forward to your participation!

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

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.

here, https://atcoder.jp/contests/abc196/submissions/21107210

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

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.

Problem F : https://www.codechef.com/problems/TASTRMAT

i used this blog https://codeforces.com/blog/entry/59386

How to solve E?

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:

$$$

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

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

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.

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/21104621

Complexity 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:sol

By 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 :/.

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

This is mine: https://atcoder.jp/contests/abc196/submissions/21106507

How to Solve Problem C ? My code got TLE verdict during the round.

My CodeYour 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.

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 n

You can refer to any video recap made by a high-rated participant if you still don't get it

check this code pls, I can't debug it.

https://atcoder.jp/contests/abc196/submissions/21094340

Problem F: Substring 2

Can someone tell me why a solution with

O((n-m+1)m)complexity would not pass, rather getTLE, given that,`10^6`

3 secondsIf m = n/2, the brute force complexity is n^2/4

Aahhh, got it, thanks.

Again, VLamarca, had it been

10^5instead of10^6, only then, this approach would fit inside the TL, am I right?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!

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.

Fuck! Thanks man!

`two ways are distinguished if they match only after rotation, reflection, or both`

I read this as undistinguished :-(