atcoder_official's blog

By atcoder_official, history, 9 months ago, In English

We will hold Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339).

We are looking forward to your participation!

  • Vote: I like it
  • -47
  • Vote: I do not like it

»
9 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Seems E,F is so difficult

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope AC ABCD.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The same to you.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I AC no problems in the contest and AC only ABCD in the visual contest. I think that you must be AC ABCD or more.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone! Is everyone ready to contest? I wish luck to everyone! :)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my first contest in AtCoder.Good luck for me!

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

If anyone solved problem E, please share your idea after the contest.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I traversed the array and for every Ai , finded the maximum among Ai-d , Ai+d and added 1 to it in the dp array of size 5e5.

    eg. 4 2
    3 5 1 2

    dp array = [0,0,0,0,0,0]
    started with 3 , maximum in dp array among [3-2 , 3+2] = [1,5] is 0 add 1 to it and put it at dp[3] = 1;

    dp array = [0,0,1,0,0,0]
    for 5 , maximum in dp array among [5-2,5+2] = [3,7] is 1 add 1 to it and put it at dp[5] = 2;

    dp array = [0,0,1,0,2,0]
    for 1 , maximum in dp array among [1-2,1+2] = [1,3] is 1 add 1 to it and put it at dp[1] = 2;

    dp array = [2,0,1,0,2,0]
    for 2, maximum in dp array among [2-2,2+2] = [1,4] is 2 add 1 to it and put it at dp[2] = 3;

    dp array = [2,3,1,0,2,0]
    Maximum among this is 3, Hence 3 is the maximum subsequence

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share your code, please?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          that is a Lazy Tag and A Segment Tree , Yes ? the other who upstairs tells is solved by dp , and upstairs didn't tell to you .

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Actually, dp array is the illustration. finding the maximum from (Ai-d) to (Ai+d) would give tle if simply traversed, therefore segment tree is used to find the maximum from (Ai-d) to (Ai+d).

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            In fact, the lazy tag doesn't matter, and the dp array is exactly the array maintained by the segment tree in my code.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We can optimize a dp solution: dp[i] = longest subsequence ending at ith index satisfying conditions

    the transition would be to consider all j < i such that abs(a[j] — a[i]) <= d but we notice that we only need to consider the last j such that a[j] <= a[i] and abs(a[j] — a[i]) <= d and the last j such that a[j] >= a[i] and abs(a[j] — a[i]) <= d

    i used a segment tree to manage these indices

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    I will try to explain my approach. As the elements are less than 5e5, you can maintain a dp over the element values (not indexes). For a given element x and max adjacent difference d, the element just before x (i.e. the previous element of the subsequence, if any) can be between x-d to x+d. I used a segment tree over the dp array, where the query returns the max value in the range mentioned. Then for the current element x, the max length of subsequence ending at that point will the be max value in range (x-d,x+d) + 1. Iterate over all elements in array and take the maximum as answer. Here's my code for reference: link

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may solve it with tree

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I AC nothing...

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Bad one

»
9 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I realized in the end that B is the recursion.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    More like simulation really

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 3   Vote: I like it -10 Vote: I do not like it
      void fun(vector<vector<char>> &a,int n,int x,char d,int i,int j,int h,int w){
      
      if(i==-1){
          i=h-1;
      }
      if(i==h){
          i=0;
      }
      if(j==-1){
          j=w-1;
      
      }
      if(j==w){
          j=0;
      }
      
      if(x==n) return;
      
      if(a[i][j]=='.'){
          // cell is white, paint it black and move it clockwise
          a[i][j]='#';
          if(d=='U'){
             d='R';
             fun(a,n,x+1,d,i,j+1,h,w);
          }
          else if(d=='D'){
              d='L';
              fun(a,n,x+1,d,i,j-1,h,w);
      
          }
          else if(d=='R'){
              d='D';
               fun(a,n,x+1,d,i+1,j,h,w);
      
          }
          else if(d=='L'){
              d='U';
               fun(a,n,x+1,d,i-1,j,h,w);
          }
      }
      else {
      
         a[i][j]='.';
          if(d=='U'){
             d='L';
             fun(a,n,x+1,d,i,j-1,h,w);
          }
          else if(d=='D'){
              d='R';
              fun(a,n,x+1,d,i,j+1,h,w);
      
          }
          else if(d=='R'){
              d='U';
               fun(a,n,x+1,d,i-1,j,h,w);
      
          }
          else if(d=='L'){
              d='D';
               fun(a,n,x+1,d,i+1,j,h,w);
          }
      
      
      
      
      
      }
      
      
      
      
      
      
      
      
      }
      
      
      
      LOL! Sure, here is my recursion. I may have made a simple problem tough to myself.
      Basically, I have also done the simulation, but I chose recursion, I would be happy to know another approach.
      
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C:

Why do input 4 -1 1000000000 1000000000 1000000000 Outputs 3000000000?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    start with 1, that's the minimum you can start with, because next stop is -1 and there after it is always positive

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh,it outputs the number of passengers at the end.

      I outputs the number of passengers at the beginning.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm writing it. Task E is interesting and easy

»
9 months ago, # |
  Vote: I like it +93 Vote: I do not like it

Trash Round.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Define $$$dp_{a_i}$$$ is the maximum subsequence ends at $$$a_i$$$. Its contributor values are the $$$dp$$$ values that ends in element from range $$$dp_{[a_i - d, a_i + d]}$$$ so we want to find the maximum $$$dp$$$ value within that range and add it by $$$1$$$ (by appending $$$a_i$$$ at the end of it). To get the maximum values of these $$$dp$$$, we can use segment tree

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are many nice variants that hint towards a solution for this one.

    This is a variant of LIS. Longest increasing subsequence is a problem that wants $$$i \lt j, a_j - a_i > 0$$$. Now you can imagine a similar problem where $$$a_j - a_i = D$$$. In this one it is $$$abs(a_j-a_i)<=D$$$. But eventually all variants are done in a similar fashion.

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

    Hints for E: Smooth Subsequence

    Start with the first DP definition that comes to mind.

    $$$dp[i]$$$ is the the maximum length of a smooth subequence ending at $$$i$$$.

    Our desired smooth subsequence has to end at some index. Hence, the answer would be $$$max(dp[i]$$$).

    How to perform transitions? Notice that the candidates for the second last element are $$$j < i$$$ such that $$$|a[i] - a[j] \leq d$$$. Hence, you can naively take contribution from all such $$$j$$$.

    Submission

    Now, If you're a beginner, most of the problems you might've solved so far would have applied DP on indices. However, it's possible to apply DP on values as well. Let's define an alternate DP definition.

    At any point of time, $$$dp[val]$$$ is the maximum length of a smooth subequence whose last element has value $$$val$$$.

    Suppose we insert elements one by one. What happens when you see the $$$i^{th}$$$ element for the first time. When an element enters, the subequences can be divided into 2 disjoint sets, one that ends at $$$i$$$ and the other that doesn't include $$$i$$$. By induction, we can assume that the for the subsequences not ending at $$$i$$$, their DP values would've been populated correctly. Now, how does $$$dp[a[i]$$$ vary? The possible candidates for the second last element are all $$$dp[old]$$$ such that $$$|old - a[i]| \leq d$$$. Hence, you can naively take contribution from them.

    Submision

    For the next part, if you are not familiar with Segment Tree, but understood the alternate DP definition on values, you can consider this problem as solved and come back to it later once you learn segment trees. There's no additional thinking required for the later parts, just blind use of template/library.

    Next, notice that you are taking contribution from a continuous range. More specifically, you are looking for a data structure that can support point update and range maxima. Hence, you can use segment tree to optimize it.

    Submission

    But if the template scares you, you can also use Atcoder Library's Segment Tree.

    Submission

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone AC problem G in $$$O(n \log{n} + q \log^2{n})$$$?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I solve it with merge sort tree.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    yes, link

    Note that it can be solved in $$$O(n \log n + q \log n)$$$ with persistent segtree: initialize segtree with 0s. then set add each element to the segtree in their order (first 1s, then 2s, then 3s...). for querying you can find the latest segtree that has elements <= x and query that tree.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I solve it with merge sort tree. n * log n for build it. (log n)^2 for answer to each query.

»
9 months ago, # |
  Vote: I like it +56 Vote: I do not like it

I think you can just copy G from somewhere else since the problem is so generic lol.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bfs and you need to keep track of both persons positions.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BFS, there are $$$O(n^4)$$$ nodes, each node represents the positions of both players. $$$dp[x1][y1][x2][y2]$$$ represents the minimum number of movees to get to a state where player 1 is at $$$(x1, y1)$$$ and player 2 is at $$$(x2, y2)$$$.

    Code

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When solving problem D using BFS (Breadth First Search), how can we ensure we don't traverse back? When we only have one dwarf, we usually use a 'visited' array to indicate whether we have traversed or not. But what about two dwarfs moving in the same direction? What should we do then?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    each node is of form x1,y1,x2,y2 so make a 4d array

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is using a 4D array the standard approach for this type of problem? In the competition, I initially thought of using a 4D array, but I'm concerned that this might waste a lot of unused space.

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        In fact a $$$60^4$$$ bool array only cost about 12.8MB

        So it doesn't matter

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that it is always best to not go back to a state where the 4-element tuple $$$(x_1, y_1, x_2, y_2)$$$ has shown up before. $$$x_1, y_1, x_2, y_2$$$ are the coordinates players 1 and 2 have moved to respectively.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share the idea behind problem F? I couldn't understand the approach mentioned in the video linked in the editorials tab.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If $$$a \cdot b = c$$$, then $$$a \pmod{m} \cdot b \pmod{m} = c \pmod{m}$$$. You can select some prime numbers as $$$m$$$, and check if they are same under those modulo. The more prime number you choose, the chance of collision will decrease.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Multiplication is expensive in that problem. They made it less expensive by picking a random mod and did the same bruteforce algorithm but with smaller numbers.

    I personally can't imagine the probability of collision but I assume when you have very big numbers, it's hard, when multiplied under same mod that their product will collide with some smaller number that you had in your array, given that you only have 1000 numbers in the array. You could probably force it to collide but not under a random modulus.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I saw some people pass F using Python, or you can implement bigint faster by using bitset to obtain the 1 / 64 constant.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I passed it with Python. At some point multiplications get too big (no number is as big as multiplication). You can sort the numbers and break when the biggest number in array is smaller than current product.

        You can also count the bit length $$$l_a$$$, bit length of product is at least $$$l_a+l_b-1$$$. The moment you don't have numbers with a particular bit length, you can also stop.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did D using multiple ways method, but I think I'm not right, can anyone share his/her smart idea

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BFS on every state that two player can be.

    the time complexity off this idea is the number of choose 2 cell of (n^2) cell.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Either you use FFT/Karatsuba in F or just AC with Python.

»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

E easier than D

»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Btw, I passed G in $$$O((n+q\log n)\sqrt{n})$$$ with Ofast, see here.

    Just need to fine tune the block length.

»
9 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Please stop making big integer problems like $$$F$$$ python people just make fun of cpp people :( like this

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The Easiest G Ever

Just a model of persistent segment tree

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This game requires almost no brain power. Just a constant stream of code. I think E and G are both original or extremely similar questions that have appeared elsewhere.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreeable

    But I used some silly references on priority_queue which increased my debugging time (will post it later)

    It cost much time that I have no time to solve F

»
9 months ago, # |
  Vote: I like it -26 Vote: I do not like it

trash contest. We don't need to think but we can AC all problem.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

there is actually a deterministic approach to solve F using python

Spoiler

my solution

»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I think the data of problem F is a little simple, such as the following code: https://atcoder.jp/contests/abc339/submissions/49968092

Input: 3 998244353 998242355 0

Correct output: 5

But that code outputs 14.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how to hack if you don't know the modulus he set? Even if he doesn't pass this question, he can change to a different modulus and submit and pass this question again.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It's meaningless to hack hashing algorithm in Atcoder contest, especially ABC.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the difficulity score of Problem D E F based on codeforces rating system?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think problem D is 1400 problem E is 1900 just because it have data structure and segment tree problem G is 1900 or 2000 as well

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I think it's a trash round. Problem F and G are too easy.

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

It's just the Goodbye 2023 on Atcoder. Imbalanced difficulty, existing problem, letting wrong solutions pass...

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the reason I didn't AK this contest.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm just wondering, what solution can be used to solve G if the queries can be answered offline?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I didn't solve it online, but I thought of a offline solution with a segment tree. You can sort the queries in descending order for the x values, and as you go through each query, insert the array values that are greater than the current x into the segment tree, then query the range of the segment tree to get the sum of elements in the range [l, r] that exceed the current x. Then you just take the sum of this subarray and subtract the sum of elements greater.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    persistent segment tree/wavelet matrix/merge sort tree can solve it online, but when talking about offline query, you can just use a simple point add range sum query segment tree with sweepline to solve it

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've created a tutorial and practice contest to help you understand how to solve it efficiently if the queries could be answered offline.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Problem E solved with dp + Fenwick Tree?

»
9 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Bad one

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

TemplateCoder.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my code only use 78 ms but i have a Runtime Error

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone point out the flaw in my logic for Problem D.

Approach :

Start a BFS from each player and maintain the count of no. of jumps in x and y coordinates required for each reachable cell.

Ex : dist1[i][j] --> stores no. of x jumps and y jumps from Player 1 in pair format.

Final answer : maximum of x jumps from player 1 and player 2 + maximum of y jumps from player 1 and player 2 --> for each reachable cell.

Submission : 50020473

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there is still no editorial yet?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc339/submissions/50118454

Any counter test for this solution of D

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi everyone, Why can't we solve problem D with DFS. I have applied DFS in all the four direction and caching the answer to avoid overlapping subcases. Here is my solution — https://atcoder.jp/contests/abc339/submissions/53169555