We will hold AtCoder Beginner Contest 295.
- Contest URL: https://atcoder.jp/contests/abc295
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230325T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: physics0523, yuto1115, evima, math957963, physics0523, PCTprobability
- Tester: m_99, cn449
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
ABC293 test cases files are not uploaded to dropbox.
ABC287 was the last beginner contest whose test case files were uploaded
How to solve E?
Could someone explain the solution for problem D?
Notice that for the condition to be satisfied Xor of all elements of the sub-string should be 0, also you don't have to store the count of all the elements as only string their parity works. Take a number say (tmp) and set the (s[i]-'0')th bit of tmp after every odd occurrence of s[i], make 0 otherwise. You can see my submission.
Can you explain how xor tends to zero for happy strings?
We can rearrange the sub-string.And a happy string is 2*(some string) to get a happy string all characters must appear even times so that we can separate them into 2 stings. Since each character is appearing even times the xor will be 0.
Dynamic program parameterized with position in array and parity for each digit. What you count is the number of intervals with that endpoint whose digit counts have those parities. Eventually, you have to sum up over all positions the entry corresponding to all even parities.
Time limit could have been more generous for python.
Store a 9-bit number for each index (0 to the size of string S). The i-th bit of this number is 1 if the frequency of digit i is odd up to that index while scanning S, and 0 otherwise. Note that a happy string can only be formed when the parity of frequency of the digits 0 to 9 between l and r is even, so the overall parity of the frequency of the digits 0 to 9 between 0 and l, and between 0 and r should be same (as odd frequency — odd frequency = even, even frequency — even frequency = even). Now after assigning a 9-bit number to each index and with the argument given above, it is clear that only those indexes can be paired to form a happy string if their 9-bit numbers are the same. Store the frequency of these 9-bit numbers in a map and calculate the overall happy string-generating pairs from there.
There are only 1024 states. Among them, only 1 state is a happy state.
Is problem G a very standard problem? Like many people weren't able to solve E or F but solved G, and the number of such people might be around 100 or so.
Like me.
It may have just been E being more difficult than usual.
I really liked G this time!
Unlike the previous ABC294, where G was honestly trash because it was a tiny modification of a very well-known problem. Also, previous G required quite a lot of code which is not in the spirit of AtCoder in my opinion.
Any hints for G?
Dynamic Connectivity
Think about what kind of graph we have. It is not just any directed graph. It has a lot of nice properties.
Use DSU or ideas from DSU.
My G is very short.
https://atcoder.jp/contests/abc295/submissions/40051128
(The main part of the code is only about 500B.)
Yeah, my G is also short, probably <1KB. I meant that previous G required long code, just look at the editorial! https://atcoder.jp/contests/abc294/editorial/6013 It is too much for ABC.
I really want to see the editoral of G.
Some of my friends said they used segment tree to solve it.
But I only used a disjoint set to do it.
How long does it usually take for atcoder ratings to be updated? (this was my first atcoder contest)
one or two hours for beginner contests
Ratings changes are out I guess
Did anyone solve problem F using DP? I thought it could be solved like fixing the position of the string and then filling the other positions with digits constrained by the digit at that position but then I realized after coding it that I only counted the string I fixed and not any other occurence of it.
Yes, i used digit DP and prefix function and number of occurrences to keep the count. Submission
The editorial of problem E is so excellent. I didn't realize that expectation could be writen as sum of P(x>=i), while instead, I used dp[i] to compute the probability of Ak<=i, and finally calculate the sum of i*(dp[i]-dp[i-1]). Although this works as well, I think the idea of editorial is more general and one might take advantage of that in the future.
Please please please explain both the solutions (your one too) and how $$$(expected value of X)= i=1 ∑ M (i×(probability that X=i))= i=1 ∑ M (probability that X≥i).$$$
I have been wondering why the same formula is true as well. And it turns out that: $$$(\text{expected value of} X) = \sum_{i = 1} ^ {m} (i \times (\text{probability that } X = i)) = \sum_{i = 1} ^ m i P(X = i) = 1P(X = 1) + 2P(X = 2) +\ldots + mP(X = m) = (P(X = 1) + P(X = 2) +\ldots + P(X = m)) +(P(X = 2) + P(X = 3) + \ldots + P(X = M)) + \dots + P(X = m) = \sum_{i = 1}^m (P(X \geq i))$$$ Which may not seem obvious from first glance.
Sorry for replying late. I find that the transformation to the sum of p(x>=i) has been explained below and the key idea is to replace multiplication of i*p(i) to the addition of p(i).
For the dp part in my solution, assume that we are going to compute dp[i]. Note that for given array of a, we denote q as the number of 0s, and n1 as the number of a[j]<=i, and n2 as the number of a[j]>i.
Next, if n-n2<k, then dp[i]=0 since the k-th index must have a value greater than k. If n1>=i, then dp[i]=1 since the k-th index must have a value less than or equal to k. Otherwise, we need at least k-n1 values which are less than or equal to i, and this is calculated as the sum of nck(q,t)*(p1)^t*(p2)^(q-t) where t belongs to [k-n1, q], and nck(q,t) means "choose t from q", and p1 means the probability of setting 0 to a value <=i, and p2 means the probability of setting 0 to a value >i. More specifically, p1=i/m, and p2=(m-i)/m. Therefore, the first loop is for i and the second loop is for t, and totally O(N^2).
In fact, I tried to compute dp[Ak=i] rather than dp[Ak<=i] at first, but I found the complexity to be O(N^3), and then I decided to give a try of computing dp[Ak<=i] and fortunately it works. Now, I think that, computing dp[Ak=i] means splitting [1,m] into three parts [1,i-1],[i,i],[i+1,m] while dp[Ak<=i] means splitting into two parts [1,i] and [i+1,m], and maybe this is the reason why complexity can be reduced from O(N^3) to O(N^2).
I think the i*(dp[i]-dp[i-1]) is more general. But the editorials idea is very pretty indeed and might be useful in different situations
Please explain
In my solution dp[i] is how many assignments of 0s to [1,m] make the kth element of the sequence (after sorting) be i or less. (My username is the same in atcoder if you want to see my code)
Why there are no English editorial of G?
Can someone please give an example or two of problems similar to D, first time seeing this kind of technique.
link link
Thanks!
link
Can someone please provide a more detailed explanation for problem E, Thankyou.
problem 1
https://atcoder.jp/contests/abc295/tasks/abc295_a
2 Testcases are failing in this code which i donot why can anybody help that my code.
import java.util.*;
import java.io.*;
public class Main{ public static void main(String[] args) throws IOException{
}
Try
equals, notcontainsIf problem D was about forming triplets (should be multiple of 3), will the idea of counting state paris $$$cnt[state] * (cnt[state]-1) / 2$$$ still hold??