### maroonrk's blog

By maroonrk, history, 7 months ago,

ARC is back!

(The problem set is organized by rng_58, but it seems that he forgot to write a blog. Thus I do it instead.)

We will hold AtCoder Regular Contest 104.

The point values will be 100-400-600-700-700-1000.

We are looking forward to your participation!

• +145

 » 7 months ago, # |   +9 Look forward to the new ARC!
 » 7 months ago, # |   +16 Just to be clear, is the point value system of ARC consistent with that of ABC in terms of difficulty of problems? As in will ARC B be as tough as ABC D, ARC C as tough as ABC F,... and so on?
•  » » 7 months ago, # ^ |   +18 Yes. (see this post for details)
 » 7 months ago, # |   0 From B to C big difficulty difference.. only for me ?
•  » » 7 months ago, # ^ |   +8 YES
•  » » 7 months ago, # ^ |   0 B is much easier than C. Many contestants only solved A and B.
•  » » » 7 months ago, # ^ |   -28 yes.. By only solved A & B fast . i got 139+ (490 to 629)
•  » » 7 months ago, # ^ |   +30 I think maybe ARC should just drop the first two problems or make them harder. The rest of ARC is div 1.5 or so, so it doesn't really make sense to add 2 "implement what you see" problems to the beginning.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +5 That way people who can solve zero hard problems are baited into participating and getting negative rating. This is why I'm scared of AGCs, since I'm one of those people. :)That said, I looked at today's round and today's A felt closer to an ABC A or B, not an ARC A, to my recollection of what ARCs are typically like.
 » 7 months ago, # |   +14 Can we make problem B harder and C easier?
•  » » 7 months ago, # ^ |   0 I think this gives us chance to solve harder problems. But, B is too easy.
 » 7 months ago, # |   +11 Can D be solved by FFT?
•  » » 7 months ago, # ^ | ← Rev. 4 →   +3 no need, just some small constant dp will domine works in roughly ("${O(n^2k^2)}$"), sorry it's actually $O(n \times n^2k)$ for n rounds and each round you need up to k * (1+2+...n/2) My Ac Code$dp_{ij}$ means how many ways can we have maximum value used is i and sum is j for sum we need only values between [1, k(1+2+...n/2)]and you can treat average x as find how many ways can we have the sum of maximum used valuex-1 the same with maximum used value n-x-- update I am not sure why it passed, but I heard that with some optimize like maintaing current maximum sum can reduce the time complexity to .. I don't knowHope someone can answer it for me
•  » » » 7 months ago, # ^ |   +5 "you can treat average x as find how many ways can we have the sum of maximum used value x-1 the same with maximum used value n-x" can someone explain it. Thanks in advance.
•  » » » » 7 months ago, # ^ |   +11 $1 \times k_1 + 2 \times k_2 + ... + N \times k_N = x \times (k_1 + k_2 + ... + k_N)$ $<=> (1-x) \times k_1 + (2-x) \times k_2 + ... + (x-x) \times k_x + ... + (N-x) \times k_N = 0$ $<=> k_{x+1} + 2 \times k_{x+2} + ... + (N-x) \times k_n = k_{x-1} + 2 \times k_{x-2} + ... + (x-1) \times k_1$The left side is a sum with maximum used value n-x and the right side is with maximum used value x-1. Count the number of cases where the two are equal.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 is k1,k2 are instances of 1,2..N?? in the multiset that you have written 1*k1+2*k2...?? can you explain a bit more?
•  » » » 7 months ago, # ^ |   0 Can you make clear how the transition works? Thanks.
•  » » » » 7 months ago, # ^ |   +8 so in normal transitionwhen we want to count $dp_{ij}$ , it should be $dp_{ij} = dp_{i-1, j} + dp_{i-1, j-1*i} + dp_{i-1, j-2*i} ... dp_{i-1, j-k*i}$it takes $O(k)$ for each transitionbut now if we maintain some kind of prefix sumwe can speed up to amortized $O(1)$in case when i is 1 we just need add our dp to another array $ad$like in $dp_{ij}$ we know that $dp_{i+1, j}, dp_{i+1, j+1}...dp_{i+1, j+k}$ will be added $dp_{ij}$so we add $dp_{ij}$ to $ad_j$ and $-dp_{ij}$ to $ad_{j+k}$after all $dp_i$ is put into $ad$we do a prefix sum in $ad$and we know $dp_{i+1,j}$ should be $ad_j$consider the case when i is not 1the only difference will be when you do a prefix sum$ad_j += ad_{j - i}$ instead of $ad_j += ad_{j-1}$
•  » » 7 months ago, # ^ |   -13 Hi tlsdydaud1 Spoiler저기... ㅇ 그만 붙이면 안 되나요?
 » 7 months ago, # |   +6 C & E are implementation garbage
•  » » 7 months ago, # ^ |   +8 Is C just writing a lot and lots of if else ?
•  » » » 7 months ago, # ^ |   +24 No, but there's a lot of cases where the input is "incorrect".
•  » » » » 7 months ago, # ^ |   0 Could you point out some not-so-obvious cases?
•  » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 For me the problem wasn't solved because of one missed if-else statement, and it wasn't where input was "incorrect" :( I missed the case like (1 -1), (-1 4), (3 6) where 1 and 4 must be combined to one pair, but are located in different pairs.
•  » » » » » » 7 months ago, # ^ |   0 Shouldn't it not be valid to combine pairs like that, since they said that they provide the (A, B) pairs for each i? So the (1, -1) pair is only the first person and the (-1, 4) pair is only the second person?
•  » » » » » » » 7 months ago, # ^ |   +5 It isn't valid, but my solution initially ignored that.
•  » » » » » » » 7 months ago, # ^ |   0 It isnt valid. if you have (3, 6), then you need (2, 5) and (1, 4).
•  » » » » » » 7 months ago, # ^ |   0 And also (1,-1),(-1,3)and (2,3),(-1,-1),(5,8),(-1,-1)
 » 7 months ago, # |   +4 What a pure implementation garbage you made to C there.
 » 7 months ago, # | ← Rev. 3 →   -10 how to solve D ?I searched for general diophantine equations and how to solve them but could not find anything elementary.We were to find all xi such that : a1x1 + a2x2 + a3x3 +....+anxn = 0where(0 <= xi <= k)andai = (x — i)where x an integer that varies from (1 to N).print for all x the number of possible solutions modulo M
 » 7 months ago, # |   0 is anyone else think the statement is hard to understand? or just me?
 » 7 months ago, # |   0 Can anyone give a counter case for my submission of C! https://atcoder.jp/contests/arc104/submissions/17176607
•  » » 7 months ago, # ^ |   0 21 4-1 -1 ans should ne no
•  » » » 7 months ago, # ^ |   0 Why no? it's possible that the second person gets on at 1 and gets off at 4 as well? Or did i misunderstand?
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   0 Not possibleEvery floor has exactly one on or one off
•  » » » » » 7 months ago, # ^ |   0 ughh okay, thanks.
•  » » » » 7 months ago, # ^ |   +1 Read the statement it says only 1 person can get on/off at some floor so the A and B generated will themselves be some permutation of numbers from 1 to 2N respectively.
•  » » » 7 months ago, # ^ |   0 Thanks ! I misread the problem!
 » 7 months ago, # |   +17 The difficulty spike from B to C was HUGE
 » 7 months ago, # |   -8 Now this was actual div 1.5 there.
 » 7 months ago, # |   0 Someone explain C, please.
•  » » 7 months ago, # ^ |   +6 Hints for C 1Each position from 1 to 2*N must be used 2Correct sequence will look like this ((())) (((()))) (()) some consecutive opening and equal number of consecutive endings 3Dynamic Programming can be used . Dp[pos][remaining] = true if we can match remaining number of people in segment ( pos to 2n )Code
•  » » » 7 months ago, # ^ |   0 Correct sequence will look like this ((())) (((()))) (()) some consecutive opening and equal number of consecutive endings What is your insight?
•  » » » » 7 months ago, # ^ |   0 I have tried some smaller cases 1. Number of in and out is clearly equal . 2. ))(( this is Impossible 3.( () () ) This type of sequence is not possible . Because length of the outer segment is clearly greater then the two inner segments . But they should be equal . 
•  » » » 7 months ago, # ^ |   0 During contest, I get to hint number 2 but could not think of a way to implement it. I didn't think about dp though.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +3 Hint1 & Hint2 are pretty obvious from the question itself. But can you please elaborate more on DP states and how transitions handles all the cases?
•  » » » » 7 months ago, # ^ |   +3 Dp TransitionsSuppose we completed matching up (n-rem) people at range (1 to pos-1) Now from pos we will try to place a new block . we will try every block length . Let our new block look like this : ((())) Block length = 6 reduce = how many people we can match with this 6 length block . so Dp[pos][rem]=Dp[pos][rem] | dp[pos+block_length][rem-reduce]; if(pos>2*n && rem==0) return true . means we have match all the people . if(Dp[1][n]==true)cout<<"Yes";  How dp transition handles all the cases ?From each position we are trying to place every possible block of diffrent lengths . So all the combinations of blocks are checked .
 » 7 months ago, # |   0 plz explain b
•  » » 7 months ago, # ^ | ← Rev. 3 →   0 generate all substring and check if the number of 'A' character equal to the number of 'T' character ,and the number of 'C' character equal to the number of 'G' character
•  » » » 7 months ago, # ^ |   0 it is giving tle for this implementation
•  » » 7 months ago, # ^ |   +3 Keep count of A, T, C and G at each position.Iterate over all substring where starting position $i$ and ending position $j$.Check condition $cnt(A) = cnt(T)$ AND $cnt(C) = cnt(G)$. If yes, increment answer.My submission C++ with simple code. See if it helps.
 » 7 months ago, # |   +7 Actually, I don't understand C (sure my bad english). But it is written in weird case, why not write for each pair of person $i, j$ ... then $C_i = C_j$.
 » 7 months ago, # |   0 Can someone explain problem C?
 » 7 months ago, # |   +18 Thank you for your participation! I like D and F.
•  » » 7 months ago, # ^ |   +18 I enjoyed F too, thanks!
•  » » 7 months ago, # ^ |   +11 looks like I was trying to solve every problems except for the fun ones :(
 » 7 months ago, # | ← Rev. 4 →   0 First, two nobrainer problems that put together barely compete with a typical div2AAnd then, boom, right after them is something on the level of div2E (or D in relatively tough rounds)
•  » » 7 months ago, # ^ |   +3 Also the ranks, it was atspeeder B.
 » 7 months ago, # | ← Rev. 2 →   0 Thanks for a quick Editorial
 » 7 months ago, # | ← Rev. 2 →   +20 For E, seems like if you consider all possible orderings, you only need to consider N! orderings of n numbers (with some tie-breaking rules), which is much smaller than 4386 groups mentioned in editorial for N=6 (N!=720).My solution that generates and checks each ordering: https://atcoder.jp/contests/arc104/submissions/17177505 (Unfortunately it's a complete mess as I try to debug within last 5 minutes)
 » 7 months ago, # |   0 Looks like I am not still sure about the problem statement C.
»
7 months ago, # |
-16

Weak test case for C

Test Case
My AC code which fails on it
 » 7 months ago, # |   0 Also, could you try to make a more balanced contest? This one was worse than most Codechef Cook-offs
•  » » 7 months ago, # ^ |   +1 ARC was always supposed to be "div 1.5". I don't think it was ever aimed at pupils, or even experts. If you see here, besides A and B being way too easy, it's not like C was too out of place from a difficulty standpoint.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Not like I argue that it is meant to be "div 1.5"But your link only confirms that the balance is often quite terribleI mean previous ARC had A800, B2900, C1700, D3000...And actually atcoder often has this kind of jumps
 » 7 months ago, # |   +6 What does left and right signify in C's Editorial??
•  » » 7 months ago, # ^ |   0 A 'left' is a floor number that belongs to the set 'A'. A 'right' is a floor number that belongs to the set 'B'.
•  » » » 7 months ago, # ^ |   0 Thank you!!
 » 7 months ago, # |   +8 I think C is missing a few crucial test cases. My code gets AC even though there is a simple case where it fails. Break case3-1 -12 43 5My code answers "Yes" but the actual answer is "No". I didn't do any sort of DP, I just check for various conditions where the answer is obviously "No". If the input passes all my checks(which is obviously incomplete) I output "Yes". So my code gives false positives but never false negatives.
•  » » 7 months ago, # ^ |   +3 Not directly related to this case, but I found another simple case in which my AC code fails: Break case1 2 -1 Maybe this kind of cases should be included in after_contest.
 » 7 months ago, # |   +11 As always, here's a screencast (didn't even get close to 69th place this time) with A-D video solutions
 » 7 months ago, # |   +18 Perhaps Problem C should have been a construction problem since Yes/No problem causes a lot of False Positives / Negatives.
 » 7 months ago, # |   +42 Saw a lot of negative feedback, want to say that problems were nice. Wording really could be better in some problems. And yeah, difficulty estimation for C is way off, I was sure that I did some overkill while it was intended solution. But I wouldn't say that the contest is less balanced compared to other ARCs, usually the gap is from E to F though and most people just don't see it.While I'm here... screencast with commentary if somebody is interested
 » 7 months ago, # | ← Rev. 3 →   -8 I think the submitted solutions for C and editorialist's solution is not completely correct. Let's take the following test case: 2 -1 3 -1 4 There is only one possible solution for this test case, which is: 2 1 3 2 4 Now, in the DP approach dp[i] stores whether a possible solution exists using all the floors from 1 to i, such that people using floors from 1 to i enter and exit at floors between 1 to i only. And, the answer eventually would be dp[2*n].So for the above mentioned test case dp should look like the following:i: 0 1 2 3 4dp: 1 0 0 0 1 dp[2] is false.But, editorialist's solution (which passes) outputs the following value:i: 0 1 2 3 4dp: 1 0 1 0 1 dp[2] is true (should be false).Although, dp[2*n] is correct for all solutions, and that's the only thing that matters eventually. But, I failed to understand how dp[2*n] will be always correct, even when some values in dp[i] may be incorrect.
•  » » 7 months ago, # ^ |   0 There are no people directly contradicting with segment 1-2, so dp thinks that we can use this segment.
•  » » » 7 months ago, # ^ | ← Rev. 3 →   -16 Yes, in the above case both 1 and 2 are unassigned, and the dp therefore thinks that a person going from 1 to 2 is valid. But that's not true.And, I think it will be better to keep track of number of people whose A and B are (-1 -1), which will help in deciding whether someone can go from i to j, if both i and j are unassigned.galen_colin keeps track of such people in his dp solution.Link to solution
•  » » » » 7 months ago, # ^ |   0 What do you mean by better? The solution is correct, dp[2*p] means that we can divide positions [1..(2*p)] into segments such that no person contradicts no segment.
•  » » » » » 7 months ago, # ^ |   -6 By, better I meant its easier for me to think of it when keeping track of above mentioned persons in my dp.Because, its difficult for me to prove the correctness of the solution mentioned in the editorial.
•  » » » » » » 7 months ago, # ^ |   +16 Well that's your problem, isn't it? I don't like how you twice said that the solution in editorial is not correct. You accuse people of something because you can't understand their logic. That's not good.
•  » » » » » » » 7 months ago, # ^ |   -9 Well, I am sorry about how I phrased it, but I mostly meant, as you can see in my last sentence of the original comment that "I failed to understand how it will be always correct", and to understand the same was one of the reasons of posting it here.
 » 6 months ago, # | ← Rev. 3 →   +34 Someone pointed out that the writer's solution code was wrong. (logic itself was ok though) We checked that the outputs of three testers’ codes were correct, and test cases used for the contest were unaffected. We don’t have hack systems, so writer’s code itself is not used during contests, therefore the contest is still rated. We apologize for the weak test cases.
 » 6 months ago, # |   0 Can anyone explain me how to approach B problem, as I am a beginner in CP
 » 6 months ago, # |   +5 Can anyone be kind enough to tell me how to make the "solution using Formal Power Series" of problem D?Actually I don't how to maintain the multiply of (1-x^(k+1)i)/(1-x)...Should I use fft to get the inverse of the polynomial and multiply them？But the solution says this solution's time complexity didn't have a log element.Can anyone help me? thks in advance.
 » 5 months ago, # |   0 Can Anyone help me in Problem D?? unable to understand the editorial.