atcoder_official's blog

AtCoder Beginner Contest 405 Announcement
By atcoder_official, history, 17 months ago, In English

We will hold AtCoder Beginner Contest 405.

We are looking forward to your participation!

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

Comments Comments (32)
| Write comment?
»
17 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I found it very hard to improve my AtCoder rating at the time I reached 2000.

I have to go to evening self-study session every Sunday night, which just the same time as ARCs are running :(

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

    I am still struggling to reach 2000, my highest rating is 1911 and now I am only 1700+, and still dropping.

    → Reply
»
16 months ago, hide # |
← Rev. 3  
Vote: I like it +3 Vote: I do not like it

I'm too bad at counting problems :(

How to solve $$$E$$$?

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

Where is your mother, the problem author of G?

I use combination to calculate the answer, the total time complexity is $$$O(n^{1.5})$$$. But I got TLE as a result.

Why do you treat the constant factors so hard? Maybe you are in need of family members?

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

    In fact, the answer is (sum of sz[i])! / mul(sz[i]!) so you only need to maintain 2 things, making it faster than calculating C(N, K).

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it -7 Vote: I do not like it

      But the difference of calculating the answer is not the main part of this problem.

      What's more, many people got TLE because of constant factors though they didn't use comb to calc the ans.

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

BFS got TLE in D, anyone help?

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

    are you sure? mine

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

      gosh, I BFS the whole matrix from every 'E' and did time-wasting things to ensure the
      shortest distance, I didn't even think about it

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

        But that is necessary isn't it ? We need to find the nearest emergency exit, not any exit. The official solution also does plain bfs, but how do they ensure that we are always pointing towards the nearest exit ?

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

          Since the bfs runs on an unweighted graph, the first time any bfs comes to a particular node is the shortest distance from some 'E' to that node.

          It's like, imagine a turtle exiting each 'E' node, labelled 'E1', 'E2' etc for each unique 'E'. Now, at each node, it divides into as many turtles as there are possible routes emerging from that cell (4 at max, if there are no walls and all surrounding cells are unvisited). They obviously maintain the same label 'Ei'. Now, since all the turtles left each 'E' at the same time, the FIRST turtle reaching a particular cell bearing some marker 'Ei' signifies the shortest distance.

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

someone please help me with E. I have never done something with placements type thingy.

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

    C(n + k — 1, k — 1) for putting n same balls into k different buckets(allow none)，mine

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

      Can you explain a litttle bit more of your idea

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

        This is my way of thinking:

        The first observation is that bananas (b) and grapes (g) will come to the right of all apples.

        Suppose that there are x oranges to the right of the last apple. Now, you first need to arrange a — 1 apples before the last apple. The no. of ways to do this is C(a + o — x — 1, a — 1). Now, to the right of the last apple, x + b + g positions remain. On fixing the positions of bananas, the positions of oranges and grapes will also get fixed. This would be C(x + b + g, b).

        Iterate over x = 0 to o and add C(a + o — x — 1, a — 1) * C(x + b + g, b) to the answer.

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

Who wrote E ???

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

    If there are $$$a$$$ apples, $$$o$$$ oranges, $$$g$$$ grapes, $$$b$$$ bananas:

    We let $$$n=a+o+g+b$$$.

    If we have determined the positions of apples and bananas, the positions of grapes and oranges are also determined.

    Besides, for every valid way to put the apples and bananas, we can also find a valid way to put grapes and oranges.

    Therefore, we can let $$$i \in [a,n-g-b] $$$, which means the last position in all the apples.

    So, for each $$$i$$$, the answer is $$$C_{i-1}^{a-1} \times C_{n-i}^{b}$$$, as we can put apples in $$$[1,i-1]$$$(the position $$$i$$$ must be placed with an apple), and put the bananas in $$$[i+1,n]$$$.

    My Submission

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

Who can tell me why my program was wrong!!!

#include<bits/stdc++.h>
using namespace std;
long long a,o,b,g,inv[4000005],chu[4000005],f[4000005];
const long long p=998244353;
long long C(long long n,long long m){
	if(m==0)
		return 1;
	if(n<m)
		return 0;
    return f[n]%p*chu[n-m]%p*chu[m]%p;
}
int main(){
	cin>>a>>o>>b>>g;
	f[0]=1,inv[1]=1,chu[1]=1;
	for(int i=1;i<=4e6;i++)
        f[i]=f[i-1]*i%p;
    for(int i=2;i<=4e6;i++){
        long long k=p/i,r=p%i;
        inv[i]=((p-k)*inv[r])%p;
        chu[i]=(chu[i-1]%p*inv[i]%p);
    }
    long long ans=0;
    int n=a+o+g+b;
    //cout<<C(100000,1000)<<" ";
    for(long long i=a;i<=n-g-b;i++)
    	ans=(ans+C(i-1,a-1)*C(n-i,b)%p)%p;
	printf("%lld",ans);
	return 0;
}
→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why isn't the submit button working? I'm selecting a language and it is automatically removing the selection of the language and giving me error

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

I solved F in an offline way with BIT. 1 pass from left to right to find segments [A, B] such that A < C < B < D. 1 pass from right to left to find segments [A, B] such that C < A < D < B.

What is the solution provided by the editorial? Seems like a pretty common technique. Anyone has deeper materials on that topic?

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

someone please help me with problem G. Why my program is wrong? I've tasted it in many test cases but I cannot see the mistake

https://atcoder.jp/contests/abc405/submissions/65704475

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

I have a problem on G.

There is 10 wrong answer in my submission.

HELP

my submission

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

    Because sometimes your nums frequency can be negative, and then what is his inversed elements?

    you should revise your implementation of the MO algorithm so that there are no negative frequencies

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

I learned Mo’s algorithm + square-root decomposition in G :)

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

Was it the new record by number of participants? ~685x20

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

My original account disappered after this competition without notice.If there is anyone know that's why?

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

can anyone tell is my approach wrong or my implementation is not correct for problem F

for finding the number of intersected line i m subtracting sum of line segments that completely lie on either side of the arc (made by the queried line segment) from the total number of line segments using Merge Sort Tree

Submission

→ Reply