atcoder_official's blog

AtCoder Beginner Contest 439 Announcement
By atcoder_official, history, 4 months ago, In English

We will hold AtCoder Beginner Contest 439.

We are looking forward to your participation!

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

»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi, that will be my first contest. Anyway, good luck everyone.

→ Reply
»
4 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

hahaha!

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

Good luck!

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

Gave the contest. It was good. When and where can I find the editorial for this contest ?

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

What a big difficult gap between F and G.

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

I solved 5 problems. Got confused on problem E for a long time...

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

is E sweep line ?

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

Happy New Year! And it's a great contest as a gift for 2026, because A~F are very easy and G is challenging for advanced contestants.

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

Great contest! I solved 5 problems.(A — E)

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

got 3 WAs on B because I forgot that YES is not Yes ;((

I really have to start getting more used to early morning programming...

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

E was such a pain, I recognised LIS — knew had to handle consecutive same elements somehow.

I only tried with sorting in increasing a and then increasing b.

Editorial shows answer breaking ties by decreasing b?

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

In case anyone got 5 wa in E (Kite) like me, consider following testcase: 5 1 1 2 2 3 1 3 2 3 3 expected ans: 3 and not 2.

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

If we have an array $$$P_0, P_1, P_2, \dots, P_N$$$, how to compute $$$\sum_{t=1}^{N}(1 - P_t)^{i - 1} \cdot P_t \cdot (1 - P_{t - 1})^{L - i}$$$ for each $$$i$$$ from $$$1$$$ to $$$L$$$ fast?

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

    Change the loops. Instead of looping over $$$t$$$ (The number of turns) by fixing the $$$i$$$-th player, fix the turn and loop over $$$i$$$. Then it turns into a geometric series.

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

      I want the value of that summation for each $$$i$$$ separately not the sum of it over all $$$i$$$.

      → Reply
      • »
        »
        »
        »
        4 months ago, hide # ^ |
         
        Vote: I like it +10 Vote: I do not like it

        Sorry I wasn't clear enough. It turns into a geometric series and we can use a generating function to solve it.

        Group the terms depending on $$$i$$$ as $$$B_t$$$ and the terms independent of it as $$$A_t$$$. Now the loop is $$$\sum_{t=1}^N A_tB_t^i$$$. Now make a polynomial $$$\sum_{t=1}^N A_t(B_tx)^i$$$ by summing for each $$$i$$$. The closed form of this polynomial is $$$\sum_{t=1}^N \frac{A_t}{1-B_tx}$$$. This is a sum of rational polynomials that can be added by DnC. The answer for person $$$i$$$ is the coeffecient of $$$x^i$$$.

        (Btw for G, in this sum we actually don't want $$$(1-P_t)^{i-1}$$$ which means (presumably) the probability that the first $$$i-1$$$ people didn't win in the $$$t$$$-th turn. We actually want the probability that the first $$$i-1$$$ people didn't win in ANY OF the first $$$1,2,\cdots t$$$ turns. Similar in the term for the last $$$L-i$$$ people. So we need to use the prefix sum of the probabilities in these two parts)

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

Original problem for E:https://www.luogu.com.cn/problem/P2782

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

This is what G made me think:

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

why getting wrong answer on 3rd 

int t=1;
    while (t--) {
        int n;
        cin >> n;
        int i=1;
        vector<int>ans;
        int cnt=0;
        for(int i=1;i*i*1ll<=n;i++){
            for(int j=i+1;((i*i*1ll+j*j*1ll)*1ll)<=n;j++){
                ans.push_back((i*i*1ll+j*j*1ll)*1ll);
            }
        }
        sort(ans.begin(),ans.end());
        // cout<<ans.size()<<endl;
        // help(ans);
    }
→ Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You need to check whether a number n has exactly one pair. For example, 8^2 + 1^2 = 65 and 7^2 + 4^2 = 65, 65 has two pairs, and therefore it should not be counted.

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

      but why this fails like u have x^2 + y^2 = n so instead of checking for x and y fix x and put x+1 then x+2 till not exceeding n

      now here x can go at mask root n and y can also go max root n so rootn * rootn which is n and n =1e7 ?then why like i am not getting TLE i am getting wrong answer

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

        root(1e7) = 3000+... so total num of operations like 1e6+... it can easily pass. for wa, you need to check each number appear exactly 1 times , otherwise not count. this might help you:link

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

I solved E but my solution was surprisingly complex for E. Segment tree + input compression + sweep. I read that some people solved it with LIS. Do you mean actually reducing the problem to LIS or did you implemented a similar solution to LIS but maintaining best sequences for 2 types. Those that ends on a segment directed in bottom-right and those directed to top-right?

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

    If you reorder pairs by A increasing, then getting LIS on B's gives you some valid non-intersecting subset and it is easy to show that this is the solution if all A's are different.

    Now, if A's collide, you can break the tie by B's decreasing. Now you can't take two elements of same A so LIS is still the answer.

    and the general LIS algo is what you need

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

      Thank you @Kikos

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

      When A's collide, can't we only use the minimum B for such elements. Because anyways, we can only take one element from all these with same A, and choosing the minimum is the best since LIS also does only that. But, this gives wrong answer on some test case. I don't know why. Have been stuck on it for a while. Would appreciate some help

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

        a = [1, 2, 2, 2, 3] b = [2, 1, 3, 5, 4]

        You can't take neither min or max element with a=2, if you want it to fit nicely into 1-2-3 sequence

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

gl & hf!

→ Reply