maroonrk's blog

AtCoder Regular Contest 163 Announcement
By maroonrk, history, 18 months ago, In English

We will hold AtCoder Regular Contest 163.

The point values will be 300-400-600-700-900-1100.

We are looking forward to your participation!

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

Comments Comments (42)
| Write comment?
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Lost 80% of contest time by only thinking. depressed :(

How to solve C/D ?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    C.1 = (sum(1/(i*(i+1))) where 1<=i<=n-1 ) + 1/n. But it doesnot work in some cases, (where n = k(k-1)). You must fix this.

    → Reply
»
18 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Proud to submit B at the last second and got accepted! :)

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    congratulations

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I also submitted B in like the last 10 mins, got AC× 11,WA × 3,TLE × 25. got pretty devastated.

    → Reply
»
18 months ago, # |
  Vote: I like it +120 Vote: I do not like it

Problem F is the same as this

→ Reply
»
18 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Cool C & D, i get like 5 WA's on B, because don't think about case A[0] > A[1] ....

→ Reply
»
18 months ago, # |
  Vote: I like it +38 Vote: I do not like it

$$$C$$$ is interesting problem. We can notice that $$$\frac{1}{x} = \frac{1}{x+1} + \frac{1}{x(x+1)}$$$. This will be the only transition from $$$n$$$ to $$$n + 1$$$ — we will remove some $$$x$$$ and insert $$$x + 1$$$ and $$$x(x + 1)$$$. Since the size of set is $$$< 500$$$, with high probability there will be no both these numbers.

My solution is:

set = {2, 3, 6}
for t in 3 .. n:
    while true:
        x = rand in set <= 1000
        y = x + 1, z = x * (x + 1)
        if y not in set and z not in set:
            set.remove(x)
            set.add(y)
            set.add(z)
            break
→ Reply
»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

anyone get why https://atcoder.jp/contests/arc163/submissions/43201545 does not work for C?

asserts should ensure it works well + bruteforcing on all cases reveals no issues (i.e. all criterias are satisfied IMO).

Idea is quite similar, just the edge cases ($$$N = i * (i + 1)$$$) are handled slightly differently,

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I am not quite confident, but I find that for n=6, your output is not correct.

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I think you should construct a solution for n-2 in the special case(where N=i*(i+1)) and then replace the largest number x in that solution by 2x,3x and 6x.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      alternatively, construct for n — 1, and then replace the highest term by 3/2x, 3x, it can be seen its always divisible by 2

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

I saw the editorial is written by GPT-4. Was it generated from only problem, or from essential describing of solving method?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Edu was first written in Japanese and then they were translated through GPT.

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

How to solve B?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    two pointers

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

      Not helpful, care to explain?

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        hint : store and sort the elements except 1st and 2nd element in an array then check every m size subarray , for each subarray check minimum operation required to have all those m elements of the subarray between modified / unmodified A1 & A2 ; minimum of them is the answer

        → Reply
»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Would anyone like to talk more about problem D. I read that "theorem" in the editorial, but I don't quite understand. For instance, it says that if s1,s2,...,sk form a strongly connected component, then A and B satisfy the condition. But, we have an edge from sk to s1, and this means that there is an edge directed from B to A, which is against the condition?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    My understanding of the editorial:

    SCCs (s1, s2, ... , sk) form a DAG.

    Let's arrange these SCCs so that iff i < j, then s_i is topologically earlier than s_j. With such an arrangement there may not be any edge from sj to si, if j > i, as that would lead to a contradiction (as sj is later in topological order).

    Note, that as it's a tournament, there exists a single topological ordering of the SCCs, as there is always a directed edge between any pair of vertices.

    So we can safely divide SCCs into sets A = { s1, s2, ..., si }, B = { si+1, si+2, ..., sk}, so that they meet the conditions. And there will be exactly K+1 such divisions into two sets of SCCs as we can choose any i in range [ 0, k ].

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

    s1,s2,...,sk form a strongly connected component

    Here is the misunderstanding. According to the editorial, (s1,s2,...,sk) do not FORM a strongly connected component. (s1, s2, ..., sk) ARE LABELS for all the strongly connected components in the graph.

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

      Thank you so much! I thought that s1,s2,...,sk are nodes but in fact they denote SCC. Now, I would like to try to understand the editorial again.

      → Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    I did something different, although I didnt manage to debug and AC within contest.

    Basically, my dp state was dp[n][cc][m] = how many different graphs of n vertices have cc connected components and m edges from small to big. Once u have that its just simple math.

    The transition then is take k vertices to form the 1st CC in the DAG, suppose it has m1 s->b edges, and suppose the 1st CC to the rest of the CC have m2 s->b edges and the remaining CC-1 components have the rest (m — m1 — m2 edges). If you get the 3 parts, you can just multiply all 3 and add to dp[n][cc][m]. So ull add something like (ways to pick k vertices with m2 as described above)*dp[k][1][m1]*dp[n-k][cc-1][m- m1 — m2]

    Also u cant compute dp[n][1][m] directly, but you can get it via C(n*(n-1)/2, m) — dp[n][2][m] — dp[n][3][m] — etc. (Or maybe there is a combinatorial argument that eludes me)

    For the ways to choose the k vertices, basically its the number of multisets such that k numbers from 0 to (n-k) such that it add up to m2. (You can write a dp for that, I dont know of a formula, bars and stars is ordered which is not what we want)

    Depending on how u do it, it can take very long (like O(n^10)), but what I realised after the contest was that by reordering the loops, u can do convolution on the results of the 3 parts to get the result fast, instead of having 3 for loops (which is O(n^6)) and reduce to just O(n^4) or O(n^2logn) with NTT. Link: https://atcoder.jp/contests/arc163/submissions/43206412

    → Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My code (according to the editorial):

    Spoiler
    → Reply
»
18 months ago, # |
  Vote: I like it +19 Vote: I do not like it

C can even be found on search engines. Hope to see more interesting CP problems instead of well-know math problems.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    link please

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

      You can find the sol in this video->link Also, the key equation can be found easily by searching "Egyptian Fractions" on search engines.

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

I didn't know that GPT-4 is smart enough to solve E

→ Reply
»
18 months ago, # |
  Vote: I like it +34 Vote: I do not like it

How Does checker of problem C work?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    long double has accuracy upto 18 digits, right? and we need accuracy upto 9 digits for numbers between 1 and 1e9.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      untrue, taking only 9 digits is not enough, for example 9, 9, 9, .... 9(9 nine times) is correct (ignore equal rule break) and 9, 9..., 9, 1e9 is not correct but you will mark exactly opposite

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        What I meant was something like

        Code

        returns true for the first case u mentioned, and false for second

        edit: hm you're right 9 digits are not enough because of upto 500 different additions.. still, 12 digits would do and we hv 18 digits (more than enough to guarantee correct answer)

        → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          (2, 4, ....., 2^n, 2^n) adds to 1

          (2, 4, ....., (2^n) — 1, (2^n) + 1) gives a difference of the order 1e-25 according to my computer (for n = 28)

          one must always be careful of making such analysis without really giving any reason for why its correct.

          void Solve() 
{
    long double ok = 1 << 28;
    long double sum = 0;
    
    sum += 2 * (1 / ok);
    sum -= 1 / (ok - 1);
    sum -= 1 / (ok + 1);
    
    cout << sum << "\n";
}
          → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    modulo hash fractions should work

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Note that the sum $$$1/a_1 + 1/a_2 + \dots + 1/a_n$$$ can have a denominator of about $$$(10^9)^n$$$, so it can be super close to $$$1$$$, while not being $$$1$$$ exactly.

    The bounds are low, so the checker can just calculate the exact fraction using big number arithmetic. It will only need the plus and times operations on bignums, and use those bignums in a fractions struct. It can be implemented without that much pain in C++. (If it is possible, I would do it with Python.)

    A fast way to do it is divide and conquer. So calculate the exact fractional sum for the left halve and right halve of the array, then add those two. This ensures most additions of fractions are done on small fractions, and only the last few additions are really done on really big fractions.

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

how to handle a[0]>a[1] in B?(0 based indexing)

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

    In that case, at least one of the endpoints will have to be modified (either the lower bound (a[0]) is greater than the minimum element or the upper bound (a[1]) is smaller than the maximum element for any elements in a[2..n]). The core of the solution does not change in this case.

    → Reply
»
18 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Problem F is exactly the same with my idea.

→ Reply