Блог пользователя chokudai

Автор chokudai, история, 13 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
13 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

ABC293 test cases files are not uploaded to dropbox.

»
13 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve E?

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone explain the solution for problem D?

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
13 месяцев назад, # |
  Проголосовать: нравится 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.

»
13 месяцев назад, # |
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.

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
13 месяцев назад, # |
  Проголосовать: нравится 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.

»
13 месяцев назад, # |
  Проголосовать: нравится +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.

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 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).$$$

    • »
      »
      »
      13 месяцев назад, # ^ |
      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.

    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится +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<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).

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      Please explain

      • »
        »
        »
        »
        13 месяцев назад, # ^ |
          Проголосовать: нравится 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)

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why there are no English editorial of G?

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
13 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
13 месяцев назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

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

}

}

»
5 месяцев назад, # |
  Проголосовать: нравится 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??