Hi, Codeforces!
I'm glad to invite you to take part in Codeforces Round 720 (Div. 2), which will take place on May/07/2021 17:35 (Moscow time). The round will be rated for the participants with a rating lower than 2100. Participants from the first division are also welcomed to take part out of competition.
You will be given 2 hours 15 minutes to solve 5 problems. All the problems were created and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.
Huge thanks to those who helped make this round possible:
- Fliahin for being the first who gave feedback and helped with ideas on some problems.
- Denisov for providing priceless feedback during the entire creation of the round.
- KAN and Aleks5d for their excellent coordination.
- Valera_Grinenko, kalki411, PurpleCrayon, BOGDAN_, okwedook, namanbansal013, 16204, ermakov22, Denisov, 4qqqq, alexX512, IaMaNanBord, perekopskiy, kassutta and never_giveup for testing and providing invaluable feedback.
- MikeMirzayanov for Codeforces and Polygon platforms.
I tried my best to create interesting problems and clear statements, so don't forget to read all ones :)
Scoring: $$$500-1000-1750-2250-2750$$$.
Hope you enjoy it!
UPD: Editorial is published!
UPD: Congratulations to the winners!
Div. 1:
Div. 2:
hope the problems are as interesting as your rating graph
Interesting!!
Makes sense actually )))
karavaiev Why are Interaction Problems actually useful when we can do it normally(In the sense standard way of I/O) as well.
for example: https://mirror.codeforces.com/contest/1504/problem/D
So interesting（）
PurpleCrayon orz !
As a loyal PurpleCrayon Fan, PurpleCrayon orz.
as also a loyal purplecrayon enthusiast, PurpleCrayon orz!
PurpleCrayon is an inspiration to me. PurpleCrayon orz!
how PurpleCrayon so geniosity orz
as a loyal purplecrayon enjoyer, Purple Crayon orz!
Interesting scoring distribution, hope its_Atrap like CodeCraft-21 and Codeforces Round 711 (Div. 2)
Is it a trap? You can check soon :)
Yes I will check it during contest since I am neither a setter nor a tester :(
It wasn't a trap, rather questions were very interesting!!!
Hope problem C will be interactive! :)
Are you a time traveller?
Another chance for me to become Specialist... or Newbie
Hope you handle it well!
I know you can do it for Specialist, my friend...
Nice try
crap that didn't go well
I think the problems will be cool!
excited to participate in this contest ... seems to be amazing :)
My First Rated Contest :D, I hope I can make Tanya proud :)
She will be proud of you (for getting so much down vote) xD. Just a joke.
I very well know, these people who are downvoting me are tanya's brothers & relatives trying to seperate us T-T, #cruel_World
I know Tanya, You are laughing at this :D
I being Tanya's father reject this relationship.
ahm...ahm... Say it Again (if you wanna get thrown out the house) :/
Problem C 1750 Points ! a bit scary.
which problem will be interactive? Any guesses?
I guess problem D :P . Don't take it seriously. This is only my guess.
Resolved... Thanks!
Sorry but why down-votes? I was just seeking to get help and improve.
Maybe because it is under round announcement. About problem: i am not actually sure, but function "merge" can slow your code, i reccomend to delete it and write it's code directly in merges places.
I also reccomend to use 64bit version of C++, it is faster
upd: please note that i am not really good in this aspects of C++, so it is probably better not trust me D:
hope i can solve c
man hope is not everything in this curse world. You should practice as much as you can. Then only you can stand apart from the crowd :).
"..., Hope is a good thing, maybe the best of things, and no good thing ever dies."
The Shawshank Redemption
hope too)
PurpleCrayon orz
Guys, can you please press green triangle to raise this round's contribution
Not for you I guess
The problems seems very elegant after watching their score distribution, you should participate in the round.
Let's hope the server will not get down in this contest
Want Ashishgup div 2 rounds.
me too :) but cannot offer this one tomorrow :(
One thing i encounter in previous Codeforces round 719 problem F1 interactive problem for someone who attempted such type of problem for the first time. fflush(stdout) didn't work with FAST i/o .
submission link->https://mirror.codeforces.com/contest/1520/submission/115326611
you can remove Fast i/o fflush(stdout) that will work
submission link ->https://mirror.codeforces.com/contest/1520/submission/115344437
in same code i used cout.flush() it worked with Fast i/o.
submission link -> https://mirror.codeforces.com/contest/1520/submission/115336786
endl.
That C's rating makes it so sus for interactive problem!
Typical interactive problem:
Div.2 C — 70% probability
Binary Search — 95% probability
the same day as my birthday)) (tomorrow)
You can get a birthday color :)
Hoping to learn something new from the questions. All the best to everyone :)
Good Luck Everyone!!!
Hopefully problems will be interesting. Another chance for me to become pupil.
what are the difference between the divs? I'm not very familiar with this CP platform.
Div 1 is more difficult than Div 2.You can not participate in Div 1 if you have less rating than 1900.But you can participate div 2 and div 3 contest. And div 3 should be easier than the other divs. Hope you understand.
You can't join div.1 unless you have got 1900 Ratings. You are not Rated for div.2、div.1 when your Raing is higher than a number.
Last Global Round I passed out and my rating reduced. Hope my name turn blue again.
me struggling for cyan.
Hope you can be cyan soon. Moreover,I heard that the disease in India is quite serious now from media，Really？
Yes you heard it correct. But we all r trying our best to fight with it. And I truly believe that we will success in it. :)
Wish everybody safe and sound.
Karavaiev has a handsome avatar.
Thanks )))))
Is that actually you?
Yeap.)
Coming from a straight male, you got a beautiful upper face, to say the least.
2:15 for 5 problems looks so interesting and challenging :) good luck everyone!
2 hours were probably for A only.
The participants of the first division should participate after the contest (virtual participation) to prevent any slowness in queue or codeforces will go down
I completely disagree. There are too much bigger official participants comparing with participants from div1. Thus the last ones don't affect the competition too much, but their participations the most interesting, to be honest.
Registration:
Total: 17738
Contestants: 17502
Out of competition: 236
If those 236 persons didn't participate this will not make any change
its my first contest and i hope i can get top 10
good luck
5 problems in 2 hours 15 mins? Seem hard...
And it was...
Can someone tell me what the rating for each of the problems will be rather than score?
That is decided after contest seeing the number of people who solved it during the live contest. So u can't get that before the contest . :)
let us just acknowledge the fact that the testers' list was ordered taken their colors in mind!
gimme some negative contribs, I am hungry fellas
don't you dare give me some positive contribs. I just want to have negative contribs and live a happy life.
Looks like there is a long queue of submissions pending to be judged. Hope this contest wont be affected.
hoping to become grandmaster in this contest
constructiveforces
Good luck to everybody having fun with this kind of problems.
Nastia and Negative Rating
Nastia the little b*tch
problem C looks quite hard
There goes my green color
A. Nastia and a rating killing problemStupid dashboard,,,
MikeMirzayanov
I submitted a solution (WA on given sample test) and then due to some technical problems, not able to continue further.
So, will my rating will be affected or not. I will be considered as participant ?
You, are going down son
Nice experience ::) Going down by 200
I just wonder why an expert deliver this contest ... I really think the quality of problems is bad .
Just because you were not able to solve them early??
Bro Deep down we all know problem A and B are very good.
The statement of A is vague . Otherwise means "if one is false ,then" so I use if(b%a==0)--> no
so this make me wa 4 times
what?? where did you find statement of A vague?
That is right (the definition of Otherwise).
If divisible by A*B = good integer
Otherwise (if the above statement is false then)
If divisible by A = nearly good integer
How did you arrive at b%a==0 condition using this??
What was bad about them?
About the statement.
I think A and B are like "guess the solution and trial and error them". I did not commit anything, and still not sure about if my solution for A would AC or not.
Edit: And just realized after contest, B: "You don't need to minimize this number." So I worked on another problem.
Yeah, I also worked on minimizing, but then noticed that if it was minimizing sample solution would be suboptimal
If anyone downvote me ,that is ok, i just want to express my feeling.
I don't think the problems were bad per se
But I don't like the steep cliff from B to C
You can downvote me if you want, but I thought C was a pretty shit problem overall. Idk what was so bad about it, my implementation didn't even end up being that bad...just thinking about all the cases and working around that god-awful min-max function ticked me off I guess :\
I don't think it was a bad problem, but do agree that it was hella painful to think about. took me like a decade just to test my program on sample 1
For me it was:
But problem itself was nice for me.
Agreed, everytime I had to test I couldn't just do the queries in my head I had to rewrite some code that evaluated the queries automatically and then remove that to submit.
The problem idea wasn't so bad though, I think the function given just made it really painful.
My thoughts exactly — and even though decoding and testing those equations was painful, it was overall an interesting problem as its solution deviated from the expected binary search solution to interactive problems.
I'm so sorry...，I wanted to upvote you,but I carelessly downvoted you, your comment makes great sense,i think.
I agree, even tho i solved it, it felt very vague.
Nice problems! Слава Україні.
Thanks! Героям Слава)
Doing heavy-light decomposition from arbitrary leaf and then connecting heads and tails isnt optimal in D?
I thought to divide by diameters and then join them. Do you think this is wrong?
I took the diameter of the tree and then added all the other nodes to the diameter one by one ,passed the sample but the logic wasn't correct as it gave wa on pretest 2 ,waiting for the tutorial...
You can consider the graph with 6 nodes in H form, the answer is 1.
For God's sake, this round was not Div2... :(
My answr to D is summation{max(0,degree-2)} over all vertices, is the answer less than this?
Waiting for editorial
wouldn’t then give you 0 on the first test?
Consider a graph with 6 nodes shaped like an H. There are two nodes of degree 3, so your answer will be 2. But you can get away with 1 by moving the middle line to the top.
Ohhhhhh, didnt think of this thanks a lot
oh That H Case I spend the whole contest trying to know why my solution not optimal :/
I should have taken more time to understand the questions, made silly mistake in A and B. But loved the overall experience and looking to learn from my mistakes.
what's the cruelest thing one can do?
RESTORE THE ANSWER
I don't like it
How the heck to solve C ? Never seen such a problem like this. Actually A was badass. Could have told that the number might be divisible by B, only should not be divisible by AB
I think I was able to come up till 2*n solution but not know what to do for 3*n / 2
in ~[n/2] queries we can find the position of 1 (or n) and then using this position we can find the rest of the numbers in n-1(or n-2, doesn't matter) queries
First try to find position of n in array using query 1. You can do this by checking adjacent pairs and if their result is n-1, check the swap as well. This takes atmost ceil(n/2) + 2 queries.
Using this position of n, you can easily find all values via query 2. This takes at most n-1 queries.
So total queries are well under the limit.
Similar way you can do if you try to find position of 1.
Could you please expand ? I literally dont get it
Use $$$t = 2$$$ and $$$x = 1$$$ to find $$$1$$$ in permutation for $$$n / 2 + few$$$ queries (if $$$p_i == 1$$$ then answer is $$$1$$$);
Use $$$t = 1$$$ and $$$x = n - 1$$$ to find other numbers in permutation for $$$n - 1$$$ queries (if $$$p_i == 1$$$ then answer is $$$p_j$$$).
? t i j x Important observation: t=1 and x=n-1 max(min(n-1,Pi),min(n,Pj)) equals — n-1 if Pi=n — max(Pi,Pj) otherwise
t=2 and x=1 min(max(1,Pi),max(2,Pj)) equals — 2 if Pj=1 — min(Pi,Pj) otherwise if anyhow by using t=1 and x=n-1 we get the position of n in the permutation in <= (n/2)+30 queries , we can get remaining elements by using t=2 and x=1 in n-1 queries we can get the remaining elements in n-1 more queries.
How to get the index of n ?? we can see that for (i,j) t=1 and x=n-1 the output can be n only when Pj=n if output is n-1 Pi can be n we can check take (i,j) like this ( 1 2 ) ( 3 4 ) ( 5 6 ) . . . if the output during any stages is n we get index_of_n otherwise we get a set of possible values of index_of_n (corresponding to output n-1,with max 2 possibilites)
so we can check the index of n in max (n/2) + 2 queries after that our job is done
I wish I could just unsubmit my solutions and wait for the next contest.
hello, tried to participate for the first time — failed miserably :) (I didn't have full 2 hours anyway, but not sure it would help if I did). One question — what are pretests ? my submission failed pretest 3 (am I supposed to be able to see pretests ?) I only was able to see the example test provided in the description of the problem. Thank you
Pretests are cases that will be tested during the contest. Not all of them will be visible to you. And there will be more tests following in the system test phase after the contest.
Check out this: https://mirror.codeforces.com/blog/entry/4088
Good bye expert
Don't be sad! Good luck on the next contest! You will comeback
How to do C?
My idea was to find any one element via binary search using 30 queries ( preferably the first element), then keep constructing the permutation from left to right using at most 2 queries each. I implemented the second one, but couldn't exactly figure out how to find the first element.
you can find the maximum of the permutation in about n/2 moves with t = 1, x = n-1, changing i and j every time. If you get the result n, j is the position of the max. If you ever find an n-1, try for j and i. If then you get the result n, that means i is the position of the max.
And then using the maximum you can use t = 2, x = 1 to find each element in n moves.
Indices are have to be different. I wasted 30 mins implementing this then noticed the statement.
My not so interesting solution.
Find the position of $$$1$$$($$$pos1$$$) and you can determine the values of the remaining positions($$$j$$$ not equal to $$$pos1$$$) with queries of type $$$t = 1$$$, $$$pos1$$$, $$$j$$$ and $$$x = n - 1$$$ in at most $$$n - 1$$$ queries.
We can find the position of $$$1$$$ in at most $$$n / 2 + 2$$$ queries.
We query the indexes in pairs $$$(1, 2), (3, 4) ... (n - 1, n)$$$ with queries of type $$$t = 2$$$, $$$x = 1$$$.
If a query of returns $$$1$$$ for a pair then it's obvious that the first index in the pair is equal to $$$1$$$.
If the position with $$$1$$$ is the second index in a pair then at most $$$2$$$ of the pairs of queries will return $$$2$$$.
One with $$$1$$$ as a second value and another with $$$2$$$ as a second value.
And we can easily check if any one of those is equal the position with $$$1$$$.
If none of them is then $$$n$$$ is odd and the last position is equal to $$$1$$$.
After that the rest is straightforward
Get the position of $$$1$$$($$$pos1$$$) and you can determine the values of the remaining positions($$$j$$$ not equal to $$$pos1$$$) with queries of type $$$t = 1$$$, $$$pos1$$$, $$$j$$$ and $$$x = n - 1$$$ in at most $$$n - 1$$$ queries.
Asking queries of type 1 with $$$x=n-1$$$ will give you the maximum value among two positions asked. If the answer to the query is $$$n-1$$$, just ask the same two position again with $$$n-1$$$ value and take the greater answer of the two queries asked.
Same thing with min and queries of type 2.
After you get the maximum and the minimum, one query of type one for two position with value equals to $$$minValue$$$ (found above) will tell you which of them is the larger and which is the smaller.
I took 12 queries to figure out exactly what the first three elements are.
Then I query every other element (of index
idx) with the largest known element (of indexmaxidx)t=2, i=idx, j=maxidx, x=1t=1, i=maxidx, j=idx, x=n-1I update the largest known element along the way.
The worst case is still 2n. To avoid the worst case, I shuffle the remaining queries.
I had exactly this solution: 115619047
To find the value of the first element I used binary search:
After checking different values of $$$x$$$, I relaized that the query of type $$$1$$$ returns $$$x+1$$$ if and only if $$$x \leq p_j$$$. And it doesn't even matter what the value of $$$p_i$$$ is. This allows us to do binary search on $$$x$$$ to find the value of $$$p_1$$$, by doing queries like $$$(t=1, i=2, j=1, x=mid)$$$, where $$$mid$$$ comes from our binary search.
After we found the value of $$$p_1$$$, we can find the value of every other element in at most 2 queries. But in the worst case it might be exactly 2 queries per element, e.g. if the permutation is sorted in reverse. That's why I shuffled the indices, hoping that it will take 1.5 queries on average.
Why was problem statement of B written in reverse order? It was so confusing before the statement got changed. The conversion of pair was written before the condition which didn't make any sense.
Isnt finding the diameter of the tree and then using Topological Sorting the intended solution for D.
ya I am thinking the same, like partition tree into a minimum number of line graphs and then join those graphs, it can be done in O(n) I think, but couldn't implement
Today I learnt that being divisible by
a*bis not equivalent to being divisible byaand divisible byb.how? please give me some example
for example 12 is divisible by 4 and 6. but is not divisible by 24 (4*6)
Your right but
He said the converse, which I think isn't correct.
24 being divisible by 24 is equivalent to 24 being divisible by 4 & 6.
48 being divisible by 24 is equivalent to 48 being divisible by 4 & 6. and so on...
Sometimes the things which appear to be so obvious also turn out to be wrong.
1) ConstructiveForces 2) MathForces 3) PoorForces
Why I kept reading "a*b" as "a and b" in the A problem?
problem B was looking carefully on constraints.
a[i]<=1e9
x,y <=2e9 and 1e9+7>1e9 is prime :)
Yaaa, I exploited the same and used a segmented sieve to calculate primes from $$$1e9$$$ to $$$1e9 + 1e7$$$, and turned each number into a prime other than the smallest one.
int A[] = {1000000409, 1000000411, 1000000427, 1000000433, 1000000439, 1000000447};all are primes greater than 1e9 I made this array and turned every element except smallest element into one of these elements.I feel Pepega right now.
Oh shit!!! I didn't notice. Will take care next time...
realized that except the minimum element all elements can be changed to any other so simply swapped the first and minimum element and did a[i]=a[i-1]+1 for all i bw [1,n-1]
I approached another simple solution . As all the consecutive pair of integers are co-prime so just find the minimum element and its index from the array. Then change all the elements according to this order. Suppose the array is
a[]={9, 6, 3, 5, 11}minimum element is 3 so change the array intoa[]={5, 4, 3, 4, 5}That means make the elements increasing order from the minimum index to left and right.What was the answer to D? What was the counterexample to selecting the maximum diameter for a tree, disconnecting the edges on the maximum diameter path, and then recursing on each individual component to create the bamboo?
Exactly!!! I also tried the same approach but I made a stupid implementation mistake :/, got RE instead. :(
1 2
1 3
1 4
1 5
5 6
5 7
5 8
Dia is 2 — 1 — 5 — 7 but ideally 1 — 5 should be removed
FRICK
What was the actual solution then?
Well, I did a DFS. While leaving nodes I removed iteratively edges, which connect two nodes with both of them with >2 neighbours (this fixes two nodes). Then I traversed all nodes again and removed edges from each node with >2 neighbours (this fixes only one node).
Then I have only sub-Bamboos left and need to stick them together on the ends.
It passed the Pretests, but it is very greedy like this, the only sorting is the DFS. Not sure whether it passes Tests.
Edit: Yes, it passed the Tests: 115602037
I first find the minimum path cover of the tree using dp, and then reconstruct those paths and connect them. 115645578
The following graph with 10 vertices was helpful for me to think about it:
You can solve this with 2 removals, but your method will make more if I understand it correctly
Yeah u rite, I would take 4 while urs 2. What was the actual solution then?
You want to remove as many edges which connect 2 nodes of degree 3 or higher as possible (call these type 1), then remove extra edges off of nodes of degree 3 or higher (call these type 2).
However, the example I showed proves that doing this randomly won't work (what if you accidentally remove the middle edge first? Your answer will be 3.
If you consider the graph of only nodes with degree 3 or higher, then you will always make an ok move if you remove the type 1 edge branching off those nodes. Then when the graph is all singletons, you can just remove the rest of the type 2 edges.
However, this is pretty finicky to implement and there may be a preferable solution. https://mirror.codeforces.com/contest/1521/submission/115618524
Yeah, I guess that also sounds like my solution: 115602037. To sort type 1 nodes I used a DFS and checked for them while leaving the nodes.
Consider the tree that looks like an H.
We can build the bamboo with 2 operations by removing the middle edge and reconnecting the both parts then.
With the longest path algo we need 3 operations.
OK... Only solve A... WA 5 times. LOL
Tbh felt more like Div1 than Div2, solving only A and B in Div2 sounds bad..
FOR A why is this incorrect x+y==z (a)+(a*b)==(b+1)*a ng g ng
if(a==b||b==1)---no else yes???
A can be equal to B take 2 2 for example you can make x = 2, y = 4, z = 6
but here there are more than 1 good int..it should PRINT NO ?
Y=4&&Z=4 ARE TWO GOOD INT HERE.
Why is z = 4 ? (2+1)*2 = 6
Only 4 is a good int here ,as good int are divisible by A*B 2 and 6 are nearly good int as they are divisible by A
if(b==1)then only no friend
Why b==1 mate? If we have 7 1 can't we display 7 14 and 21
1 is divisible by all 3
For a = b, a*(b-1) + a = a*b
In case of a==b (of course b is not equal to 1) also , a*b + a = a*(b+1) will work As only there is 1 good int i.e. a*b and 2 nearly good int's a,a*(b+1)
He has written NO for a=b case.
There is answer if $$$a == b$$$
If $$$A = 5, B = 5$$$ then you can print $$$20\ 5\ 25$$$. First two divisible by $$$5$$$. Third divisible by $$$25$$$.
a could be equal to b
For example take a = b = 8, x = 8 , y = 56 and z = 64
I can explain my solution if b is 1 then the answer is no, since in this case b will divide all no.s x=a*(b-1) if b is not 2, y=a , and z=a*b , a*(b-1)+a=a*(b-1+1)=a*b else x=a*(b+1) , y=a , z=a*(b+2) , here since b is 2 , so b will divide (b+2)
print A*B , A , A*B + A when B!=1 and when B==1 answer as NO
Link to Explanation of Problem A
How to solve D ??
I swear those min/max functions in C looked exactly like this on my screen...
I got hitmotised honestly!
Solved A in 2 attempts, and B in 6 !! Really great questions, learned a lot. _/_
My learnings from the contest: Nobody knows what a good array looks like
I was able to solve D by reducing the problem to the minimal path cover problem and solving that using dynamic programming. Is there any other way to solve for the minimal path cover in a tree?
Can you please also give links to minimal path cover good articles?
Also, can you tell any case where minimum answer won't be just cascading child (when >1 for non-root node)? Can't think of even that :(
Truly interesting round, but I lost tons of point on WA :(
By the way, how to solve E...I tried to construct a grid like this:
Where $$$x$$$ presents the number. And then expand this grid's size by one per step, randomly fill other numbers in available positions.
In problem B, earlier it was "any i" then it got changed to "all i's".. -- WA.
Also, Goodbye expert :p
The given sample testcases should've cleared it out, I had to check them to make sure I was getting it right. Although all in all yes the question was poorly written at the start of the contest.
My idea for Div2D
Is this logic correct ?
I think, it's wrong. I took this counterexample:
Your algorithm can remove the middle edge and then it can't be done in 2 removals.
Thank you !
i wish, i could undo myself 3 hours back!
Is it round from I_love_myself? (According to the names of the tasks)
Unfortunately, no. But Nastya is happy!!
Thanks for the contest, I really like problems B and E. None of the problems alone are bad, however looking at all of them together felt monotonous. There wasn't much diversity in the set and the statement seemed confusing at times.
div 1.5 huh?
more like div 1.25 tbh
Deleted.
More like 1.3141592653589793238462643383279502884197169399375105820974944 5923078164062862089986280348253421170679821480865132823066470938446095 5058223172535940812848111745028410270193852110555964462294895493038196 4428810975665933446128475648233786783165271201909145648566923460348610 454326648213393607260249141273724587006606315588174881520920 9628292540 9171536436789259036001133053054882046652138414695194151160943305727036 5759591953092186117381932611793105118548074462379962749567351885752724 8912279381830119491298336733624406566430860213949463952247371907021798 6094370277053921717629317675238467481846766940513200056812714526356082 778577134275778960917363717872 tbh
Was only able to solve, A and B, so maybe I'm not qualified enough to say this, but the problems were good. Especially the B one, had to stress test my code to find a mistake XD. Also, problem A showed me the importance of reading a problem carefully and not underestimating A (spent over 30 minutes on it LOL). Don't know if I'll sink or swim in this one, but it was a fun one.
for Problem A,
a=1, b=1
why x=1, y=2 ,z=3 is not a answer? x+y=z
Because all three numbers are divisible by $$$A * B = 1$$$. You required that exactly one number is divisible by $$$A * B$$$
Because, x,y,z are good(x,y,z are divisible with a*b=1*1=1)
no ; cause x,y,z all are divisible by A*B mean there all Value is good......but condition is any 1 Value good......
because 1, 2, and 3 are all divisible by (a * b = 1)
Just commenting because I saw the fireboy image and could not find icegirl. Used to think nobody liked the game(except me)
I solved B by converting the array in the following way — {1e9 + 7 , min(a[0],a[1]) , 1e9 + 7, min(a[2],a[3]), 1e9 + 7 ........}. Then if n is odd I make a final operation n-1 and n-2 making a[n-1] = 1e9 + 7 and a[n-2] = min(a[n-1],a[n-2]). Here is my solution(https://mirror.codeforces.com/contest/1521/submission/115604019).
explain the approach of A bro? i got TLE!
Link to Explanation of Problem A
I think the authors wrote Div.2 instead of Div.1 by mistake. (not saying contest was bad. It's just I was bad at those questions)
At least A and B was ok for div2
Why does 115570549 give MLE for B?
If $$$n = 1$$$ you output 0, but don't read the array element, so on the next iteration you'll read the array element instead of $$$n$$$, which can be up to $$$10^9$$$.
Solution for Div2B without using
10^9+7. Find the index of minimum element(if there are more than one choose any). Let's call itidx. Now use this index with every other indexiand do,Yes, did the same
I did in same way :)Link
What wrong in my solution? https://mirror.codeforces.com/contest/1521/submission/115596986
Try this,
1
3
35 9 5
Answer should be zero . My also giving zero.
I apologize, my bad. Try this,
1
3
2 21 14
Mine Even simpler
bad contest, very bad problem C. Please don't allow blue to make any contest from now.
Looks like my dream of becoming an expert will always be a dream :(
no mate you will be there in a month.
Level of questions were very good. Even first problem was good enough to take time.
for problem c i listed all the possibilities, and figured that if query(t = 2, l, r, x) gets the answer exactly x meanwhile query(t = 1, r, l, x) gets the answer lower or equal to x, then p(i) is not more than x. thus we can do binary search and the total queries will not exceed nlogn. however it got WAed on pretest 3, may someone help me?
$$$n * log(n) \ge (3n / 2) + 30$$$ for big $$$n$$$.
Thanks, I even forgot how to compare them during the contest! What a stupid mistake :P
Hopefully, I can become an expert for the first time. BUT I DID'T
Rebecoming expert here
I really liked the idea behind problem D. It was just amazing. Although i wasn't able to solve D in the contest but learnt a lot.
Btw great contest.
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Can anyone give me corner for B,I dont know why my approach failed? karavaiev
1
3
4 25 10
Check this Explanation
today 10^9 + 7 proved it's importance to me...great contest btw.
Karavaviev please don't make any contest in future problem A its was so easy input 3 5 3 13 2 7 11 output YES 10 50 60 YES 169 39 208 YES 28 154 182 WTF
And why you don't like it?
As if you would have done better. The contest was very good, I liked the problems. They were very interesting, especially I liked problem B.
Posted by a dude who didn't solve this problem
Very nice contest. Thank you Karavaiev.
"I tried my best to create interesting problems and clear statements, so don't forget to read all ones :)"
A problem was very unclear karavaiev "Otherwise, the integer is nearly good, if it is divisible by A." this mean nearly good no. can be divisible by B or not? Eg. 4 2 Correct o/p : 8 4 12. In whole contest i was thinking it cant be divisble by B and ruined the contest
Why "otherwise" was not clear for you ?
You could have asked in the 'Ask a question' section, I also asked a query related to problem B and got the reply instantly.
https://mirror.codeforces.com/contest/1521/submission/115630016 this is my solution and it showing wrong output format Expected int32 anyone plz tell me how to resolve it??
wrong output format Expected int32, but "11957579097" found (test case 451)
your output should be in range [1,2e9], but "11957579097" too large.
I got it,thank u
Where can I see the editorial?
in problem B..........for input 9 6 3 11 15....my output is.....1 2 1500450271 6 and 2 3 1317313771 3....the array becomes.........1500450271 1317313771 3 11 15....why is this wrong.....actually my approach is whenever the gcd of two consecutive element is not 1....greater element will get replaced by a prime number(p)... 1e9 < p < 2*1e9 my solution https://mirror.codeforces.com/contest/1521/submission/115631210
at your submission page's bottom,
"Click to see test details"
It helps.
Can you explain how to solve task D?
In D, The given sample 1st test case tree is already bamboo tree. Every node have 2 child
But why it require some operation
A bamboo is a tree in which no node has a degree greater than 2.
Number of child is different from degree(except for root)
Where's editorial?
.
It's hard to say that the difficulty distribution of problems was very good. A and B were not that easy either, and C apparently seems to be harder than the usual C. Not to mention D. I think that the good problem doesn't guarantee a good contest :(
This was the toughest codeforces round for me till now. :)
In problem A how you answer 56 8 YES And print 3 good integer while you said exactly one ???
What will happen when A=4 and B=1?
Answer is NO
Codeforces Div.2（NO） Special Problems Round（YES）
Problem E is interesting :)
In problem A if A is divisible by B the answer must be No but my solution got accepted without handling this case ... I smell an unrated round :(
Edit I smell my stupidity XD
Check this example - a=6 , b=6 ('a' is divisible by 'b') Here Answer is "YES" One of the possible x,y,z is :- 6 , 30 , 36
But there's no nearly good numbers here just like when B=1 x y z are just good numbers they are all divisible by B so answer can't be Yes ... Some people saying that A%B!=0 but that wasn't mentioned at all that's not right
x and y in the above example are nearly good numbers. The case of b=1 is different. In that case, the numbers are not only divisible by b but also by a*b.
Note that nearly good numbers can be divisible by b.
Now I get it thanks divisible by A*B doesn't mean divisible by A or B
Google Forces......
A similar problem compared with Problem D.
Really impressive
(deleted)
Why are Interaction Problems actually useful when we can do it normally(In the sense standard way of I/O) as well good contest btw learned a lot
Is there a solution to D?
Why my blog is hidden in the recent blog tab? Sorry for writing this here cuz i'm not able to write a blog now!
Problem A : Shouldn’t the answer be NO if a is divisible by b?
All tasks have "constructive" tag?!
Спасибо за раунд!!!