We will hold Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339).
- Contest URL: https://atcoder.jp/contests/abc339
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240203T2100&p1=248
- Duration: 100 minutes
- Writer: cn449, physics0523, kyopro_friends, evima
- Tester: math957963, leaf1415
- Rated range: ~ 1999
- The point values: 100-250-250-400-525-550-600
We are looking forward to your participation!
Seems E,F is so difficult
DO NOT try to evaluate the difficulty of a task based on its point value. It's often inaccurate.
I don't know why people are downvoting you
It is not often inaccurate; rather, it is sometimes inaccurate.
who is nandini bro :) ?
The fact is that G is so easy. I solved all of the tasks!
Tasks were too easy.
F was kind of fun though :) For some reason, hashes weren’t the first thing I came up with
Hope AC ABCD.
The same to you.
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.
Hello everyone! Is everyone ready to contest? I wish luck to everyone! :)
The same to you
This is my first contest in AtCoder.Good luck for me!
If anyone solved problem E, please share your idea after the contest.
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
Can you share your code, please?
https://atcoder.jp/contests/abc339/submissions/49946979
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 .
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).
In fact, the lazy tag doesn't matter, and the dp array is exactly the array maintained by the segment tree in my code.
$$$dp[i] = max(dp[i], dp[j] + 1) : [ abs(a[i] - a[j]) <= k] \forall j \in [0, i) $$$ to speed this Transition up I used BIT since $$$a[j] \in (a[i] - k, a[i] + k)$$$.
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
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 elementx
and max adjacent differenced
, the element just beforex
(i.e. the previous element of the subsequence, if any) can be betweenx-d
tox+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 elementx
, 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: linkyou may solve it with tree
I AC nothing...
Bad one
I realized in the end that B is the recursion.
More like simulation really
C:
Why do input 4 -1 1000000000 1000000000 1000000000 Outputs 3000000000?
start with 1, that's the minimum you can start with, because next stop is -1 and there after it is always positive
Oh,it outputs the number of passengers at the end.
I outputs the number of passengers at the beginning.
I'm writing it. Task E is interesting and easy
Trash Round.
How to solve E?
https://mirror.codeforces.com/blog/entry/125434#comment-1112843
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
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.
Hints for E: Smooth Subsequence
Start with the first DP definition that comes to mind.
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.
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
thank you so much got it now adaptatron fonmagnus ilovenandini
hey man, haven't thought of this approach. thanks for sharing
Did anyone AC problem G in $$$O(n \log{n} + q \log^2{n})$$$?
I solve it with merge sort tree.
I also tried with merge sort tree in $$$O(\log^2{n})$$$ per query but it kept TLEing.
You can use zkw segment tree to speed up. submission
What is zkw segemnt tree?
Passes comfortably: submission
Sqrt Decomposition is the easiest solution and surprisingly it passed!
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.
I solve it with merge sort tree. n * log n for build it. (log n)^2 for answer to each query.
I think you can just copy G from somewhere else since the problem is so generic lol.
How to solve D?
Bfs and you need to keep track of both persons positions.
I did something like dijkstra and it TLE'd.
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
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?
each node is of form x1,y1,x2,y2 so make a 4d array
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.
In fact a $$$60^4$$$ bool array only cost about 12.8MB
So it doesn't matter
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.
Can anyone share the idea behind problem F? I couldn't understand the approach mentioned in the video linked in the editorials tab.
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.
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.
I saw some people pass F using Python, or you can implement bigint faster by using bitset to obtain the 1 / 64 constant.
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.
I did D using multiple ways method, but I think I'm not right, can anyone share his/her smart idea
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.
Either you use FFT/Karatsuba in F or just AC with Python.
Can Python get you through $$$10 ^ {1000}$$$?
we can ignore products greater than that by sorting first, it ACed for me, https://atcoder.jp/contests/abc339/submissions/49957736
Wow, ingenius.
E easier than D
Same as task E.
Btw, I passed G in $$$O((n+q\log n)\sqrt{n})$$$ with Ofast, see here.
Just need to fine tune the block length.
Please stop making big integer problems like $$$F$$$ python people just make fun of cpp people :( like this
For cpp you can use bigint in Nyaan's library. ac submission
The library seems so terrible :(
Terrible in what way(s)?
I didn't mean by code writing (that's pretty much nice) but I am just afraid of no of lines to put in my code to solve certain problem.
You don't even need to break at any point after sorting, it still passes. My submission-code
The Easiest G Ever
Just a model of persistent segment tree
we can even solve it with merge sort logic without persistent.
How u solve D
bfs on pair of cells
I see solutions based on persistent segment tree/fenwick tree and even wavelet tree.
The first G I solved during the contest
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.
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
trash contest. We don't need to think but we can AC all problem.
there is actually a deterministic approach to solve F using python
just dont multiply 2 numbers with combined length greater than the max length of largest a[i]
my solution
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.
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.
It's meaningless to hack hashing algorithm in Atcoder contest, especially ABC.
What is the difficulity score of Problem D E F based on codeforces rating system?
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
Thanks for your opinion!!!
I think it's a trash round. Problem F and G are too easy.
It's just the Goodbye 2023 on Atcoder. Imbalanced difficulty, existing problem, letting wrong solutions pass...
This is the reason I didn't AK this contest.
I'm just wondering, what solution can be used to solve G if the queries can be answered offline?
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.
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
I've created a tutorial and practice contest to help you understand how to solve it efficiently if the queries could be answered offline.
Can Problem E solved with dp + Fenwick Tree?
I dont think so. I solved with DP + segment tree. and the segment tree used for findind maximum value of a segment of numbers so it cant be handle with Fenwick.
After search some material in the Internet, I have solved the Problem E with Fenwick Tree.It seems that Fenwick Tree can be used to deal with range max/min query problem.Here is my Fenwick Tree Solution.
I didnt know this. thank
For more details you can refer to this paper.
Bad one
TemplateCoder.
Can anyone tell me why my code only use 78 ms but i have a Runtime Error
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
Take a look at Ticket 17330 from CF Stress for a counter example.
Why there is still no editorial yet?
https://atcoder.jp/contests/abc339/submissions/50118454
Any counter test for this solution of D
Take a look at Ticket 17334 from CF Stress for a counter example.
Thank you sir
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