### chokudai's blog

By chokudai, history, 15 months ago,

We will hold AtCoder Beginner Contest 295.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +69

| Write comment?
 » 15 months ago, # |   +13 ABC293 test cases files are not uploaded to dropbox.
•  » » 15 months ago, # ^ |   +1 ABC287 was the last beginner contest whose test case files were uploaded
 » 15 months ago, # |   +1 How to solve E?
 » 15 months ago, # |   0 Could someone explain the solution for problem D?
•  » » 15 months ago, # ^ |   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.
•  » » 15 months ago, # ^ |   0 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.
•  » » 15 months ago, # ^ |   0 There are only 1024 states. Among them, only 1 state is a happy state.
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 Like me.
•  » » 15 months ago, # ^ |   0 It may have just been E being more difficult than usual.
 » 15 months ago, # | ← Rev. 2 →   +3 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.
•  » » 15 months ago, # ^ |   0 Any hints for G?
•  » » » 15 months ago, # ^ |   0 SpoilerDynamic Connectivity
•  » » » 15 months ago, # ^ |   +6 Hint 1Think about what kind of graph we have. It is not just any directed graph. It has a lot of nice properties. Hint 2Use DSU or ideas from DSU.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 My G is very short. (The main part of the code is only about 500B.)
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 15 months ago, # ^ |   0 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.
 » 15 months ago, # |   0 How long does it usually take for atcoder ratings to be updated? (this was my first atcoder contest)
•  » » 15 months ago, # ^ |   +1 one or two hours for beginner contests
•  » » 15 months ago, # ^ |   +1 Ratings changes are out I guess
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 Yes, i used digit DP and prefix function and number of occurrences to keep the count. Submission
 » 15 months ago, # |   +1 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.
•  » » 15 months ago, # ^ |   0 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).$
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » 15 months ago, # ^ |   +7 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=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).
•  » » 15 months ago, # ^ |   +3 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
•  » » » 15 months ago, # ^ |   -10 Please explain
•  » » » » 15 months ago, # ^ |   0 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)
 » 15 months ago, # |   0 Why there are no English editorial of G?
 » 15 months ago, # |   0 Can someone please give an example or two of problems similar to D, first time seeing this kind of technique.
•  » » 15 months ago, # ^ | ← Rev. 5 →   +1
•  » » » 15 months ago, # ^ |   0 Thanks!
•  » » 15 months ago, # ^ |   +1
 » 15 months ago, # |   +1 Can someone please provide a more detailed explanation for problem E, Thankyou.
»
15 months ago, # |
Rev. 2   -10

# problem 1

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{

    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

if(str.contains("and")|| str.contains("not")||str.contains("that")|| str.contains("the")||str.contains("you"))
{
System.out.println("Yes");
}else {
System.out.println("No");
}

}


}

•  » » 15 months ago, # ^ |   0 Try equals, not contains
 » 6 months ago, # |   0 If 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??