chokudai's blog

AtCoder Beginner Contest 295 Announcement
By chokudai, history, 21 month(s) ago, In English

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!

  • Vote: I like it
  • +69
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

ABC293 test cases files are not uploaded to dropbox.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the solution for problem D?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how xor tends to zero for happy strings?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are only 1024 states. Among them, only 1 state is a happy state.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How long does it usually take for atcoder ratings to be updated? (this was my first atcoder contest)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).$$$

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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).

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Please explain

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there are no English editorial of G?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give an example or two of problems similar to D, first time seeing this kind of technique.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please provide a more detailed explanation for problem E, Thankyou.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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{

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

    int aa= Integer.parseInt(br.readLine());

    String str= br.readLine();

    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");
    }

}

}

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

→ Reply