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

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

We will hold Denso Create Programming Contest 2022(AtCoder Beginner Contest 239).

We are looking forward to your participation!

UPD: Due to the high volume of access to the server, we are currently unable to start the contest. We will postpone the contest start time to 22:00. Sorry for the inconvenience.

UPD.

This contest is now Unrated because we are unable to resolve the problem. We apologize for the inconvenience.

UPD:

This contest has been cancelled. We apologize for the inconvenience.

  • Проголосовать: нравится
  • +108
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +91 Проголосовать: не нравится

Is it me, or is Atcoder down right now?

UPD: Never mind, round will be unrated. Hard luck for the authors!! I hope the problem will be fixed before tomorrow's ARC.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +70 Проголосовать: не нравится

Am I seeing dreams??It is saying atcoder is temporarily unavailable

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +30 Проголосовать: не нравится

502 Bad Gateway

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +98 Проголосовать: не нравится
We are investigating, so please wait! !! !!

Chokudai (twitter)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

will it rated?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

Delayed?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Atcoder Down?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +55 Проголосовать: не нравится

Will it be postponed?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

502 Bad Gateway!!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Deferred by 1 hour

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I came here just to check if it is down for everyone or for me only.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

will the contest be postponed cause we have cf round today as well?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Official twitter: 【お知らせ】DBへの高負荷により、現在サイトが閲覧不能な状態になっております。ABC239を22:00~に1時間順延させていただきます。申し訳ありません。

1 hour delayed

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

503 Service Unavailable

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

delaying by one hour means making clash with global round.It's better to shift it to 14th February(Considering the fact that tomorrow is ARC)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +55 Проголосовать: не нравится

Tip: if you want to know if a website is down for everyone or just you, you may use the website https://downforeveryoneorjustme.com. Its short address is https://isup.me.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

The website is up now. Contest delayed by 1 hour.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think there will be clash of time between atcoder contest and cf global round. Can you consider postponing this contest to tomorrow?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Time delayed, I wish the server will turn good soon.

Spoiler
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It seems fixed now!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Rather then less participation they should postpond the round to some other day :)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

well it's overlapping by only 5 minutes so why not make it start 20 minutes earlier as website is fine now?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +50 Проголосовать: не нравится

Never have I ever thought I would see this day :(, I thought Atcoder was invincible

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

It seems that AtCoder hasn't been fixed completely. Hope the problem can be solved soon.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

Becomes unrated.

ABC239】復旧見込みが立たないため、22:00~開始できるか分からないため、このコンテストはUnratedとさせていただきます。申し訳ありません。 コンテストが開催可能な状態になれば、22:00~のコンテストは開催されます。

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Seems like some script kiddies creating huge loads.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +130 Проголосовать: не нравится

It's a special contest for me, heno239, but it just happened to be 502 Bad Gateway for this time X)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

I've never seen AtCoder like this. But I feel bad for the authors :(.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Will it be cancelled?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Rather than making it unrated you can postpone it to tomorrow

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Hope atcoder will resolve the problem at the ARC tomorrow.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

feel sorry for atcoder and hope to come back before tomorrow's ARC.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится
Upcoming Contests

Taking contest simultaneously?

UPD: ABC240 has been postponed to 2/20(Sun) 20:00

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Nice contest, especially liked problem F

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me the bug. It is failing on 1tc. submission

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Is it possible to solve E for larger k?

»
5 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +8 Проголосовать: не нравится

For problem D, If A,B,C,D<=1e5

We can use sieve of Eratosthenes to find all primes <= 2e5. The problem is asking if there is at least one number X in range A to B such that there is no prime in range X+C to X+D. This is equivalent to sum of prime[X+C]...prime[X+D]=0(where prime[i] is 1 if i is a prime). This can be solved in O(1) for each number in range A to B with prefix sums.

UPD: Actually, this doesnt work for 1e5 queries

  • »
    »
    5 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +1 Проголосовать: не нравится

    To solve the full bonus problem for $$$1e5$$$ queries and $$$A,B,C,D \lt = 1e5$$$:

    Solution
»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

QUES-1 The question just need the simple implementation.Just put the values and make sure to calculate with fixed precision .

Solution

QUES-2 The Ques was sligtly tricky.Must handle the -ve carefully.Got one WA too,but this also get cleared.

Solution

QUES-3 This was the good question ,firstly thought to try some circle property and then I thought to try all possible combination that will lead sqrt(5) as the distance. The implementation may be messy.

Solution

QUES-4 Great Example of Easy but looking Hard question. As the first turn is of Takahashi,hence everything depend on the Akoi .If he/she is able to find any number from c to d which give the sum prime,he is the winner ,otherwise Takahashi is the winner.The implementation is to take every prime from a+c to b+d in set and hence proceed according to question.

Solution
»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +13 Проголосовать: не нравится

I would be very thankful if anybody can prove that the following solution for Problem F is not correct:

Every time we try to add an edge between two components, we choose those who want the most degrees and merge them, instead of "add an edge between a connected component $$$X$$$ that wants $$$1$$$ degree, and a connected component $$$Y$$$ that wants $$$2$$$ or more degrees."

The solution above led to WA on random_22.txt & random_23.txt. See Submission #29471857.

Forgive me for poor English.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Can somebody please explain solution to the problem F (with proof), I don't get the proof behind the editorial's solution. Thanks.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

For those who don't know- Avoid writing i<v.size()-1 or i<v.size()-x as check condition for a loop. v.size() returns unsigned value and subtracting some +ve number results in some big value. Typecast v.size() to signed or use some method mentioned in here. First time paid cost for ignoring this warning warning: comparison of integer expressions of different signedness: ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} and ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wsign-compare] . Use to think, why does this warninig even exist?!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Am I the only fool who solved E with dfs + dp + segtree? any better solution?

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    For each node you can store the 20 highest values in a vector and after you apply dfs for the child add these 20 elements to the parent. Once dfs for all children are complete sort the parent vector and remove all elements except the first 20. You can see that each edge adds at most 20 elements from the child to parent so at max $$$((n-1)*20)$$$ elements are added to a vector before sorting.

  • »
    »
    5 лет назад, скрыть # ^ |
    ← Rev. 4  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Make use of the fact that K is 20.

    Let S[i] = multiset of at most 20 largest X values that are in subtree i

    do a normal dfs,

    if current node u is a leaf, S[u] only contains X[u]

    else merge S[v] to S[u] for all children v (S[v] has already been calculated)

    Notice that for any two sets to be merged, the size of each multiset is never > 20, so merge the multisets(use small-large merging for bigger K). If new size is >20(at most 40) keep removing smallest number until size of new Set is 20. For each query it is enough to check all elements in S[v] until reaching the kth one. It can be sped up with order statistics tree. Submission

    btw order statistics tree is basically a set, but to use as multiset, store the values as pair<value, num> where num is a unique value to differentiate between equal values

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

    ok let me paraphrase a little, I turned the problem into finding kth largest element in a subarray per query.Any easy way to do it without segtree?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Help Please!!!Why my solution for Promblem E lead to TLE?Submissions/29479674

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain G?