chokudai's blog

AtCoder Beginner Contest 196 Announcement
By chokudai, history, 3 years ago, In English

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!

  • Vote: I like it
  • +48
  • Vote: I do not like it

Comments Comments (47)
| Write comment?
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I can't believe I travelled into past !! Round 186.

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    How to solve D with BONUS: Solve for HW ≤ 200!?

    → Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Only one color in the first AC :D

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot Nots0fast ! . I thought that answer in that case would be 0 but it will be 1.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      can u please explain it little bit?

      → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    D can be solved in O((3^(HW))*HW).

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Yeah it is !!

    I just wrote a plain brute force recursive solution and it passed in 6ms.

    Its complexity is O(3^(H.W)).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do u need to fill 1*1,i guess just 2*1 is enough right

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, filling 2x1 matrix is enough. The remaining place will be filled by 1x1 dominos because of 2A+B=HW constraint.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I just wrote a most brute-force brute force which I don't know the complexity, and it passed.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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()
    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how to apply binary search here.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My Code
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Problem F: Substring 2

Can 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
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

opps!

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Here rotations and reflections are considered different arrangements and we should count them separately, so basic recursion will work.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Fuck! Thanks man!

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

      I read this as undistinguished :-(

      → Reply