Hello, Codeforces!
amurto and I are glad to invite everyone to participate in Codeforces Round 838 (Div. 2), which will be held on 15.12.2022 17:35 (Московское время).
This Round will be rated for participants with rating strictly lower than 2100. Participants from the first division are also welcomed to take part in the competition but it will be unrated for them.
You will be given 7 problems and 2 hours and 30 minutes to solve them. One of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!
We would like to thank:
- errorgorn for amazing coordination and help with the problem preparation.
- KAN for translation of the statements into Russian
- TheScrasse for providing suggestions which helped us to improve one problem.
- GoatTamer for discussing problems with us while our proposal was in review and testing the round.
- dorijanlendvaj, Um_nik, tabr, jeroenodb, Kira_1234, rivalq, thenymphsofdelphi, MagentaCobra, prvocislo, towrist, maomao90, IceKnight1093, AGRU, Omja, valeriu, TheScrasse, Perpetually_Purple, priyanshu_bhardwaj, Nahian9696, koderkushy, Non-origination, brobat, jampm, nyaruhodo, the_hyp0cr1t3, iLLusio, Utkarsh.25dec, ak2006, AlperenT, physics0523, udhavvarma03, welleyth, meme, SlavicG, MasterRayuga, recurecurring, dedsec_29, blitztage, Mo2men and tibinyte for testing this round and providing feedback.
- MikeMirzayanov for great Codeforces and Polygon platforms.
Score distribution is 500 — 1000 — 1750 — 2000 — 2500 — 2750 — 3500.
UPD1: Congratulations to the winners!
Overall:
Rated:
UPD2: Editorial is out.
We are looking forward to your participation!
Really awesome problems that I enjoyed testing very much. Highly recommended to participate (and up-solve :P)
As a tester, this is truly one of the rounds of all time.
This is the first time I've tested a round and it was a great experience, getting to know the "producer" side of Codeforces. The problems were all amazing, and I hope you guys enjoy the contest! And may you achieve $$$\Delta \geq 0$$$ :)
brobat orz
.
orz
orz
brobat orz
A, B, and C are truly amazing. D got fewer solves :-( in this round.
Can you explain your approach for B
sort the array; start making each element a multiple of previous;
Yes, I did the same
Just try to make all numbers (let num be 'x') equal to nearest power of 2 which is greater than or equal to 'x'. And with little observation you will be able to conclude that the nearest power of 2 (let it be 'y') such that it is greater than or equal to 'x' will always be lesser than 'x' i.e. y — x <= x. This way you don't need to sort the array or use any vector.
That's nice, btw one can immediately see the fact if you represent $$$x$$$ in binary. If $$$i^{th}$$$ bit is the msb, then, then after adding $$$2^{i}$$$ (note that $$$2^{i} \le x $$$) the number becomes $$$ \ge 2^{i+1}$$$. So, after adding some stuff which is $$$\le x$$$ we get a number that's higher than the next power of two. So, its proved!
Yes exactly btw what was your approach for this question?
make every element equal to power of 2
As a tester master, I am the master tester. First round I tested, orz problems!!
As a tester newbie, I am the newbie tester. Second stack round I tested, orz problems!!
Cool problems, I recommend taking part.
As a tester, Good luck to everyone who will participate
As a tester, I can assure you all will have fun in solving problems.
As a tester, I have enjoyed testing this problem set and all of the problems are really high quality
As a tester, I hope you'll enjoy the problems as much as I did! Yet another well-coordinated round by errorgorn :)
Please participate
amurto orz
Only if you promise me positive elixir trade.
As a tester, I highly recommend reading all the problems.
blog of #838 posted and there's no editorial for #837
As a tester, I didn't really tested the problems
As a tester, the round is awesome!
I see more comments from testers than from others, so I am also adding mine to increase the count XD.
PS: Problems are really good and one can look at stack's previous round to see his problem quality.
As a discusser of problems while proposal was in review and a tester, please let me participate
As a tester, so huge number of the testers...
As a tester, I really enjoyed testing this round. I solved some of the most enjoyable problems yet!
As a participant, I haven't tested the round yet. Really awesome problems that I enjoyed. I recommend this round for everyone.
As a participant its scary to have so many testers, I hope everyone may achieve Δ ≥ 0 :)
That means everyone gets 0.. :)
As a non-tester I can assure the problems are of high quality.
Source:- Trust me bro.
Trusting you bro
As a tester and an ex-tester, my assertion still holds true.
I think it will be interesting to solve this contest
it will be nearly impossible to solve contest by us(whole questions),but yeah we can try to solve 3-4 questions.
As a tester, it’s a(Good) round ^_’
hope to gain more rating which i have lost in previous two contest.
As a nothing, this is truly one of the best contests.
why rating of previous contest is not updated yet??
I have never seen this many testers in any div2 contest.
Will the rating of educational #139 be updated before #838 starts? If not, rating of educational #139 will be updated based on the rating after #838…
Stack and Amurto Round. 🛐
Very excited for this contest.
CM today
Lost 100rating 🤡
When ratings will change?
When ratings will change?
After a long time. Best of luck Everyone.
RETURN MY RATTTTIIIINNGGGGG
When will the Ratings change for this round?
Will the Ratings change for this round?
2 recent contests, someone can do this
There is a list of allowed languages in the announcement Email:
I don't understand why do you limit the programming languages contestants can use? E.g. why can't I use Rust?
I support you. I myself practice a bit in rust, and there's no reason to exclude it in my humble opinion
Is Perpetually_Purple suffering from success because now he is not "Perpetually_Purple"?
Sorry for the lame joke
Perpetually_Purple is purple in name, yellow in rating and red in skill.
blue in balls..
Argentina vs France suiii
oh no , 1750 points for problem c
Hi, I'm new to programming so was wondering, when the contest means it will start at 8:35 AM, does that mean we have to start coding at 8:35? Or can we start anytime after that?
This game is from 8; 35 to 10:35,You can compete at any time during the two hours of the competition, but I suggest you enter at the beginning of the competition, otherwise your competition ranking may be lowered a lot.
All the best everyone
Good luck to everyone!
I think the interactive problem is C
Hey, Can anyone help me? I am a starter in cp, which div is suitable for me?
The higher the Div number, the easier, so Div 4 is the most suitable for a newbie. However, this doesn't mean you should only do Div 4 contests. I encourage you to try ALL contests, but just keep your expectations realistic.
If you're at a point where you cannot solve even the first problem in Div2 during the contest, try to aim to solve at least the first problem. If you're at a point where you can only solve one problem in Div2 during the contest, then try to aim to solve two problems, or at least try to solve the first problem a little faster and/or with fewer failed attempts. And so on.
As long as you keep your expectations in check, you should be able to benefit from every contest, as long as you utilize them effectively as a learning experience instead of only trying to hope for a miraculously high ranking.
But if you have time management concerns, e.g., you can only afford to put aside time for one contest in the next few days due to being busy with other work, then you should probably just stick with the easier contests for now, i.e. join the Div3 in a few days instead.
Div2,3,4 is suitable for you. Participate on those divisions contest regularly.
Hope to get to cyan :(.
Me too :(:
Can't believe it! I'm expert now!
Interactive problems, the worst thing that happened to Codeforces.
You can't just say it's bad because you are not strong enough to solve it :D.
It's better to take a break from prime-factorisation problems this time
Good DP in Problem C
As I said good DP, in Problem C
You are not supposed to reveal any information during the contest.
I didn't write this during the contest, it was before;)
Yeah binary strings are so fun that I cant stop enjoying them
It was cursed for me :(
difficult round (•_•)
hoping for a color change to cyan :-) Let's see
Div.1 + Div.2... Not enjoyed this one tbh...
Is there randomized solution of D or something else?
I try to use the conclusion that 0 is the only number that leads to distinct gcds when gcding with other numbers, but failed.
You can take three pointers i,j,k (initially 1,2,3) and ask query for i,j and j,k and say u get the input as x and y respectively. If x>y, you can increment k to max(i,j,k)+1, else, if x<y then i = max(i,j,k)+1 else j = max(i,j,k)+1. So in every two queries, you are discarding one element of the array for which you are sure that it isn't equal to 0 and you have to dicard n-2 elements in total, so this will take a total of 2(n-2) queries.
Ok, thanks
Cannot come up with D and I'm about to get negative delta
any idea?
query for(1,j) where 2<=j<=n and if(p1==0 || p1>=(n+1)/2) we can solve
let query(i,j)=gcd(pi,pj)
else we know p1=max(query(1,j)), if p1>1, we can deal with {j|query(1,j)==p1}
but if p1==1 what can we do next
You can see here.
Oh I see thanks
I only thought about "how to find a number >=(n+1)/2 in n queries"
However the answer is "how to find a number !=0 in 2 queries"
also I think interactive problem should appear at least E...
D is a little bit early
i don't know why my D is wrong i am so frustated :( debugged for almost an hour but could not find mistake!!
Similar. I have theoretical proof for time limit and correctness of my algorithm which means i made some stupid mistake in code and just could not debug it ;-;
That's because the first number you picked can be 1 in which case the list of potential indices will reduce only by 1 instead of being divided by some number >=2.
DEFG are too hard. :(
Hint for Problem D?
The best I could come up with is the observation that 0 will never give the same GCD against two different values (a property that only 0 has), but I couldn't figure out how to hunt 0 down from there...
you take 3 indices a, b, c:
if gcd(a, b) == gcd(a, c), it means that a is not 0, thus you remove a.
if gcd(a, b) > gcd(a, c), it means that c is a "divisor" of a, thus you remove c.
if gcd(a, b) < gcd(a, c), it means that b is a "divisor" of a, thus you remove b.
you make 2 queries for removing 1 element, total number of queries equals (n — 2) * 2
Thanks bro
nice solution !! it seems so simple and you explained in 3 lines!
let a=24, b=18 and c=20 then gcd(a,b)>gcd(a,c) but c is not a "divisor" of a. I guess the actual reason is since gcd(a,c)<gcd(a,b), it implies gcd(a,c)< a hence c is not 0 and can be removed.
you're right, I didn't know what to call it. I came with that Idea from the fact that if b is 0, the gcd will always be greater. So the real reason would be if gcd(a, b) > gcd(a, c), it means that c is not 0.
one obsrvation is that for A[i] > (n/2) -->it give gcd = A[i] for two places himself and with 0 two indicies for this can be found in O(n) iteartion
This only if choosen is >(n/2)
whenever, there are too many testers saying the round is one the most interesting rounds. Don't take them seriously.
:)
Am I really not seeing something, or is C really addition of nC0 + nC1 + ... + nCk, where k is the amount of '0' or '1' depending on the last digit? If that's the case, how can I calculate it in O(n) or O(n log n)?
It's sum of 2^(number of continuous digits in suffix) for every i
I did it using dp. if s[i] == s[i-1] , dp[i] = dp[i-1]*2 else dp[i] = 1.
I also did DP but with memoization
why dp[i]=1,it should be dp[i]=(all possible current arregments)-(dp[i-1]*2)
No, it's a lot simpler.
Let's say you have a prefix of $$$k$$$ 1s. Then every extension is valid, i.e., there are $$$2^{k - 1}$$$ possibilities. You can watch for the chain and double the number of possibilities at each step. A prefix of $$$k$$$ 0s is symmetric.
But now, let's say at some point the string changes, e.g., from 1 to 0. Up to the 1, the majority must be 1, so in order for the majority to change to 0, the next value must be 0, and there is only one possibility. This resets the chain. If we follow it up with another 0, we are now back to having the freedom of 0 or 1 in between, so the chain (which we just reset) now grows in the same way as before.
tl;dr — separate the string into blocks of 0s and 1s. For each block of length $$$k$$$, add $$$2^{k - 1}$$$ to the answer.
My submission: 185325238
facepalm I read the question wrong and thought that a good substring only need the final median to be good... Then I started to look at Pascal triangle and all those stuff...
Feels good that I am not the only one who did it. :(
I just made the same mistake and misread the problem statement and tunnel visioned... I was also wondering how to solve for nCk sums fast. I guess I should learn to read problem statements more carefully
I also stuck here :)
It's too hard. Div.1 + Div.2?
The problems are good, but my condition is not good. I have used more than 1 hour thinking about strange algorithms, which lead to insufficient time to finish F.
How do you solve D? My idea ( that almost solves it) is to keep track of candidates. Take a random number and check gcd with all the caniddates. The new candidates will be the caniddates with highest gcd because they are the multiples of the inital number (and dont add the inital number to the new candidates), and since zero is a multiple, it will be among the candidates. The number of candidates at worst case decreases by half so the number of queries is n * (1/2 +1/4 +1/8 ...) < 2*n. The only problem is when we happen to start with one. Then we get another n queries and we make 3*n queries.
I found one approach which keeps a track of exactly 3 candidates each time and asks 2 queries to eliminate one; you can use this as a hint or check here.
Smart approach, thanks.
I did this solution and solved the problem with
1by first picking two indexes and checking them with every one else (in random order) "in parallel" (i.e.gcd(x, 0), gcd(y, 0), gcd(x, 1), gcd(y, 1), gcd(x, 2), gcd(x, 2)). The moment I get the first non-1 I know that this was not "1" and continue as you described.By randomizing index order the expected number to get the first non-1 seems to be "quickly enough", though I'm not sure what are the actual odds (i.e. if we happen to randomly pick
x = 1,y = 2and then the ordering happens to try to check it with 2, 4, 8, 10, ... first it can probably break). But it just passed final tests, so I guess it's fine.DDDDDDDDDDDDDDDDDD!!!!!!!!!!!!!!!!!!!read 1 or -1???!!!!!!!what!?
The judges were very kind
+1
Here's my solution for D
Maintain a list of potential index that could be 0, let's call it v, query v[0] against v[1], v[2], ..., v[v.size() — 1], we can see that if query(v[i]) = max(query(v[1...v.size() — 1])), v[i] can either be 0 or multiple of v[i], remove all v[i] != max(query(v[1...v.size() — 1])), repeat
If there is exactly 1 query(v[i]) = max(query(v[0...v.size() — 1])), let's call that v[i] is vmax, then either v[0] or vmax is 0
Run this until size of v is <= 2, we have our answer! Also, if gcd(v[0], v[1]) = gcd(v[0], v[2]) = 1, v[0] couldn't be 0, so remove it
what do you do when v[1] is 1? wont you make n queries without narrowing down the potential indices? couldnt figure out what to do when the first element is 1 :(
you can remove 1 from the first 2 queries
You don't really remove the 1 this way. But it works nevertheless
Why swishy123's exact solution is failing on test case 26. May be some new test cases are added.
wait, so i just got EXTREMELY lucky lol, i think the new test cases is the test people managed to hack others with
I don't get why your idea doesn't work. You keep discarding one element with two queries until you find an element that is not one. Say you have discarded m elements. The total number of queries your code will make is 2*m + 2*(n-m) = 2*n
I fixed my code with your idea (I didn't know how to get an element that is not 1 during the contest) and it gets AC. 185457951
I did it but got WA on pretest 5. Just could not debug the code the whole contest ;-;. Edit — Actually got query limit exceeded.
Same here, did you find out the difference between your solution and Swishy123 solution?
Yes https://mirror.codeforces.com/blog/entry/110056?#comment-980737
\worst case, queries = n + n/2 + n/4 + ...
A -> D is pretty easy :D but dunno why my F is RTE >:(.
fast coding forces be like
Why not prepare this contest as div.1+div.2? I think it is too difficult for div.2. Or maybe arc is anothor good choice, Uh?
Afterall, problems are nice.
Wasted a lot of time trying to solve D before even seeing C, but great round with interesting problems nonetheless.
I found D easier than C and solved it before problem C. Or at least it's more beautiful
this guy https://mirror.codeforces.com/profile/jiangly is amazing. Solving problems within 1 minute.
Cause he's world's best coder
A really great round with good problems !
Thanks a lot!
I hope all the upcoming December contests would be like this :)
What? A contest without successful hack? Maybe problems are too hard and no one has extra time for hacking?
Awesome num theory forces.
What was the idea for problem E? Was there a combinatorics formula or some constructive algorithm?
For a fixed tree the weights are also fixed. The proof is to just delete the leaves until the whole tree is deleted. In fact, $$$n$$$ has to be even. Otherwise, the tree is impossible and the answer is $$$0$$$.
Now we are interested to find $$$\sum d(u,v)$$$ over all ordered pairs $$$(u,v)$$$ ($$$u \neq v$$$) for a fixed tree. After rooting the tree you can get a general formula that depends on subtree size of each node and their parities. The formula is easily extended to hold for all trees of size $$$n$$$. (Of course, the final answer has to be divided by $$$n(n-1)$$$ )
What do you mean by a fixed tree?
The tree (a set of currently unweighted edged) is given in the input and the task is to assign weights so it's good. I claim that at most one valid assignment exists.
The key idea of problem D is to delete non-zero but not to find zero. After I saw the accepted code I got the idea immediately but it is difficult to change the direction while the round is running. I tried to delete 1 all the time on the round and thought about many ways including random, but it seemed impossible to make the probability small enough to pass the problem. Has anyone passed this problem with a random method?
This method works with very high probability :
Notice that if you query(x, y) for all y with a fixed x, either p(x) = 0 or p(x) = maximum answer to a query. If you let k be the maximum answer to a query, you can notice that you only need to look at multiples of k, and multiples of k are exactly the elements that answered k to the query. Thus, you divided the number of elements by k doing that. This is almost enough to solve the problem, except if the first element you pick is one, and you're gonna use almost 2n queries before dividing for the first time. To avoid that, you can just ask random pairs until you find an element > 2 and start dividing with this element.
Interesting, this is way easier, but I thought using randomness in the beginning wouldn't work, especially with small permutations, so once I realized the problem of picking 1 as your first number I followed the approach of comparing the first and second elements with each of the next elements until I got a gcd different than 1, since both can't be 1. Then you apply the normal strategy with the remaining elements and since you eliminated one number for every two operations I'm pretty sure this should work, although I haven't been able to get AC yet.
How do you check if, in any iteration,p(x)=0?
if p(x) = 0 then the maximum gcd is the maximum element left so only two elements are leftover and you are finished.
I was saying if my x is such, that p(x) = 0, and elements left in the array are [0,2,4,10] then my answer for queries will be [x,2,4,10=k], from this how to determine whether p(x) is 0 or not?
I tried this approach (just participated virtually now), and it does not work, instead of choosing a random pair I choose a random Y from all multiples of a X, but pretest-5 is evil. :(
I thought about the same method as you described. But in my caculation, valid pairs(gives gcd(a_i,a_j) > 1) only takes about 2/5 in all pairs(C(n,2)) which means we need to do about 20+ times queries to find such a pair with a not-found porbability around 1e-9 and then we need to do at most 2n(n + n/2 + n/4 + ...) times queries in worse case to find the answer. So on the round I thought it is difficult to pass the problem especially for small n like 7 or 8. I cannot give a solid proof of this method but it is true that the real process has a very low probability to enter the worst case(we pick k as 2,4,8,...).
I spent about ten minutes to figure out that you should read a 1/-1 after each testcase in problem D.
I bet there's people who spent more TAT.
I spent 20 mins on that
$$$D$$$ looks like author typed something randomly, then suddenly noticed, that this produces "something meaningful", and created problem, which asks to get strictly that "something meaningul".
Well, just to make it clear initial version was to find the whole permutation using atmost $$$3n$$$ queries, which is quite natural and cool imo.
Testers found it hard and some unintended solution which uses around than $$$3n+\alpha$$$ (where $$$\alpha$$$ varies from $$$30$$$ to $$$40$$$ depending on implementation) were getting cheesed. That is why we decided to have current version. Most of the testers liked it. So we went with current version.
My solution to D 185365086 (idea is to take any number and querying it with other valid elements to try to get a higher GCD) shouldn't work but I was able to make it AC through randomization and just running an infinite loop when I am about to exceed total queries so that the system rejudges my submission.
Can anyone try to hack this?
(Edit: Cleaner version 185377734)
Very Clever Solution orz
Errorgorn had warned us about this loophole. That is why we had high number of test cases initially.
Interaction was taking a lot of time, so we had to reduce the number of test cases.
Good job btw (:
Wait why the infinite loop does not giving TLE, it's cool hack can you explain lill more about running this infinite loop and system rejudge thing.
what's the idea behind B
an easier provable idea: make each element a power of two. The power of two is always found between n and 2n. And it is obvious that if all the numbers are powers of two, then in each pair someone divides the other
Mathforces!
$$$D$$$ was great. Maintain two possibilies, $$$poss[0]$$$ and $$$poss[1]$$$ as the "possible" indexes where $$$0$$$ can be present. Initially $$$poss[0] = 1$$$, $$$poss[1] = 2$$$. Let $$$ g = gcd(p[poss[0]],p[poss[1]]) $$$. (Use the first query to determine $$$g$$$ initially.
Then, start with index $$$3$$$. (And now we need to update $$$poss[0]$$$ and $$$poss[1]$$$).
Calculate $$$gcd(p[poss[0]],p[3])$$$ and $$$gcd(p[poss[1]],p[3])$$$ and $$$gcd(p[poss[0]],p[poss[1]])$$$ (You have already stored it).
Sort them, lets say sorted values are $$$x$$$ $$$y$$$ and $$$z$$$ where $$$x \le y \le z $$$. It can be shown that if $$$gcd(y,z) = x$$$ and $$$x!=z$$$ and $$$y!=z$$$ then, index $$$p$$$ and $$$q$$$ will be the possible candidates for $$$0$$$ where $$$ p $$$ and $$$ q $$$ are the index among ($$$poss[0], poss[1], p[3])$$$ and no index ($$$p$$$ or $$$q$$$) is common in index corresponding to $$$x$$$ and $$$y$$$. (Index corresponding to, say $$$x$$$ means that the two indexes whose gcd is $$$x$$$.). So update $$$poss[0] = p$$$ and $$$poss[1] = q$$$ if the above conditions are satisfied, otherwise don't update it. Then repeat the process for the next index.
At the end, $$$poss[0]$$$ and $$$poss[1]$$$ are the answers. Link for my submission: https://mirror.codeforces.com/contest/1762/submission/185373278 (Solved it just after contest :( )
I don't understand outputs of interactive problem debuging enviroment
https://mirror.codeforces.com/contest/1762/submission/185375790
I manualy checked test1 and test2 and both work hmmm?
D has a strong vibe of this problem: https://mirror.codeforces.com/contest/1634/problem/D
Not only it asks to find zero, but solutions are very similar too
Why gcd(x,0)=x,is it a definition?
gcd(x,0) = x
sorry，I write it wrong
Because any number is divisor of zero.
I am so sad，my rating will drop，because I have never solved interactive problem，so I always got idleness limite exceed in D，but it is a interesting round.
for problem B sort the array and make the i+1th index multiples of previous .
why is it failing anybody
After sorted the indexes are rearranged but you should output the original index
To fix it you should use pair<int,int> {a[i],i} to store the original index, or let b[i]=a[i]*N+i where N>max(n), then sort b, we can get original index=b[i]%N.
On E, I got the AC formula
but couldn't prove it; can anyone provide some reasoning as to why this works?
How did you figure out the formula during the contest?
I got the observation that, if we root the tree at 1, the label of the edge of each node to its ancestor is $$$(-1)^{\text{subtree size}}$$$. Then, I attempted counting based on $$$n$$$'s subtree, but couldn't really manage the path from 1 to $$$n$$$. Trying to sum over all nodes was a tough task too. I just resorted to guessing after a while, and surprisingly a simple tweak to Cayley's Formula works.
Pick any edge in the path $$$1 \rightarrow n$$$. It divides the tree in two subtrees (let's say that the left subtree contains $$$1$$$, and the right subtree contains $$$n$$$). Then, you can iterate over the size $$$m$$$ of the left subtree.
I think you also have to choose the endpoints of the edge. You can do this in $$$m(n-m)$$$ ways and that's why the exponents of $$$m$$$ and $$$n-m$$$ are $$$m-1$$$ and $$$n-m-1$$$ instead of $$$m-2$$$ and $$$n-m-2$$$.
oops, I forgot :D
Problem B Video Solution And Code (Hinglish)
Missed being candidate master just for 10 points :'( Thanks for problem D, exactly my favourite type of problem.
Upd: Reached candidate master the next contest!
Try getting +210 today and becoming master
4 th test case in c f([1,3])=1 how, extension of 010 can be 00100,01100,00110 hence f([1,3]) should be equal to 3.
It must satisfy the constraints for all of the previous prefixes too. For example, $$$00100$$$ is not considered an extension as for $$$s_2 = 1$$$, the prefix is $$$b[1, 3] = 001$$$. We can we that the median of this prefix is $$$0$$$, and not $$$1$$$ as it should be.
oops! i missed the first line
:)
Ratings updated preliminary, it will be recalculated after removing the cheaters.
Am I the only one who understood the problem C incorrectly? At first, I thought each prefix is an independent case and later I thought even after surpassing a prefix the elements constructed could be changed with new incoming characters.
Can anyone tell me why am I getting Wrong Answer on testcase 2 for my code of problem A:
include<bits/stdc++.h>
using namespace std;
int main() { int t; cin>>t; while(t--) { long long n,i; cin>>n; long long a[n]; for( i=0;i<n;++i) { cin>>a[i]; } long long EvenCount = 0, OddCount = 0, evenmin=9999999,oddmin=9999999,count=0,sum=0,k; long long Even[n], Odd[n];
for(i = 0; i < n; i ++) {if(a[i] % 2 == 0) { Even[EvenCount++] = a[i];
}
The value of a number is smaller dose not mean it takes less operations to change it parity, like 8(need 3 operations,8->4->2->1) and 10(need only 1 operation,10->5)
as not a tester, round was great!
MikeMirzayanov i had received a mail regarding plag. Both are my accounts, i gave the contest with both of my id's simultaneously.
And those 2 upvotes are from your other ids.
ez div2!
Hi, the Editorial to Problem C is wrong.
For eg: consider -> 110111 according to Editorial for f([1,6]) = 2^2 , which is wrong.
There are 2^3 possible ways for f([1,6]).
Proof: 1 _ 1 _ 0 _ 1 _ 1 _ 1 Possible values: 2 1 1 2 2 => 2*1*1*2*2 = 2^3
The answer should not be 2^(max continous len — 1).
Rather, it should be like this
For every consecutive same elements, we can fill gaps with 2 options (0,1), and if there are different elements then we can only fill with only 1 option.