Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contes...

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

We are looking forward to your participation!

• 12 hours ago, # ^ | DO NOT try to evaluate the difficulty of a task based on its point value. It's often inaccurate.

  • 4 hours ago, # ^ | I don't know why people are downvoting you

    • 3 hours ago, # ^ | It is not often inaccurate; rather, it is sometimes inaccurate.

      • 3 hours ago, # ^ | ← Rev. 2 →   0 who is nandini bro :) ?

  • • 50 minutes ago, # ^ | Tasks were too easy.

• 3 hours ago, # ^ | The same to you.

• 4 hours ago, # ^ | The same to you

• 88 minutes ago, # ^ | ← Rev. 2 →   +1 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

• 88 minutes ago, # ^ | ← Rev. 2 →   0 Spoiler

• 87 minutes ago, # ^ | 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

• 84 minutes ago, # ^ | ← Rev. 3 →   +2 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

• 81 minute(s) ago, # ^ | you may solve it with tree

• 90 minutes ago, # ^ | More like simulation really

• 89 minutes ago, # ^ | start with 1, that's the minimum you can start with, because next stop is -1 and there after it is always positive

  • 78 minutes ago, # ^ | Oh,it outputs the number of passengers at the end. I outputs the number of passengers at the beginning.

• 83 minutes ago, # ^ | Define dpaidpai is the maximum subsequence ends at aiai. Its contributor values are the dpdp values that ends in element from range dp[ai−d,ai+d]dp[ai−d,ai+d] so we want to find the maximum dpdp value within that range and add it by 11 (by appending aiai at the end of it). To get the maximum values of these dpdp, we can use segment tree

• 81 minute(s) ago, # ^ | ← Rev. 2 →   0 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<j,aj−ai>0i<j,aj−ai>0. Now you can imagine a similar problem where aj−ai=Daj−ai=D. In this one it is abs(aj−ai)<=Dabs(aj−ai)<=D. But eventually all variants are done in a similar fashion.

• 79 minutes ago, # ^ | Hints for E: Smooth Subsequence Start with the first DP definition that comes to mind. dp[i]dp[i] is the the maximum length of a smooth subequence ending at ii. Our desired smooth subsequence has to end at some index. Hence, the answer would be max(dp[i]max(dp[i]). How to perform transitions? Notice that the candidates for the second last element are j<ij<i such that |a[i]−a[j]≤d|a[i]−a[j]≤d. Hence, you can naively take contribution from all such jj. 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]dp[val] is the maximum length of a smooth subequence whose last element has value valval. Suppose we insert elements one by one. What happens when you see the ithith element for the first time. When an element enters, the subequences can be divided into 2 disjoint sets, one that ends at ii and the other that doesn't include ii. By induction, we can assume that the for the subsequences not ending at ii, their DP values would've been populated correctly. Now, how does dp[a[i]dp[a[i] vary? The possible candidates for the second last element are all dp[old]dp[old] such that |old−a[i]|≤d|old−a[i]|≤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

• 81 minute(s) ago, # ^ | I solve it with merge sort tree.

  • 78 minutes ago, # ^ | I also tried with merge sort tree in O(log2n)O(log2⁡n) per query but it kept TLEing.

    • 75 minutes ago, # ^ | You can use zkw segment tree to speed up. submission

      • 73 minutes ago, # ^ | What is zkw segemnt tree?

  • 64 minutes ago, # ^ | ← Rev. 2 →   0 Sqrt Decomposition is the easiest solution and surprisingly it passed!

• 81 minute(s) ago, # ^ | ← Rev. 3 →   +2 yes, link Note that it can be solved in O(nlogn+qlogn)O(nlog⁡n+qlog⁡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.

• 81 minute(s) ago, # ^ | Bfs and you need to keep track of both persons positions.

  • 80 minutes ago, # ^ | I did something like dijkstra and it TLE'd.

• 80 minutes ago, # ^ | BFS, there are O(n4)O(n4) nodes, each node represents the positions of both players. dp[x1][y1][x2][y2]dp[x1][y1][x2][y2] represents the minimum number of movees to get to a state where player 1 is at (x1,y1)(x1,y1) and player 2 is at (x2,y2)(x2,y2). Code

• 79 minutes ago, # ^ | each node is of form x1,y1,x2,y2 so make a 4d array

  • 60 minutes ago, # ^ | 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.

    • 52 minutes ago, # ^ | ← Rev. 2 →   0 In fact a 604604 bool array only cost about 12.8MB So it doesn't matter

• 78 minutes ago, # ^ | Note that it is always best to not go back to a state where the 4-element tuple (x1,y1,x2,y2)(x1,y1,x2,y2) has shown up before. x1,y1,x2,y2x1,y1,x2,y2 are the coordinates players 1 and 2 have moved to respectively.

• 70 minutes ago, # ^ | If a⋅b=ca⋅b=c, then a(modm)⋅b(modm)=c(modm)a(modm)⋅b(modm)=c(modm). You can select some prime numbers as mm, and check if they are same under those modulo. The more prime number you choose, the chance of collision will decrease.

• 67 minutes ago, # ^ | ← Rev. 3 →   0 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.

  • 52 minutes ago, # ^ | I saw some people pass F using Python, or you can implement bigint faster by using bitset to obtain the 1 / 64 constant.

    • 48 minutes ago, # ^ | 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 lala, bit length of product is at least la+lb−1la+lb−1. The moment you don't have numbers with a particular bit length, you can also stop.

• 46 minutes ago, # ^ | 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.

• 76 minutes ago, # ^ | Can Python get you through 101000101000?

  • 74 minutes ago, # ^ | we can ignore products greater than that by sorting first, it ACed for me, https://atcoder.jp/contests/abc339/submissions/49957736

    • 72 minutes ago, # ^ | Wow, ingenius.

• 63 minutes ago, # ^ | Btw, I passed G in O((n+qlogn)n−−√)O((n+qlog⁡n)n) with Ofast, see here. Just need to fine tune the block length.

• • 42 minutes ago, # ^ | The library seems so terrible :(

    • 7 minutes ago, # ^ | Terrible in what way(s)?

• 62 minutes ago, # ^ | we can even solve it with merge sort logic without persistent.

  • 46 minutes ago, # ^ | How u solve D

    • 43 minutes ago, # ^ | bfs on pair of cells

• 48 minutes ago, # ^ | I see solutions based on persistent segment tree/fenwick tree and even wavelet tree.

• 45 minutes ago, # ^ | The first G I solved during the contest

• 56 minutes ago, # ^ | 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

• 45 minutes ago, # ^ | 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.

• 28 minutes ago, # ^ | It's meaningless to hack hashing algorithm in Atcoder contest, especially ABC.