chokudai's blog

Denso Create Programming Contest 2022(AtCoder Beginner Contest 239) Announcement
By chokudai, history, 3 years ago, In English

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.

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

Comments Comments (94)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +91 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +70 Vote: I do not like it

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

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

    503 Service Temporarily Unavailable

    → Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

502 Bad Gateway

→ Reply
»
3 years ago, # |
  Vote: I like it +98 Vote: I do not like it
We are investigating, so please wait! !! !!

Chokudai (twitter)

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

will it rated?

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Delayed?

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

Atcoder Down?

→ Reply
»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

Will it be postponed?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +83 Vote: I do not like it

    It will coincide with the global round!

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

      Note that it would overlap only 5 minutes.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +63 Vote: I do not like it

        I need to have a rest. :(

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

          I see. I thought you would use the abc as a warmup to the global.

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

            Most of the time Problem G and H are not so easy for me.

            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          Now you can have a 155 minutes' rest lol

          → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 4   Vote: I like it -10 Vote: I do not like it

        Edit: I apologize for my mistake. I took 22:00 as Indian time by mistake.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Nah..., you shifted something by 30 minutes. It is actually 5 minutes overlap.

          → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

502 Bad Gateway!!

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

Deferred by 1 hour

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

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

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

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

1 hour delayed

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

503 Service Unavailable

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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)

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

So it's rated or unrated?

→ Reply
»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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.

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

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

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

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

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

    The website is not working consistently. The best solution would be to postpone the contest for tomorrow.

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

It seems fixed now!

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

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

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

    By that time they can work on the system issues & we wont not miss a beautiful set of problems :)

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Becomes unrated.

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

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

Seems like some script kiddies creating huge loads.

→ Reply
»
3 years ago, # |
  Vote: I like it +130 Vote: I do not like it

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

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

Will it be cancelled?

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

Rather than making it unrated you can postpone it to tomorrow

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

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

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

Hope atcoder will resolve the problem at the ARC tomorrow.

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

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
Upcoming Contests

Taking contest simultaneously?

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice contest, especially liked problem F

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

    I tried to solve the more complected problem where we have to build n+m-1 new vertex, before finally noticing that this does not fit the first sample :/

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

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

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

Is it possible to solve E for larger k?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can process the queries offline. Group the queries by node, then run a dfs on the tree. At each node, aggregate the values that are present in the subtree of that node. This can be maintained efficiently using the smaller-to-larger merging technique. The last piece is that you can answer order statistic queries efficiently if instead of a normal tree set you use an order statistic tree.

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

      I actually submitted that using pbds order statistic tree (didn’t notice the constraint on K before solving), unfortunately it TLE’d on some cases…..

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    euler tour + persistent segment tree

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

    Just do Mo's algorithm. Submission

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Or Parallel Binary Search algorithm in $$$\mathrm{O}(n+q\log^2 q)$$$ time.

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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

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

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

    Solution
    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

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.

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

    I did that, sort all components based on number of needed edges in descending order, then merge 1st component with the remaining from 2nd to last using small-large merging. If it is not possible to merge largest component(0 needed edges) and there are still components that have not been merged, answer is -1: Submission

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

    EDIT: sorry I misunderstood your alg, thought I came up with a counterexample but I don't think it's quite right.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Consider this graph with the the required degrees as

    4 2
2 1 2 1 
1 4
3 4

    Node $$$4$$$ already has a degree of two, hence a final degree of 1 is not possible. So the answer is $$$-1$$$ but your solution incorrectly produces an output of $$$(3, 2)$$$.

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

      works in my case, produces the correct output code

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        The comment was intended for CharlesWuQiushi

        For your code, you can try this testcase:

        Input
        A Possible Configuration
        Your Output
        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much... and thanks everybody who has tried to hack my solution. I've never considered such condition. I got AC after adding the following snippet:

      for (int i = 1; i <= m; ++i)
	read (x, y), add_e (x, y), add_e (y, x)
	, --d[x], --d[y];
for (int i = 1; i <= n; ++i)
	if (d[i] < 0) return puts ("-1"), 0;

      This algo may be really acceptable. In my procedure, every connected component ultimately requires exactly $$$2$$$ or $$$1$$$ edge(s), which is similar to what explained in official editorial, or it's definitely impossible to construct a tree.

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

      Thank you very much!

      I got WA random_23 before.

      My code worked out a wrong answer in your input.

      I added this and it got AC!

      rep(i, n)if (d[i] < 0) {
        cout << -1;
        return;
    }
      → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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?!

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

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

    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

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

    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?

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

Help Please！！！Why my solution for Promblem E lead to TLE？Submissions/29479674

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Rather than inserting values of all nodes in subtree into vector of vector F , insert only 20 biggest values , you can use vector of multiset for that

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

Can someone explain G?

→ Reply