Hi, Codeforces!
Alexdat2000, Igorfardoc, and I are pleased to invite you to our Codeforces Round 890 (Div. 2) supported by Constructor Institute, which will be held on Aug/05/2023 17:35 (Moscow time). This round will be rated for participants with a rating lower than 2100.
We would like to thank:
- errorgorn for coordinating the round.
- mzen, maomao90, thenymphsofdelphi, Dominater069, Mike4235, cadmiumky, irkstepanov, zengminghao, Gheal, DeMen100ns, FEDIKUS, thanhchauns2, MinaRagy06, Java, xudian, madlogic, squishybanana04, stefanbalaz2, kobebryan9, Murinho, IlyinAD, chha_aa07, Pemguimn, the_hyp0cr1t3, STommydx, peshkoff, AndZhi, revelcoS, Valenz, and tibinyte2006 for testing the round and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon.
You will be given 5 problems, one of which is divided into two subtasks, and you will have 2 hours to solve them.
One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.
The score distribution is 500 — 750 — 1250 — 2000 — (1500 — 1500)
UPD: Tutorial
UPD2: Congratulations to the winners!
Div. 2:
Div. 1:
We are thrilled to share some exciting news with you! We are teaming up with our partner, Constructor Institute in Schaffhausen, Switzerland, to bring you an amazing opportunity: a round supported and organized in collaboration with Constructor Institute, where you can explore Master's programs in Switzerland. Now we pass the floor to our partner.
Hello, Codeforces community!
Constructor Institute in Schaffhausen (Switzerland) is pleased and proud to have the opportunity to support the round on Codeforces. We invite you to participate in it!
If you are passionate about studying in Switzerland and pursuing a Master’s degree, we encourage you to fill out the form to initiate the application process and scholarship interview. Our Institute representatives will be in touch with you to guide you through the next steps.
We offer two Master programs, both taught in English, with flexible duration of 1.5 or 2 years full-time:
- MSc in Computer Science, Software Engineering, and Leadership
- MSc in Quantum Software Engineering, and Computer Science
Our Master's programs open doors to a world of opportunities. Many of our students have secured high-profile roles in multinational companies in Switzerland and across the globe. Additionally, our programs also serve as an excellent preparation for Ph.D. research in fields such as software engineering, cybersecurity, artificial intelligence, and other advanced topics.
We understand that financing your education can be a concern, and to support your journey, we are offering the following scholarships:
- Tuition waiver scholarships — 20,000 CHF per year, covering the cost of tuition fees.
- Full scholarships — 20,000 CHF per year, covering the cost of tuition fees, along with a monthly stipend of 2,000 CHF to assist with living expenses in Schaffhausen.
Both scholarships are non-repayable, providing you with financial peace of mind.
To learn more about Constructor Institute and its programs, visit our webpage.
Eligibility for the programs and its available scholarships:
- You have obtained or you will obtain a Bachelor’s degree in Computer Science, Software Engineering, Physics, or a related field before the program starts.
To express your interest in this opportunity, please complete the form:
We wish you good luck in the competition and enjoy solving the problems.
Omg Igorfardoc round!
Omg sponsored div2 round!
It will be interesting if Mike and the team can share how they prepare a contest.
So we can understand your efforts and hard work to conduct a contest.
Yes, I agree as I believe it would greatly deepen all participants' understanding of the contest if the authors can share with us the problem statements beforehand.
Problem statements won't help me. They should provide editorials for the questions before-hand
Editorials won't help me, They should provide Author's solution before hand.
Author's solution won't help me, They should hand me my -100 rating before hand
I think he meant after the contest.
Getting Problem statements before the round will be very useful to prepare for round.
Go to catalog section. There you'll get most of your answers.
can i expect constructive algo problem? as it was sponsored by constructor institution
Oh hell no
As a tester, I thought the problems were nice, and I recommend participating in this round!
As a tester, I hope my enjoyment when testing the round would be indicative of your enjoyments when participating in it.
orz tibinyte2006 testing round !!!
Hope to become cyan!
Hoping to reach specialist this time.
All the Best shrey_17sept
Hope to become specialist before arrival of Joyboy
manga readers...
garp is in danger
Hope to be constructive(as this round)
As a tester, I really enjoyed this round! Everyone should participate!
My favourite pokemon !
I say a full constructive and a happy specialist for me. gl everyone!
As a participant i recommend all of you to participate.
As a tester, good luck! (And give me contribution)
Based on the score distribution, I think this round would be speedforces.
Hiha, this round is going to be fun! >_<
hoping to become pupil again
As a tester, problems is excellent and cute :>
This Constructor Institute, it's the former "Schaffhausen Institute of Technology", right? Is it going to obtain (or maybe already has) accreditation any time soon? I also wonder what's the connection with Constructor University Bremen... They seem to share the logotype.
As a tester, ris noitubirtnoc em evig esaelp
Is this a hint to one of the problem :>
Use reverse(str.begin(), str.end()); :p
good try
Round Clashing with Leetcode Round
Codeforces > Leetcode
hope i can ac C problem ：）
Thanks,Constructor Institute.
Hope I can be a master.
5 problems? I think it will be hard.
actually 6 problems,because one of the 5 problems is divided into two subtasks
Hoping to become pupil this contest
preparing for permutation problems :) DYK? A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
It's good to see that cf is finally improving on their problem statements.
For me, this was the coolest contest I've been to in the last couple months. Namely in the fact that the tasks mostly do not require knowledge of complex algorithms, all the solutions are quite short. Thank you! And a question. in E2 n = 1e6 to prevent bitset O(n^2/64) solutions?
I'm fed up with these constructor algo problems.
A: If a[i]<=a[i+1], then 0 <= max(0, a[i+1]-1) and a[i]-1 <= a[i+1]-1 <= max(0, a[i+1]-1), therefore max(0, a[i]-1) <= max(0, a[i+1]-1), then a[i]<=a[i+1] holds after any times of operation. If a[i]>a[i+1], we need to perform a[i] operations to make a[i]=a[i+1]=0. So the answer is max(a[i]) where a[i]>a[i+1].
B: If n==1 there's no solution, let's assume n>=2. Let t be the number of occurences of 1 in a[i]. If t==0, then we can let a[1]+=n-1 and a[i]-=1 (2<=i<=n). Let's assume t>=1. Then sum(i: a[i]==1)(b[i] — a[i]) >= t because b[i] is positive integer and b[i]!=1, so b[i]>=2. Therefore, sum(i: a[i]!=1)(b[i]-a[i]) <= -t --> sum(i: a[i]!=1)(a[i]-b[i]) >= t --> sum(i: a[i]!=1)(a[i]-1) >= t. So if sum(i: a[i]!=1)(a[i]-1) < t, there's no solution. Otherwise, we can construct a solution: First turn 1 into 2, then we reduce the maximum element in a by 1 for t times. If there's some a[i] remain unchanged, then a[i]>1, then we can reduce them by 1 and add them to any occurence of 2.
C: For any 1<=i<=n-1, let's find the maximum value it can become by binary search. Assume the value we are checking is T. Then we need T-a[i] operations on i-th element. If a[i+1]>=T-1 then we are done. Otherwise, we need T-1-a[i+1] additional operations on (i+1)-th element, Then check if a[i+2]>=T-2. We repeat this process until we find some j such that a[i+j]>=T-j, or we have used more than k operations. Then we can solve the problem in O(n^2*log(k)).
D: We can solve the problem by D&C (Divide and Conquer). Assume we need to find the index of maximum element on [L, R]. If L==R then the answer is L. If L+1==R, we can do query(L, R) and the answer of query is 1 if p[L] is the maximum (0 otherwise). In general cases, we choose M close to (L+R)/2 and solve (L, M) and (M+1, R) recursively, assume their answer be x, y. Then we only need to find if p[x]<p[y]. Let's do query(x, y) and query(x, y-1), the difference of answer of the queries means "there are how many i such that x<=i<=y-1 and p[i]>p[y]". If p[x]<p[y], then we have p[i]<=p[x]<p[y] for x<=i<=M and p[i]<p[y] for M+1<=i<=y, so the difference will be 0. Otherwise we have p[x]>p[y], so the difference will be at least 1. Then we can solve the problem. The cost of queries will be not greater than 2*n^2 for the top layer, 4*(n/2)^2 = n^2 for the second top layer, 8*(n/4)^2 = n^2/2 for the third top layer and so on. So the total cost is not greater than n^2*(2+1+(1/2)+(1/4)+...)=4*n^2.
For C, how does O(n^2*log(k)) pass so seamlessly if n=1000 and n^2*log(k) = about 2e9?
Edit: Soz idk why I thought n^2 = 1e8 imma kms
$$$n^2 \log_2 k = 1000 \cdot 1000 \cdot \log_2 10^8 \approx 10^6 \cdot 26 = 2.6 \cdot 10^7$$$, not $$$2 \cdot 10^9$$$
1000*1000*20 = 2e7...
your maths is blowing my mind
log_2(1e8)~= 26,n^2= 1e6n^2lgk~= 2.6e7$$$O(n^2)$$$ has very little constant, and if you count $$$n*n*log(1e9)$$$, it's actually $$$30'000'000$$$
We can optimise the min max range to
.
In B why can't we just jumble up the elements of the array such that a[i]!=b[i] and all elements will remain same so the sum of array a will be equal to array b ?
because you can have an arr=[2,2,2] and still come up with answer [1,1,4] while if you try to jumble you will still end up with having the same array.
How to approach C problem anyone??
binary search on answer.
binary search to find the maximum possible $$$a_i$$$ we can make for every $$$i$$$
YocyCraft's solution is good — in order to find it, you probably have to make the observation, that it has to be optimal to increase only one segment of numbers. After that, you can try starting that segment at every number.
Note that we can binary search the answer, as the following gives rise to a monotonic function -
We ask the simpler question: "Is the value
Xattainable after at mostkoperations?"Since the constraints on n are small enough, an
O(n^2)solution suffices.Loop through the array, checking if we can make this current element equal to
X. We can calculate the cost required to make this element equal toX, by simulating the process, making sure that the next element is adjusted appropriately using recursion. If we can afford the cost, then we say that we can attainX. Otherwise, we are unable to achieveX.Careful implementation must be done, but this is the general overview of the logic.
Ough, probably I need to learn binary search, as I didn't try to use it and wrote $$$O(n^2)$$$ solution, which I thought is very difficult for $$$C$$$ problem.
Could anyone please tell me how my E1 question didn't pass the test 7?
correct output is 4
My first subbmission can pass this test case
Thank you so much.
It seems like you should update your dp values from n to 1 instead of from 1 to n, otherwise you could have updated some larger values before you visit it.
Oh my God, this mistake is so classic. I can't believe I made it again.
I made exactly the same mistake during the contest orz.
E2，seems to be bad. why 1e6.
so any hint?
We wanted to force $$$O(\frac{n\sqrt n}{32})$$$ complexity. Although $$$O(n \log^2 n)$$$ FFT methods can also pass. I think it is suitable for div 2 round to make the last problem more "educational".
Is this the reason why E1 is so basic?
Many people using 2log FFT didn't pass. The bitset solution is not educational, just very intentional and unnatural. Your goal is to educate, not to show off.
what is 2log FFT btw?
Guess: it is divide and conquer and performing FFT on each array $$$O(n*log(n))$$$
hence $$$n*log^2(n)$$$
divide and conquer + FFT
thanks
Do you know how it feels like to only come up with a $$$\mathcal O(n\log^2 n)$$$ solution when $$$n = 10^6$$$?????? I thought about the 2log FFT for almost an hour and struggled on how to optimize it, but you finally tell me it actually is intended solution?????????
$$$\mathcal O(\dfrac{n^{1.5}}{w})$$$ is a totally brute, I agree with you. But that doesn't mean you have to limit it ———— It can still pass, it's not a big number. From a progressive perspective, this is a worse solution, indeed. but within the scope of programming competitions, some things just simply cannot be hacked. Come on, Codeforces don't have Quantum machines; I don't think it is allowed for you to enlarge the data range at will.
I think it's so bad, really. It's not a joke. Nor E2 problem itself is educational.
I'm not saying it is an intended solution, it's not. I am saying that it is possible to get AC with it with some optimizations. The intended solution is the $$$O(\frac{n \sqrt n}{32})$$$. It is just that we are not concerned whether or not the alternative $$$O(n \log^2 n)$$$ will TLE or AC.
I'm personally not sure how my comment got intepreted as $$$O(n \log^2 n)$$$ is the intended solution...
Oops, it seems that we have some different understandings on your word "force"......
So since you are not concerned about the alternative solution, why don't you just reduce the data range to $$$5\times 10^5$$$ or less? You say that you are not concerned. And in that case, all $$$\mathcal O(\frac{n^{1.5}}{w})$$$ solutions will definitely pass without caring about constants.
The word "force" is used here to mean that we wished to separate $$$O(n^{1.5})$$$ and $$$O(\frac{n^{1.5}}{w})$$$. In fact, a tester (mzen) submitted $$$O(n^{1.5})$$$ that we are still unable to hack.
To suggest to contestants to contests that we do not want to accept $$$O(n^{1.5})$$$, we made constraints much bigger than normal $$$O(n^{1.5})$$$ problems.
Edit: mzen's solution is described in their comment at https://mirror.codeforces.com/blog/entry/119058?#comment-1055388
You think the impression is more important than the actual? You want people to think nsqrtn as unpassable, but some people still could pass? You are just like the ostrich who sticks its head in the sand.
But seems that many $$$O(\frac{n \sqrt n}{32})$$$ solutions didn't passed?
Well, we are sorry about that then.
I thought that our solution (which ran in ~1200ms) already had rather large constant. We use stl bitset with the variable bitset trick from https://mirror.codeforces.com/blog/entry/100910?#comment-896029. I'll have to see what bitset implementations people are using for future contests.
It seems that some solutions used dfs to walk the tree and got RE,and if we change it to loop from $$$n$$$ to $$$1$$$,it could AC.
i also use O(n*sqrt(n)/32) and it is just 749ms as you can see it here : https://mirror.codeforces.com/contest/1856/submission/217710498
I heard some of my friends used FFT and got TLE,and some got PP;And I also found some implemented-nice bitset solutions passed,and some bad $$$O(\frac{n \sqrt n}{32})$$$ solutions got TLE.Is this really suitable for a CF contest?
How to solve it with FFT in $$$\log^2 n$$$? I can only understand how to do it in $$$\log^3 n$$$
hint for E2?
I haven't solved it, but it looks like $$$O(n^{1.5})$$$ knapsack
I boiled to problem to:
solve the following problem for each $$$i$$$ from 1~n:
denote a = $$$[sz_v]$$$, where $$$v$$$ is all the direct sons of $$$i$$$ and $$$sz_i$$$ denotes the subtree size of $$$i$$$. find a subset of $$$a$$$ $$$v$$$ such that $$$\sum v$$$ multiplied by $$$\sum a-\sum v$$$ is maximum.
but i don't know how to solve this:( seems that top performers used some sort of crazy stuff lol
Intended complexity is $$$\mathcal{O}(\frac{n\sqrt{n}}{32})$$$. The key idea is that the total sum of values for the knapsack isn't too large. So the number of distinct elements is small. See https://mirror.codeforces.com/blog/entry/49812 for details.
I did exactly this but didn't AC
The $$$\frac{1}{32}$$$ factor is actually significant! In your solutions, I see that you either
vector<int>(which doesn't help)vector<bool>which is a bitset, but you do not use bitwise operations on it (shift + or, instead of manual loop).I didn't know we could do bitwise operations on vector of bool. Either ways, that's a stupid thing to trap a solution on, I think bounds should have been looser
Wow, thanks
Anyone who had wa7 on e1, how did you deal with it?
thanks you people_plus_plus for great testcase, now I know that I don't know how to use knapsack properly
i wish all cf problem statements are like this contest. even though I did badly in it.
Any idea for E1? I thought of a dfs approach, in which I visited every node and counted the total number of nodes in it's subtree. Then according to the number of immediate children to the node, I tried dividing the total number of nodes in the subtree into two groups such that both the groups have roughly the same number of nodes.
I kept getting wrong answer on test case 7 for some reason I don't understand. Can anyone provide some insight to it please?
Your idea is very good, the only part that is missing is how exactly you are dividing the subtrees into two groups. In order to do that, you have to use a kind of knapsack-DP in order to calculate all sizes of the two groups
Can you please elaborate a bit, my idea was also similar but I didn't know how to approach further with it.
Can you please tell me what are the dp states?
For a certain node: dp[i] = true iff there exists a subset of the subtrees of the node that have together exactly i nodes. For each subtree with k nodes, you update the dp-array by setting dp[j] to true iff dp[j-k] is true. For a node which has m subtrees with n nodes together, this runs in O(nm).
Can we do it for E2
That method does not work for E2. Consider the case of the root having the other 10e6-1 nodes as children: Then, the dp-array has the size of 10e6-1 and we iterate through it 10e6-1 times. It is possible to improve that by small constant factors, but for E2 you have to make bigger changes
It is interesting, that transition from E1 to E2 looks like a super standard problem that everyone should know how to solve, yet so much struggle to do so. (Note, personally idk how to solve E2).
Just wanna know how many people got WA on problem D because of making query with l = r LOL.
WA on 6th pretest in C anyone?
Submission: 217341446
long
Thank you for your invaluable feedback, but I did use long long for my calculations in C (also the answer can't exceed a 32-bit integer)
Improve your binary search correctness. You need a standard.
I did not use binary search, I tried to do a greedy $$$O(n^2)$$$ solution, you can observe that the maximum value can be obtained if you build a pyramid that is tilted to the left.
Your situation is same as mine. During contest, I also got WA 217328079 on 6th pretest in C. Our approaches are similar. Both the outer loop and inner loop are counting backwards.
Once I changed the inner loop to count forward, I can get AC. See my 217375396. Not sure why yet.
I have just found the mistake in my implementation — I wasn't updating the height of the first element in the sequence after lifting the entire sequence, the correct submission: 217377033 (the only difference is that I have added the
currentvariable)Take a look at Ticket 17042 from CF Stress for a counter example.
Thanks so much!
Who decided E1 was a good problem on 5th position?
I mean, according to the problem points (1500 for E1, 2000 for D), it was expected that E1 would be easier than D.
just asking to confirm if it is just with me or happening with u also? Did the first question took more than 5 minutes to load for u all?
No. You might want to try mirrors of codeforces like m1.codeforces.com, as they work much faster
Most balanced contest ever!
Cool problems, thanks. :)
wasted 30 minutes on C because I did not read the constraints carefully
Had high hopes from this contest, but got stuck at A:(
Please help me what went with my logic/code ; It keeps failing on pre-test 2. I am not able to find a test case, where this fails. If you could provide me with one, I can word out the error myself. Thanks!
What's your logic?
I will give you a test case where your solution fails but keep in mind that you should in general go for the simplest solution. Try to solve the problem again and find the simplest way to solve if you want to improve.
1
4
7 4 10 10
your codes answer: 10 correct answer: 7 after 7 operations the array becomes 0 0 3 3
0mar thanks for your help man! The max_element() points to the first such value if multiple max values are there. Would surely go for simple logic only. Thank you.
Hints for B?
Rough Idea: Just watch out for number of 1s in a. If there are none, then a_i := a_i — 1 for all i in {1,2,...,n-1} and a_n := a_n + n-1 Otherwise, let y be number of 1s and x is sum of non-one numbers... increase each of these y 1s to 2 and so, if x — y >= y, then YES else NO. [This works because you can reduce these non-one numbers to cover up the y increment and if something is still unchanged, reduce it by 1 [not equal to zero as this value is at least 2] and increase one of the 1s (original) by another 1]
Distribute money from rich to poor
How is that?
Take the money from the richest guy and make the change in the lives of the poorest guys.
[Richest] [Mediocre] [Mediocre] [Poor] [Poor] [Poor] [Poor] [Poor]
The richest guy wants to affect the lives of as much people as possible. The richest guy knows that Mediocre guy will not appreciate 1 cent donation as much as the poor guys would. That's why the richest guy always targets the poorest to make the most impact on the population.
please help in C
use binary search on each index.
Binary search on the answer + bruteforcing every position where the maximum value will be
C was a good problem E1 also. I solved it with DFS+SUBSET SUM Dp
Is it possible to solve C without binary search? My idea is to check each subarray and find the maximum value achievable, but was not able to implement it in $$$O(n ^ 2)$$$.
I'm waiting for the sys testing to be over, so I can see what I did wrong in my $$$O(n^2)$$$ approach (intuitively I think it's totally possible)
Yes its possible, you need to maintain the maximum allowed value of ai for subarray [i,j] based on values in [i,j] and j+1. Rest is just sum of AP and prefix sums
Solution : https://mirror.codeforces.com/contest/1856/submission/217318594
well，E1 is easier than D and it can easily AC,but E2's score is lower than D,it makes A+B+C+D+E1 > A+B+C+E1+E2 . you know , AC E2 is more and more and more harder than AC D.
Is it good?
Could anyone tell me why my E1 code returns the wrong answer on test #13?
my E2 solution without bitsets fits in half of TL, can anyone hack? 217346719
My solution without bitsets works in 452 ms, while with bitset — in 421 ms. Without pragmas and bitsets — in 900 ms.
A question to anybody who solved C: this problem is about BS on the answer. How do you understand a problem requires being approached in this way? Is there a particular signature or something which makes you think in this direction? Is it the constraints? The fact that the operation was mentioned to be performed no more than k times? Does it ut just comes with experience and/or by solving similar problems(if yes please suggest some)? Any good insight is appreciated.
If problem is such that answer at some point is possible then it must be possible for all either less or greater values then we can try to think of binary search. A better and formal name for this behaviour is montonic function. A monotonic function is a function which is either entirely nonincreasing or nondecreasing
in this case the function is like if we can get a value x then for sure we can get another value <= x?
Yes, so that's why we only then need to search for values > x
ok. Which is if I found that for some x is possible. I know the best ans so far is x and I look in the interval [x+1, hi]. Makes sense. So once this is clear the problem becomes how to check if it is possible to get some value. Right?
YES
when the problem is about minimum or maximum, it is pretty common to use binary search.
Yup also dp and greedy can be option too
It's a feeling, a hunch. At first you digest the problem and then you start bruteforcing different techniques in you head.
This is basically what's going on inside of my head
can someone tell me why i got FST on E1? 217343471
my approach: I calculated the subtree size for each node. then for every node, stored the subtree sizes of its child nodes in an array. then did a dp to partition the array in 2 sets such that the difference of their sum is minimized. and then added their product with answer.
upd: got ac after making the graph directed :')
Does 11k+ submission of B justified ??
What do you mean?
I think it was pretty good idea and I don't think that much number of submission is justified
I am gonna get downvoted, but I also find it suspicious that everybody was able to find the idea. I have seen way easier Bs with less subs.
You can't just say that "I have seen way easier Bs with less subs.". You aren't measuring objective difficulty here. You're measuring how you felt about the problems. You have seen Div2B's whych were easier for you but harder for most people. This time the problem was easier for most people (many probably guessed the amswer), but harder for you.
This is actually a thing that happens to everyone. I remember two recent contests and their Div2E's (both were 2400 rated problems): I was able to solve one in about 15 minutes, while I couldn't get the other one even after 90 minutes.
After getting FST on problem D, I dropped from rank 3 to rank ~200. I am not surprised because in each recursion I ask three queries (r-l)*(r-l). If my code did not pass the pretests, I would come up with the solution.
And I think the score division in problem E is not suitable.
Sorry for my bad English!
Could anyone help me out with C Submission
Take a look at Ticket 17030 from CF Stress for a counter example.
Thanks figured it out, i had to update the whole array
j
I hope rating changes will update before i get to sleep.
IKR
My FSTed solution for E2 involves heuristics to solve the simplified problem "partitioning the given set of positive integers $$${a_1,a_2,\cdots,a_k}$$$ into two, so that the difference between the smaller sum and $$$\frac{\sum a_i}{2}$$$ is minimized." Specifically:
I am curious about how to construct strong tests for such heuristics. Any ideas on constructing them?
If you have subtree of size $$$1$$$, gcd always be $$$1$$$, so you claim that you can always make exactly $$$\frac{\sum{a_i}}{2}$$$. Just make any test with large $$$k$$$, where it can't be achieved.
Actually, my intention is to ask for the ideas behind the construction, not just the test makes my solution fail.
But I have also come up with one idea: For example, if the set of numbers are $$$1,3$$$ and $$$g$$$ repeated $$$2k'$$$ times ($$$g$$$ and $$$k'$$$ are ome sufficiently large integers), then the $$$\gcd$$$ of them is $$$1$$$, but it is impossible to select a subset with sum $$$\frac{\sum a_i}{2}$$$.
I have never realized that the construction can be that easy :(, thanks for your reply.
Really that many people found B2 solution that easily???!! I guess I need to improve my intuition.
Well it's kinda constructive problem, you should approach them a little bit differently from others
I'd like to report probably a system issue.Vladithur MikeMirzayanov. During the contest i submitted my solution to e2 and it got rte on test 17. I had 20 minutes to debug it but i didn't manage to do it in time. Surprisingly after contest it appeared that the reason for rte was probably stack overflow because of dfs recursion. (i changed in ac submission after contest only recursion to iteration and it easily got ac). Therefore here are 2 questions:
Here is my 1st submission to e2 which got rte: https://mirror.codeforces.com/contest/1856/submission/217343160 Here is my submission to e2 after contest which got ac https://mirror.codeforces.com/contest/1856/submission/217365641
According to this blog about compiler options, stack for C++ is limited to 256 mb.
I see. However that blog was 13 years ago so there could be some updates. Moreover, my complaint is also that the verdict imo should be mle not rte in this case.
Command lines have not undergone significant changes. For example, for gcc11-64-winlibs-g++20, the command line looks like this:
g++.exe -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++20 -o %name%.exe *.cpp.I think the verdict of RE is more appropriate. The process in the operating system terminated with an error, and that's what RE is. It's a different situation from trying to allocate more memory and reaching the ML.
Why not set stack size to be equal to max memory limit for any problem?
Video Editorial for problems A,B,C,D and E1;
https://youtu.be/jxLu6DMDV7o
Hope to become cyan!
congrat you're cyan
Is this ratings without cheaters or what? MikeMirzayanov
Let's go I'm master now!
congrats
Best Div2 A is easy to read and B is easy to read too
I really want to say that bitset is a way to optimize your code, and it really can be used in races for answers.
https://mirror.codeforces.com/contest/1856/submission/217389353 can anyone tell me why i am wrong in this submission ? thank you !
Take a look at Ticket 17029 from CF Stress for a counter example.
Thank you so much !!! Hope you get the best luck in your life :3
One of the tag in problem C is Dp. has anyone solved problem C using DP ? if yes then please share the approach of DP.
I enjoyed this game, its concise problem description made me feel comfortable.
Thanks for the round, pE2 was really interesting!
https://mirror.codeforces.com/contest/1856/submission/217324302
10
8 1 11 1 2 1 1 1 1 1
total sum of this array is28
so we can make another array like this
2 2 2 2 10 2 2 2 2 2
so why this case ans is no?
Your Answer is wrong for Test 2.. 3rd one.. which is
Thanks for contest!A little late,but contest was great!
https://mirror.codeforces.com/contest/1856/submission/217873662 Could someone tell me what I am doing wrong?