Блог пользователя chokudai

Автор chokudai, история, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Atcoder Implementation contest :/

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

And I solved G today.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

G can be solved using bitset

Code
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how to solve E ?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

How to solve H?

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.