chokudai's blog

AtCoder Beginner Contest 258 Announcement
By chokudai, history, 2 years ago, In English

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!

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

Comments Comments (34)
| Write comment?
»
2 years ago, # |
  Vote: I like it +37 Vote: I do not like it

G is a well-known problem, see https://youtu.be/BJhzd_VG61k?t=3841

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

    You can use bitsets too. It's much more easier to implement.

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

    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.

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

Atcoder Implementation contest :/

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

LoL dude I took a class Big Data Processing and learned counting triangles this spring semester.

And I solved G today.

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

G can be solved using bitset

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

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

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

    how to solve E ?

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

      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.

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

        Can you share the link to your code , I want to see how to use binary lifting for this case .

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

        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.

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

        can you please explain a bit more? can't properly grasp what's happening

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

      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.

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

      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.

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

Problem C : https://mirror.codeforces.com/problemset/problem/1681/B

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

What is the observation or logic behind problem F? I even don't know how to start the first step to analyze this problem :(

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

Is there a solution to G — Triangle without using bitset?

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

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 1
Code 2

PS:- Found the mistake. In code 2 I need to reverse the string before converting it to bitset.

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

Anybody can help me with the B problem. I couldn't figure it out till the end.

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

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

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

Can somebody tell what is the approach used in E to find the k th box's weight

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

    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 lifting

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

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

      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?

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

        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.

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

Will the test cases for recent abc's not get added to the dropbox?

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

How to solve H?

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

    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$$$ and
    1. $$$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

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

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Input
    your output
    correct output
    → Reply