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.
- Contest URL: https://atcoder.jp/contests/arc104
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201003T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: satashun
- Tester: tempura0224, kobae964
- Rated range: ~ 2799
The point values will be 100-400-600-700-700-1000.
We are looking forward to your participation!
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.
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?
no need, just some small constant dp will do
mine 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 value
x-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 know
Hope 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.
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.
Can you make clear how the transition works? Thanks.
so in normal transition
when 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 transition
but now if we maintain some kind of prefix sum
we 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 1
the only difference will be when you do a prefix sum
$$$ad_j += ad_{j - i}$$$ instead of $$$ad_j += ad_{j-1}$$$
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?
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.
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
2
1 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?
Not possible
Every 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
Someone explain C, please.
Each position from 1 to 2*N must be used
Correct sequence will look like this ((())) (((()))) (()) some consecutive opening and equal number of consecutive endings
Dynamic Programming can be used . Dp[pos][remaining] = true if we can match remaining number of people in segment ( pos to 2n )
Code
What is your insight?
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.
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?
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
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$$$.
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 :(
First, two nobrainer problems that put together barely compete with a typical div2A
And 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.
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
3 1 -1 4 -1 5 -1
include<bits/stdc++.h>
include
define pb push_back
define ld long double
define mp make_pair
define vl vector
define vd vector
define vld vector
define ll long long int
define pl pair<ll, ll>
define all(a) a.begin(), a.end()
define forr(i, n) for(ll i=0; i<n; i++)
define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std; const ld PI =3.1415926535897923846; const ll MOD = 1000000007; const ll N=998244353; ll power(ll x,ll n){ll res=1;while(n>0){if(n&1) res=res*x%MOD;x=x*x%MOD;n>>=1;}return res;} ll modinverse(ll a){return power(a, MOD-2);} void solve() { ll n; cin>>n; vl a(n), b(n); set s1; map<ll, ll> mp1; forr1(i, 2*n) s1.insert(i); vector onof(n); forr(i, n) { cin>>a[i]>>b[i]; mp1[a[i]]++, mp1[b[i]]++; if(a[i]>0) s1.erase(a[i]); if(b[i]>0) s1.erase(b[i]); if(mp1[a[i]]>1&&a[i]!=-1) { cout<<"No\n"; return; } if(mp1[b[i]]>1&&b[i]!=-1) { cout<<"No\n"; return; } if(a[i]>0&&b[i]>0&&a[i]>=b[i]) { cout<<"No\n"; return; } if(a[i]==2*n||b[i]==1) { cout<<"No\n"; return; } } vl c(n, -1); forr(i, n) { if(a[i]>0&&b[i]>0) c[i]=(b[i]-a[i]-1); } forr(i, n) { if(c[i]>0) { forr(j, n) { if(c[j]>=0&&a[j]>a[i]&&b[i]>a[j]&&c[i]!=c[j]) { cout<<"No"<<endl; return; } else if(c[j]==-1&&a[j]>a[i]&&b[i]>a[j]) { b[j]=a[j]+(b[i]-a[i]); c[j]=c[i]; if(b[j]>2*n||mp1[b[j]]>0) { cout<<"No\n"; return; } s1.erase(b[j]); mp1[b[j]]++; if(i>j) { i=j-1; break; } } } } } cout<<"Yes\n"; } int main() { #ifndef ONLINE_JUDGE // for getting input from input.txt freopen("input.txt", "r", stdin); // for writing output to output.txt freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); ll test=1; //cin>>test; while(test--) { solve(); } cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"; }
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.
Not like I argue that it is meant to be "div 1.5"
But your link only confirms that the balance is often quite terrible
I 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.
3
-1 -1
2 4
3 5
My 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:
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 solutionsPerhaps 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
I think the submitted solutions for C and editorialist's solution is not completely correct. Let's take the following test case:
There is only one possible solution for this test case, which is:
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 4
dp: 1 0 0 0 1
dp[2] is false.
But, editorialist's solution (which passes) outputs the following value:
i: 0 1 2 3 4
dp: 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.
There are no people directly contradicting with segment 1-2, so dp thinks that we can use this segment.
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.
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 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.
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.