### maroonrk's blog

By maroonrk, history, 2 years 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! Comments (85)
 » Look forward to the new ARC!
 » 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?
•  » » Yes. (see this post for details)
 » From B to C big difficulty difference.. only for me ?
•  » » YES
•  » » B is much easier than C. Many contestants only solved A and B.
•  » » » yes.. By only solved A & B fast . i got 139+ (490 to 629)
•  » » 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   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.
 » Can we make problem B harder and C easier?
•  » » I think this gives us chance to solve harder problems. But, B is too easy.
 » Can D be solved by FFT?
•  » » 2 years ago, # ^ | ← Rev. 4 →   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
•  » » » "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.
•  » » » » $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.
•  » » » » » 23 months ago, # ^ | ← Rev. 2 →   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?
•  » » » Can you make clear how the transition works? Thanks.
•  » » » » 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}$
•  » » Hi tlsdydaud1 Spoiler저기... ㅇ 그만 붙이면 안 되나요?
 » C & E are implementation garbage
•  » » Is C just writing a lot and lots of if else ?
•  » » » No, but there's a lot of cases where the input is "incorrect".
•  » » » » Could you point out some not-so-obvious cases?
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   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.
•  » » » » » » 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?
•  » » » » » » » It isn't valid, but my solution initially ignored that.
•  » » » » » » » It isnt valid. if you have (3, 6), then you need (2, 5) and (1, 4).
•  » » » » » » And also (1,-1),(-1,3)and (2,3),(-1,-1),(5,8),(-1,-1)
 » What a pure implementation garbage you made to C there.
 » 2 years ago, # | ← Rev. 3 →   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
 » is anyone else think the statement is hard to understand? or just me?
 » Can anyone give a counter case for my submission of C! https://atcoder.jp/contests/arc104/submissions/17176607
•  » » 21 4-1 -1 ans should ne no
•  » » » Why no? it's possible that the second person gets on at 1 and gets off at 4 as well? Or did i misunderstand?
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   Not possibleEvery floor has exactly one on or one off
•  » » » » » ughh okay, thanks.
•  » » » » 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.
•  » » » Thanks ! I misread the problem!
 » The difficulty spike from B to C was HUGE
 » Now this was actual div 1.5 there.
 » Someone explain C, please.
•  » » 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
•  » » » Correct sequence will look like this ((())) (((()))) (()) some consecutive opening and equal number of consecutive endings What is your insight?
•  » » » » 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 . 
•  » » » 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   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?
•  » » » » 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[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 .
 » plz explain b
•  » » 2 years ago, # ^ | ← Rev. 3 →   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
•  » » » it is giving tle for this implementation
•  » » 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.
 » 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$.
 » Can someone explain problem C?
 » Thank you for your participation! I like D and F.
•  » » I enjoyed F too, thanks!
•  » » looks like I was trying to solve every problems except for the fun ones :(
 » 2 years ago, # | ← Rev. 4 →   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)
•  » » Also the ranks, it was atspeeder B.
 » 2 years ago, # | ← Rev. 2 →   Thanks for a quick Editorial
 » 2 years ago, # | ← Rev. 2 →   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)
 » Looks like I am not still sure about the problem statement C.
»

Weak test case for C

Test Case
My AC code which fails on it
 » Also, could you try to make a more balanced contest? This one was worse than most Codechef Cook-offs
•  » » 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   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
 » What does left and right signify in C's Editorial??
•  » » A 'left' is a floor number that belongs to the set 'A'. A 'right' is a floor number that belongs to the set 'B'.
•  » » » Thank you!!
 » 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.
•  » » 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.
 » As always, here's a screencast (didn't even get close to 69th place this time) with A-D video solutions
 » Perhaps Problem C should have been a construction problem since Yes/No problem causes a lot of False Positives / Negatives.
 » 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
 » 2 years ago, # | ← Rev. 3 →   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 is false.But, editorialist's solution (which passes) outputs the following value:i: 0 1 2 3 4dp: 1 0 1 0 1 dp 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.
•  » » There are no people directly contradicting with segment 1-2, so dp thinks that we can use this segment.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   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
•  » » » » 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.
•  » » » » » 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.
•  » » » » » » 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.
•  » » » » » » » 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.
 » 2 years ago, # | ← Rev. 3 →   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.
 » Can anyone explain me how to approach B problem, as I am a beginner in CP
 » 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.
 » Can Anyone help me in Problem D?? unable to understand the editorial.
 » I think the official editorial of the Problem C is wrong.It reads "There is no pair of floors $(x+i,x+k+i)$ such that the person at Floor $x+i$ is 'left'."I think the correct version is "There is no pair of floors $(x+i,x+k+i)$ such that the person at Floor $x+i$ is 'right'."And the next sentence is in the same way.