We will hold Denso Create Programming Contest 2022(AtCoder Beginner Contest 239).
- Contest URL: https://atcoder.jp/contests/abc239
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220212T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer:kyopro_friends,Nyaan
- Tester:math957963,sugarrr
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-500-600-600.
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.
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.
Am I seeing dreams??It is saying atcoder is temporarily unavailable
503 Service Temporarily Unavailable
502 Bad Gateway
same from me.
same,too
Build more pylons
Chokudai (twitter)
will it rated?
Delayed?
Atcoder Down?
Will it be postponed?
It will coincide with the global round!
Note that it would overlap only 5 minutes.
I need to have a rest. :(
I see. I thought you would use the abc as a warmup to the global.
Most of the time Problem G and H are not so easy for me.
Now you can have a 155 minutes' rest lol
Edit: I apologize for my mistake. I took 22:00 as Indian time by mistake.
Nah..., you shifted something by 30 minutes. It is actually 5 minutes overlap.
502 Bad Gateway!!
Same, is contest going to be delayed?
Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
Deferred by 1 hour
I came here just to check if it is down for everyone or for me only.
will the contest be postponed cause we have cf round today as well?
Official twitter: 【お知らせ】DBへの高負荷により、現在サイトが閲覧不能な状態になっております。ABC239を22:00～に1時間順延させていただきます。申し訳ありません。
1 hour delayed
503 Service Unavailable
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)
So it's rated or unrated?
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.
Isn't it showing down for everyone for every website? Or is it just me?
https://www.isitdownrightnow.com/ does the same as well.
Good. With one of these websites we can check the availability of every other website. With two of them we can check the availability of every website.
One can use
ping (your-site-here)in terminal if using linux based os. Pretty fast and easy.It does not tell you if a website is down for everyone or just you, does it?
https://www.isitdownrightnow.com/atcoder.jp.html
It Does.
You have probably got a notification that I responded to your comment and saw another comment instead. Your website is ok.
The website is up now. Contest delayed by 1 hour.
no it isn't
It was for a brief amount of time.
ok well sorry then
I think there will be clash of time between atcoder contest and cf global round. Can you consider postponing this contest to tomorrow?
The website is not working consistently. The best solution would be to postpone the contest for tomorrow.
Time delayed, I wish the server will turn good soon.
It seems fixed now!
Rather then less participation they should postpond the round to some other day :)
By that time they can work on the system issues & we wont not miss a beautiful set of problems :)
well it's overlapping by only 5 minutes so why not make it start 20 minutes earlier as website is fine now?
Never have I ever thought I would see this day :(, I thought Atcoder was invincible
It seems that AtCoder hasn't been fixed completely. Hope the problem can be solved soon.
Becomes unrated.
ABC239】復旧見込みが立たないため、22:00~開始できるか分からないため、このコンテストはUnratedとさせていただきます。申し訳ありません。 コンテストが開催可能な状態になれば、22:00~のコンテストは開催されます。
Seems like some script kiddies creating huge loads.
It's a special contest for me, heno
239, but it just happened to be 502 Bad Gateway for this time X)Petition to no next contest
ABC 239.5.Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
I've never seen AtCoder like this. But I feel bad for the authors :(.
Will it be cancelled?
Rather than making it unrated you can postpone it to tomorrow
Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
Hope atcoder will resolve the problem at the ARC tomorrow.
feel sorry for atcoder and hope to come back before tomorrow's ARC.
Start Time Contest Name
2/13(Sun) 20:00 ◉ AtCoder Regular Contest 135
2/19(Sat) 20:00 ◉ Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)
2/19(Sat) 20:00 ◉ AtCoder Beginner Contest 240
2/26(Sat) 20:00 ◉ AtCoder Beginner Contest 241（Sponsored by Panasonic）
Taking contest simultaneously?
UPD: ABC240 has been postponed to 2/20(Sun) 20:00
Nice contest, especially liked problem F
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 :/
Can anyone tell me the bug. It is failing on 1tc. submission
Is it possible to solve E for larger k?
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.
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…..
euler tour + persistent segment tree
Just do Mo's algorithm. Submission
Or Parallel Binary Search algorithm in $$$\mathrm{O}(n+q\log^2 q)$$$ time.
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
To solve the full bonus problem for $$$1e5$$$ queries and $$$A,B,C,D <= 1e5$$$:
The problem is asking "Is 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 "Is there is at least one number $$$X$$$ in range $$$A$$$ to $$$B$$$ such that the next prime number from $$$X+C$$$ is at least $$$D-C+1$$$ numbers away?"
As $$$A$$$ to $$$B$$$ is a range of consecutive numbers, this is also equivalent to "Are there $$$2$$$ primes with the smaller one in the range of $$$A+C$$$ to $$$B+C$$$ such that their gap is at least $$$D-C+1$$$?"
Use sieve of Eratosthenes to find all primes $$$<= 2e5$$$. Calculate a $$$dp$$$ array, where $$$dp[i] =$$$ distance from number $$$i$$$ to last prime number, for all $$$i$$$ from $$$2$$$ to $$$2e5$$$
transition: $$$dp[i] =$$$ $$$0$$$ if $$$i$$$ is prime, else $$$dp[i] = 1+dp[i-1]$$$); // is_prime($$$i$$$) is gotten in $$$O(1)$$$ with sieve
For a query: if there is any $$$i$$$ in range $$$A+D$$$ to $$$B+D$$$, such that $$$dp[i]$$$ is at least $$$D-C+1$$$, answer is Takahashi, else Aoki
Instead of checking each dp value in the required range, we can just take the maximum dp value in the range and compare with $$$D-C+1$$$.
This becomes range max query which can be easily done quickly with a Segment Tree or Sparse table. Submission
QUES-1 The question just need the
simple implementation.Just put the values and make sure to calculate withfixed precision.QUES-2 The Ques was sligtly tricky.Must handle the
-ve carefully.Got one WA too,but this also get cleared.QUES-3 This was the good question ,firstly thought to try some
circle propertyand then I thought to try all possible combination that willlead sqrt(5) as the distance.The implementation may be messy.QUES-4 Great Example of
Easy but looking Hardquestion. As the first turn is of Takahashi,hence everything depend on the Akoi .Ifhe/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 froma+c to b+din set and hence proceed according to question.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
WAonrandom_22.txt&random_23.txt. See Submission #29471857.Forgive me for poor English.
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
EDIT: sorry I misunderstood your alg, thought I came up with a counterexample but I don't think it's quite right.
Consider this graph with the the required degrees as
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)$$$.
works in my case, produces the correct output code
The comment was intended for CharlesWuQiushi
For your code, you can try this testcase:
Thank you very much... and thanks everybody who has tried to hack my solution. I've never considered such condition. I got
ACafter adding the following snippet: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.
Thank you very much!
I got
WA random_23before.My code worked out a wrong answer in your input.
I added this and it got
AC!Can somebody please explain solution to the problem F (with proof), I don't get the proof behind the editorial's solution. Thanks.
For those who don't know- Avoid writing
i<v.size()-1ori<v.size()-xas check condition for a loop.v.size()returns unsigned value and subtracting some +ve number results in some big value. Typecastv.size()to signed or use some method mentioned in here. First time paid cost for ignoring this warningwarning: 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?!Am I the only fool who solved E with dfs + dp + segtree? any better solution?
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.
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
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?
I solved by DFS + priority queue. No segment tree involved. Submission
Help Please！！！Why my solution for Promblem E lead to TLE？Submissions/29479674
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
Can someone explain G?