Hello, Codeforces!
Members of team EZEC are glad to invite you to participate in Pinely Round 1 (Div. 1 + Div. 2), which will start on Nov/20/2022 17:35 (Moscow time). You will be given 7 problems, one of which has a subtask, and 2 hours and 30 minutes to solve them. The round will be rated for everyone. It is greatly recommended to read all the problems.
There is at least one interactive problem, so please see the guide of interactive problems if you are unfamiliar with it.
We would also like to thank:
- Our red sun orzdevinwang, the youngest TOP10 coder in history, for illuminating our path.
- Our great emperor antontrygubO_o for cooperating and coordinating with us to make this round happen. He saved the round by contributing his problem when a problem was found similar to an existing problem.
- Our authors for providing great ideas (both rejected and accepted): orzdevinwang, dXqwq , Forever_Pursuit, SpaceJellyfish, unputdownable, RedreamMer, pigstd. Without them, the round couldn't have been prepared so quickly.
- Our testers for high-quality testing and valuable advices: Ecrade_, cmll02, Redcrown, mtw, jqdai0815, pocafup, ieeqwq, Mooos, Justcyl, do_while_true, Ari, ffao, InternetPerson10, feecIe6418, __ZMF__, dingdingsb, PubabaOnO, lqx2005, myee, louhao088088, LinkZelda, Inversentropir-36, KagamineRin, zaozao_zmx1, Promisenxt, Tom66, RedLycoris, DearMargaret, Lynkcat, zeliboba, Kostroma, iwalainz, zemen, MELNIKOFF_OLEG, AndreySergunin, _overrated_, nick.sh, oleg_smirnov2001, kokokostya, lxyb, halin.george, Endagorion, I_love_myself, SSerxhs, LMOliver, George1123, Um_nik, 244mhq, apeiya.
- MikeMirzayanov for the great systems Codeforces and Polygon.
Fun facts:
- Anton reviewed 18 problems in total.
- This is the 13th round of EZEC. Here are some previous rounds: Round 11 on Luogu, Round 12 on nowcoder.
- The team has an anime character EZEC-chan (the girl in the image), hope you like it :3
- orzdevinwang found a better solution of F the day before the contest.
This round is made possible with the support of Pinely!
Pinely is a privately owned & funded algorithmic trading firm, our main focus is set on high frequency and ultra low latency trading.
We are a team of mathematicians, programmers, engineers and computer scientists driven by the immense passion for knowledge. We constantly face various challenges such as developing strategies for trading, optimizing trading systems to achieve the lowest latency reactions to various market events, saving and processing large volumes of historical data. The work we do requires a high ability to create effective C++ code, algorithmic thinking and mathematical intuition, which attracts winners, awardees and medalists of various competitions in the respective fields such as ICPC, IMC, HITB PRO CTF and Google HashCode etc.
Find out more about us on our website pinely.com or from our employees registered here on CF.
If you want to join our team please send your CV to [email protected] or fill in the form
Top 30 contestants and 10 random contestants placed 31-100 will receive a branded Pinely hoodie :)
The statements were made as briefly and clearly as we could. GLHF!
Scoring distribution: 500 — 1000 — 1250 — 1750 — 1750 — (2500+2000) — 3500
UPD1: Editorial is out. link.
UPD2: Congratulations to the winners:
Auto comment: topic has been updated by pigstd (previous revision, new revision, compare).
Where is fyy Memorial Valley School
In fact there's something more about the problem D: As a tester, I give out a solution with BGF and ODE for it. So in fact, this problem still can be strengthened. :)
But to make the gap less large, the problem provider didn't do that. :)
However, the gap between D and E might be even larger than such between C and D. :(
i am agree with him
In fact there's something more about the problem D: As a tester, I give out a solution with BGF and ODE for it. So in fact, this problem still can be strengthened. :)
But to make the gap less large, the problem provider didn't do that. :)
However, the gap between D and E might be even larger than such between C and D. :(
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
haha I broke your silly chain
All hail our emperor anton
All hail our emperor anton
All hail our emperor anton
haha I broke your sacral spine
are you broke :))))
All hail our emperor anton
broke another chain
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
haha broke your silly chain
recursion base case reached
orzdevinwang orz
orzdevinwang orz
no
orzdevinwang orz
pocafup orz
orzdevinwang orz
orzdevinwang orz
orzdevinwang orz
As a tester, i'd say
Anyone who upvote me can get high ranks in this contest
If my rating dropped,I will downvote you!!!
If it's tried, "You cannot vote twice. You have already voted for this comment before."
Anime round is coming :|
As a tester, I'm cute (。・ω・。)ノ♡
pigstd orz
pigstd orz
pigstd orz
pigstd orz
pigstd orz
pigstd orz
pigstd orz
pigstd orz
pigstd orz
pigstd orz
As a tester, I strongly recommend this round for straightforward statements & high-quality and interesting problems. GLHF!
Who is she?
my mommy
WAIFU!!!! We really need an anime-mascot-cute-girl for codeforces <3
I can't wait to see that!
Just noticed Technocup 2022 Elimination Round 1 is going to be held tomorrow as well (which in the past years has a live mirror on CF). Are we going to have 2 rated CF rounds in the same day ?
This year Technocup will be held not on Codeforces, but on the Allcups platform made by VK so unfortunately it seems to me there will be no mirror.
Wow, EZEC Round! EZEC is one of my favourite Chinese problemsetting groups. Looking forward to solving the problems with high quality.
Is it hard?
Maybe hard I think.
In this round, we tried our best to avoid weird, difficult and confusing problems. Let's discuss them after the contest!
are you sure about that?
What a cute blog ._.
She is so cute!
Looks like a good contest, good luck everyone!
After seeing the photo I really have a good feeling about this round
happy world cup day
Stop putting otaku images in codeforces!
I apologize if it bothers you. The picture is a representation of our team spirit. She is not from an anime. We designed the picture and spend a lot of time and money to make her alive. I appreciate your honesty and hope you like her
is pigstd a girl? pigstd
If you take a look at her profile, you will know that she is Chisato Nishikigi, obviously a girl. She even has a picture of herself uploaded as proof.
Yes!I'm her classmate,she is so cute! :d
cute~~ girl pigstd!!!
Dude, this is not important, the important thing is that pigstd is really cute.
It depends on your imagination :).
Hopefully I can hit 500+ this round :)
Rated?
Rated for everyone
The problems are very nice, recommend participating.
I hope there will be no anime in the problem description.
The statements were made as briefly and clearly as we could.
Don't worry :)
dXqwq orz
orz
I hope I can be red this time!
is this rated?
Great progress on the announcement
CF plus World Cup night!
Is China in the world cup?
yes! in the same group with Italy (
All hail our emperor Anton :)
how did you draw the anime girl? did you get it commissioned?
Red Round and The World Cup.... just I need tourist beside me and a tub of popcorn... Rank 1 and amazing World Cup guaranteed ^,^
Ah, why it couldn't have been moved a bit earlier so it doesn't clash with WF opening? :/
How young is orzdevinwang?
Grade 10
:depression:
good luck everyone !
Weebs Get a life
EZEC-chan is so cute!
Off topic: where does EZEC-chan's tail come out from?
Is pigstd really a girl?
Of course a cute girl~
Don't be cheated by his anime girl profile.sure.What is your definition of girl?
how is this div1+div 2? where is the div 2 in this lol
average newbie
ironic
I would love to get castrated by both of you.
mm yes
so inspirational
It is difficult for me,I wrote problem A and went to bed. After reading B and C, I have no idea. I want someone to teach me, after the game
me too... -120+ yay
wasted starting 10 minutes figuring out wtf is common prefix and sufifx
How are you a specialist?
By solving question in contest and ignoring people like you.
Me too but i wasted like 25 min something
Oh, the round seems to be more difficult than the writers expected, but as difficult as I expected, because I'm just a low-level taster.
btw, the writers are watching the World Cup.
Why not try the next div4 Codeforces Round 835 (Div. 4) to gain your confidence and rating?
Because it's on Monday and not on weekend.
Spend 1h on E because I forgot to check whether the vertex is a cut point and 1h on an incorrect solution of F. :(
is there a nice way to cover this case? i ended up directly checking the validity of my candidate answers in $$$O(n^2)$$$ with bitset.
I did the following:
Find arbitrary spanning tree, choose any leaf in it. It is definitely not cutpoint. In case it has degree less than $$$s - 1$$$, (where $$$s$$$ is the size of current connectivity component), you can switch it and you're done. Otherwise, switch any other node, for example, adjacent of the leaf in the spanning tree (as I did it).
hmm I'm not sure that any node works in that case, since there can be other nodes in the spanning tree that are also degree $$$s-1$$$. for example, the case
which looks like
hacks your solution 181782667. If the spanning tree is a star graph about 1, then choosing node 4 as your leaf will cause you issues, as it and its parent are both connected to everything.
Any smallest degree vertex in the component works (unless it's a clique which is a different case)
Doesn't this break for this example:
1-2, 1-3, 2-4, 2-5, 4-5, 3-6, 3-7, 6-7
1 has the smallest degree of 2, but it is a cut point.
Edit: Oh, I guess it works for the overall problem, though.
Yes, doesn't matter if it's a cut point, it will always give an answer set of size 1.
How to solve D?
put $$$a$$$ and $$$b$$$ on top of each other, and lets build a string $$$c$$$ of length $$$n$$$ on the alphabet $$$(0,0)$$$, $$$(0,1)$$$, $$$(1,0)$$$, and $$$(1,1)$$$ (i can't get the column vectors to play nice with the inline latex, but the first one goes to $$$a$$$ and the second goes to $$$b$$$). we will count by starting off with the empty string, and sequentially inserting characters into valid positions.
carries are started by a $$$(1,1)$$$, are continued leftwards by either $$$(0,1)$$$ or $$$(1,0)$$$, and are terminated by $$$(0,0)$$$ or another $$$(1,1)$$$.
suppose we will place $$$x$$$ chains of carries, where $$$1 \leq x \leq k$$$. we will place $$$x$$$ of $$$(1,1)$$$ and $$$k - x$$$ of $$$(0,1)$$$ or $$$(1,0)$$$ that will continue these chains. we have $$$2$$$ characters to choose for each of the continuations, and we must place these $$$k-x$$$ items into one of $$$x$$$ groups, so there are $$$2^{k-x}\binom{k - 1}{x - 1}$$$ to make this assignment.
now, for each of these $$$x$$$ chains, either it will be terminated by a $$$(0,0)$$$ or by the $$$(1,1)$$$ that starts the next chain. let's manually terminate $$$y \leq \min(x, n-k)$$$ chains with $$$(0,0)$$$. there are $$$\binom{x}{y}$$$ ways to place these.
we have $$$n-k-y$$$ non-carry positions left to place. each of them can go in one of $$$y+1$$$ groups: either to the left of one of the $$$(0,0)$$$'s, or on the very right before any of the chains have begun. there are $$$3$$$ legal characters for these: $$$(0,0)$$$, $$$(0,1)$$$, and $$$(1,0)$$$. thus, we have $$$3^{n-k-y} \binom{n-k}{y}$$$ to fill in these last positions.
our answer comes out to
from here, i brute forced my way though to the end using a convolution, so there is likely a more clever solution. nevertheless, i manipulated the equation with
note that the inner summation is a convolution of two sequences $$$p$$$ and $$$q$$$, where
precompute the inner summation with your convolution tool of choice in $$$O(n \log n)$$$, which allows us to compute the outer summation in $$$O(k)$$$.
how to do D without breaking out the arbitrary mod FFT/NTT?
I got to the following formula:
where $$$i$$$ is the number of blocks of consecutive carries (11 followed by 11,10 or 01 any number of times, ended by 00). The binomial coefficients count the placement of these blocks within the n bits. The second sum accounts for the case when the last block is not ended by 00.
If you want a continuous sequence of k carries then consider two binary strings a and b of length k+1. The first bits of two strings must be 1 and the last 2 bits must be 0 and for the rest of the positions at least one of the bits must be 1.
Note: first means the least significant bit.
Based on this, we can solve this using a bunch of combinatorics.
I could think of this during the contest, than my idea came out to be that we want to divide a block of size n + 1 into f different blocks of size >= 1, f = n + 1 — k as the root idea is a block of size k + 1 dimineshes it into k, its true for all k >= 0, so we need size of k + 1 >= 0
I think somewhere in the middle i started to think too much and it all became a mess but can you explain how to move ahead after this, or what is wrong in my approach
Let's consider i blocks with sum lengths of all blocks being k, then there are two cases
GREAT ROUND, How to solve Problem C? and can anybody prove why answer always exists?
It doesn’t. The checker guarantees that the answer exists for all testcases.
The answer does NOT always exist. The problem specifically implies this. However, the problem guarantees that an answer must exist for each test case, so you don't have to worry about these no-answer scenarios.
A simple counterexample is when every row has at least one 1. Since there is no all-zero row, this means every set is a proper subset of another set, which must lead to a cycle of proper subset chains, so each set in this cycle is a proper subset of itself, which is impossible.
Anyway, my answer was to enforce a rule that the number $$$i$$$ will only appear exactly in set $$$i$$$ and its proper subsets. I'll refer to $$$i$$$ as the ID of set $$$i$$$. This fulfills the three conditions:
Sets are non-empty (must contain its ID) and values are from $$$1$$$ to $$$n$$$ (all IDs are from $$$1$$$ to $$$n$$$, and no other values are considered).
All sets are distinct, because if we consider any pair of sets, they cannot both be proper subsets of each other (this leads to a contradiction as I mentioned above), so the one that isn't a proper subset will lack the ID of the other.
Binary Matrix representing proper subsets is proven by how we construct the sets: for row $$$i$$$ of the matrix, we add the ID $$$i$$$ to each column $$$j$$$ for which $$$b_{i, j} = 1$$$. This fulfills the third condition, while also following the ID rule.
My submission: 181766895
In problem C:
what should be the answer for this test case:
My code returns this:
B and C were pretty "sucky sucky" problems.
Hopefully I lose enough rating to do tomorrow's Div 4 contest
For Problem E, if there is a component which contains a cycle, how do we determine the minimum non-zero number of operations that can be performed on it such that the component remains connected?
I realized that the answer is $$$|C_u|$$$ if $$$C_u$$$ is complete, and 1 if $$$C_u$$$ is acyclic but not complete, but I couldn't figure out the solution for general graphs. Can anyone provide a hint on how to solve this general case, or at least let me know whether there is an easier alternative approach for solving E?
I have thought of this solution:
Let's think the graph is not connected.
Let's think there is no single vertex, else we could invert its edges.
If there is a connected component that is not complete, let's invert the edges of one its vertex that is not a joint and is not connected to all vertices of the component. Then it will be connected to at least one of the other vertices and the other vertices themselves will be connected together. Note that if there is a vertex of the component that is connected to every other vertex, the other vertices are all not joints, and if there is none, the leaves of the DFS tree still are all not joints.
If all the components are complete, there are either two components or more.
One possible answer is to invert all the vertices of any component.
There is another way to do it if there are >= 3 components. We can see that if we invert a vertex in each of some two components, the graph will be connected. (Note that after we invert some vertices, the not inverted vertices of each component will be connected together and the inverted vertices of each component will also be connected together and also with the not inverted vertices of other components.)
I understand that if there is a degree-1 vertex in a component with $$$\geq 3$$$ edges, then this vertex alone is enough. But there is a broad set of graphs for which no vertex has degree-1, but the graph is also not complete. Inverting all vertices in this component might not be optimal (which pretest 4 thankfully demonstrates), so how do we determine the optimal number? Is there some clever way of choosing which vertices to invert that leads to an optimal solution?
Spent more than half of contest trying to figure out amount of ways to choose t blocks of k elements from n positions and didn't seem to succeed(problem D). How to solve it?
First N choose t for the places, then for the sizes, we have t integers summing up to K, each must be greater than 1, it's a case of bars and stars.
Thanks! But shouldn't we take care about cases where for example n=5 last block is at position 3 and it's size more than two(0-indexed)?
The way I imagined the places, was rather than based on a fixed position, based on insertion between blocks of n-k integers. As in, if we have n-k integers and we need to place t blocks of a total of k between them, we have n-k+1 possible places a block.
Thanks! Got it now.
In problem G, the time limit seems not to be enough to make the allowed number of queries interactively.
dalbaiob
Can problem $$$D$$$ be solved using $$$DP$$$ and matrix exponentiation trick to optimize the $$$DP$$$ to not end up in a complexity of $$$O(N\cdot K)$$$?
If so, how can we use matrix exponentiation in this case?
In fact we can solve the bonus of D with DP, but need some hard knowledge. :(
You will see it in the tutorial soon.
how to solve E? because I don't get what's wrong with my code
I don't know your approach, but here is a counterexample: graph with two components A-B-C and D-E-F, both paths. The answer should be 1, because if you apply the operation on any vertex other than B or E, the graph becomes connected. The test-case format is:
More generally, if there is a connected component with at least 3 vertices and at least one vertex has degree-1 (which is always true for a tree btw), then choosing this vertex would always be sufficient. It will connect to all other components, and although it loses an edge with its neighbor, it will gain edges to the other neighbors of this neighbor, so connectivity within its own component is preserved.
(I didn't solve E btw, but this particular subcase I was able to establish)
Thank tou for the counterexample!
Penalties for wrong submissions are killing me. And it's not just in this contest, but in almost every contest I participate in. Last 6 contests: 15 wrong submissions of which 9 are in last 2 contests...
Any advice on how to have mental energy to spend extra few minutes checking if the solution is actually correct?
how to solve D?
A really huge gap between C and D.
Oh I so agree !!
How to solve E ?
Is C is to hard or I'm just a rookie ?
if (User.rating <= 1300) { cout << "ROOKIE\n"; } else cout << "HARD\n";
FSTforces.
If anyone is curious, my take on
Consider the subarray of length 3 case. Since the median cant be in the middle, this rules out cases where for a 3-tuple (a, b, c), either a > b > c holds true, or a < b < c holds true. So this lets us know that there is a zig-zagging throughout the whole array, it always will go up and down. Some elements will always be less then their adjacent neighbor elements and some will always be higher, we will denote those low numbers and high numbers respectively. Now, notice that in a subarray of length 5, WLOG suppose the middle number is a low number. In order for it not to be the median, either the first, the last, or both the first and last numbers must be greater than it. If this is not true, than it is the median. For example, (3 5 1 7 2) is valid, so is (5 9 4 7 2), but not (4 9 7 8 5). Let us look only at this pattern that happens between the first, middle, and last numbers in a 5-tuple, suppose the 5-tuple is (a, b, c, d, e), we shall call them (a, c, e) respectively. As we said before, either a, e > c, a > c > e, or a < c < e. This tells us, that if a < c, then it must be true that c < e, and likewise if e < c, then it must be true that c < a. From this we can deduce that when the 'low' numbers start increasing, they will stay increasing, and likewise for decreasing. What we get is a 'V' shape in the 'low' numbers, they will start relatively high, reach some minimum, and only increase from there. WLOG this can be extended to the 'high' numbers. Since we have a 'V' shape at the bottom, and an upside down 'V' shape at the top for the high numbers, we now know that all the high numbers are larger than all the low numbers (which is something that was not obvious to begin with). This knowledge allows us to determine that the first n/2 numbers are low, and the last n/2 numbers are high (some edge cases). So you can treat them separately. This allows us to take the odd and even indices, separate them, and squeeze them back together to get two equivalent problems:
We have now reduced the problem to: "given a partially filled permutation, find the number of valid permutations that have only one minimum/maximum (depends on whether we are handling the 'high' or 'low' numbers case". It would take a visual representation to show you how to do this efficiently, but it is certainly doable within O(n log(n)) time, possibly faster.
But for those wondering, the next part of the solution is along the lines of:
you can come up with an interval where you know for sure the lowest x numbers are (including the minimum) for some X which you can find by looking at the pre-filled numbers in the permutation, and following the direction of increasing/decreasing pairs. (or x = n if there are no pre-filled), then, by doing the same method, you can look at the interval between all the pre-filled numbers in the permutation, working your way up from the minimum, and then, based on that determine that the numbers a-b, for some a and b, will all be placed in two intervals of certain size. Continue doing this until you reach the edges of the array, and you are done. Once you get those assignments of "there are x numbers that I must put in decreasing order among y positions, and increasing order among x-y positions", such as: putting 3-7 in [-, -, -], [-, -] which you can do like this: [3, 5, 7], [6, 4]. The way you get the number of possibilities is by saying "I will place numbers starting from the highest going to the lowest, either in the left or the right array". So in my example, you would have 01010 (left, right, left, right, left). In other words, you would have (x choose y) ways of setting that up. Once you have all your various X's and Y's, your answer would just be the product of (X_i choose Y_i) for all
i
. Repeat for the 'high' numbers, multiply the two together (this will also ensure that if one of them has no possible solution, you get zero), and you are done! oh, add mod as well :].
you are not alone
Anyone help me.....What is the output for this test case in problem B.
14 1 2 3 2 1 2 1 2 1 2 1 2 1 2
If it give answer n ? how it is work ?
remove 14 then 2 next to 3 then 1 next to 3 and so on until everything is removed
ALL of the following simultaneously being true for problem D is pretty infuriating:
:(
A speed-round for contestants who didn't solve D
D is a problem of distributing 1s into blocks, which is easy.
how do you do the case for distributing 0s? The first 0 of each block has to be both 0, and other 0s has 3 ways to get it
stupid e
Why is my solution getting WA for problem E?
My Logic:
Please correct me if my approach is not correct.
First of all, the graphs are undirected, so every connected component is "strongly connected". I don't understand how you arrived at Steps 4 or 5, but neither are correct.
Counterexample for Steps 4 and 5: consider two or more trees (a component with no cycles within it) of say, size 50 each. Then the optimal answer is 1. Just pick any leaf (degree-1 vertex); the operation will connect it to all other trees, and although it loses the edge to its parent, it gains an edge to its grandparent, so it is still connected to its parent and all other nodes in its tree.
Your solution is (almost) correct, look at test 4 to find error in logic. I one-line-fixed your solution: 181807261
From guitarhero_0221 's comment test case, I realized that we can't directly remove any node from the non-complete-component. We should first check if removing a node from this component still preserve the connections between other nodes in the same component.
But, why does reversing the component fix the solution?
Unlike first vertex, last vertex in dfs order will never break condition "check if removing a node from this component still preserve the connections between other nodes in the same component". This vertex will be one of the leaves or vertex on some cycle.
I fell into this trap too. And could not understand this until I saw test above. Tourist solves this "issue" by taking last vertex of bfs order if all vertices are not connected to each other
Wow, thanks a lot. I understood it. Also I was thinking instead of reversing( or getting the last vertex of bfs) we could sort the nodes in each component based on the degree of that node. Will this work?
Upd : Yea Its working, Thank you Igorjan94 :)
Yes. This way we will get leaves first (or if there is no leaves we don't care at all about order and can use any vertex)
One down, one to go
Updated: Accepted!
Seems like this solution of mine for B is similar to editorial. May I know a testcase where it'd be WA?
submission
Thank you in advance!
When
n <= 3
you don't read the rest of the inputwhy this is wrong for the first test case ?!
3 1 2 3
1 1
2 1 2
4 1 2 3 4
1 1
2 1 2
3 1 2 3
set 3
[2 1 2]
can't be a proper subset of set 1[3 1 2 3]
Congratulations to dorijanlendvaj for reaching LGM with a 2nd place finish!
dorijanlendvaj ANIMALL!!!
Can somebody please check where my toposort solution of C is wrong
put your full code in ideone , we don't know what the "topoSort" does
Submission
The solution is wrong because of this part of the problem statement: "In other words, bi,j is 1 if Ai is a proper subset of Aj and 0 otherwise.".
Also if you get WA on pretest 1 (the samples from the problem statement), then you can look at the failure details even during the contest and the checker says "wrong answer Not meet the requirements of b_{3,1} (test case 1)". I made exactly the same mistake in my initial submission: 181794076
Really liked problem E. Thank for authors of contest!
Why is my solution getting WA for problem E? sorry for my bad english and thank you in advance https://codeforces.me/contest/1761/submission/181809468
My solutions (video):
A. Two Permutations
If $$$n - a - b \le 1$$$, then you can see that $$$p=q$$$, because either there is one element not in the common prefix or suffix, making the position of that element forced, or the common prefix and suffix intervals are touching/overlapping, so check if
Unable to parse markup [type=CF_MATHJAX]
. Otherwise, $$$n - a - b \ge 2$$$, and you can take $$$q = p_1, ..., p_a, p_{n-b}, ..., p_{a+1}, p_{n-b+1}, ... p_n$$$, so the answer is "Yes."B. Elimination of a Ring
If there is $$$1$$$ distinct element, then $$$n=1$$$ so the answer is $$$1$$$.
If there are $$$2$$$ distinct elements, they alternate between two elements, and two elements are deleted each operation no matter what, except for the last two operations, where one element is deleted each time, so the maximum number of operations is $$$n/2+1$$$ ($$$n$$$ will be even).
If there are $$$\ge3$$$ distinct elements, the main idea is to make it so that there is a unique element in the ring. Then you can just delete elements next to the unique element one at a time. So assume the frequency of each element is at least two. There will be two equal elements on the ring with distance at least $$$3$$$ apart, going clockwise or counter-clockwise. Take one of those elements $$$x$$$. If its two neighbors are different, delete $$$x$$$. Otherwise, delete one of its neighbors, then you are guaranteed able to delete $$$x$$$. Repeat the process until $$$x$$$ is unique, and then we can do as stated before. The answer is $$$n$$$.
C. Set Construction
If $$$A_i$$$ is a subset of $$$A_j$$$ make a directed edge from $$$j$$$ to $$$i$$$. Then, run a depth-first search algorithm on all the nodes $$$u$$$ with no parents. Let $$$x$$$ be the smallest number not used yet, (this is guaranteed to be $$$\le n$$$, since there are $$$n$$$ nodes). Let $$$N$$$ be the set of all the neighbors of $$$u$$$. Then you can set $$$A_u=(\bigcup_{v \in N} A_v)\cup x$$$. $$$A_u$$$ is guaranteed to not be a subset of anything we don't want because of $$$x$$$.
D. Carry Bit
Consider all blocks of carry bits and non-carry bits. Loop over $$$i$$$, the number of carry bit blocks.
If a carry bit comes right before a non-carry bit, there is only one way. If a carry bit comes right before another carry bit, there are three ways.
If a non-carry bit comes right before a carry bit, there is only one way. If a non-carry bit comes right before another non-carry bit, there are three ways.
So you can go through each of the four cases, whether it starts/ends with a carry bit or non-carry bit, and calculate the number of ways in that case, using the stars and bars formula. Special cases need to be handled for $$$k=0$$$ and $$$i=1$$$.
\begin{array}{|c|c|c|c|c|} \hline \text{First block} & \text{Last block} & \text{Ways to put carry blocks} & \text{Ways to put non-carry blocks} & \text{Ways to set bits} \cr \hline \text{Carry} & \text{Carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{(i-1)-1} & 3^{n-i-(i-1)}\cr \hline \text{Carry} & \text{Non-carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{i-1} & 3^{n-i-(i-1)} \cr \hline \text{Non-carry} & \text{Carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{i-1} & 3^{n-i-i} \cr \hline \text{Non-carry} & \text{Non-carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{(i+1)-1} & 3^{n-i-i} \cr \hline \end{array}
Sir,please check MY CONTEST CODE OF C of PROBLEM C , i am applying the same APPROACH as you but got wrong on test 2 UNABLE TO FIND OUT WHAT IS WRONG IN MY CODE SINCE YESTERDAY
Trash problem E, if use
cin
orscanf("%1d",&x)
will get TLE.Meaningless.Try C++20. It's faster.
btw after the contest, plenty of my classmates were complaining about this meaningless TLE in problem E.
Extremely thankful for this. Skill issue? maybe :(
Nice round, i like b, d, e!
although im still annoyed at myself for accidentally printing n^3 on the k=0 case instead of 3^n LOL
its worse when the one sample with k=0 had n=3 XD
(
Hey Everyone , This is My Code for C ,but i got wrong on test 2 but don't know why?
my approach is :) - i am applying DFS in PROBLEM C assume like directed tree
- i is subset of j then we can say that j is ancestor of i - we got a adjacency list from given matrix
then we set of parent = set of parent + set of its all sons please go through my code ,
please give any counter cases where the code is falling , is there anything i missed?
Take a look at Ticket 16477 from CF Stress for a counter example.
I deeply love this contest. But the data in problem B is a little bit weak.
My program passed the final test but it uses the wrong initialization.
TLE with std::cin for std::string in problem E is sad. :( I usually use scanf/printf for everything except strings, but here is an example where it may screw you, so you either should use char* with scanf or ios_base::sync_with_stdio(0) and your lovely cin/cout...
It would be nice to finally fix language selector issue and remove excessive use of flags.
Sources with supporting arguments:
Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.
Please support the initiative and stop reinforcing poor UX practices.
I really enjoyed this one, I'm a big fan of dX!! Although I didn't play this game, I like E and D very much. Personally, I think the difficulty of E is much less than that of D. It may also be my math problem.
I have been wrongly accused of copying the code. Both the codes are quite different and any similarity is just a coincidence. I use codechef ide for writing programs which is not public and hence the question of copying the codes cannot arise. I request you to not to mark my submissions for these two questions as invalid. I don't copy code and compete with full honesty.
This is regarding these two messages I received:
Attention!
Your solution 181793513 for the problem 1761C significantly coincides with solutions Nighthe/181764653, suryansh_2003/181793513. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Attention!
Your solution 181762172 for the problem 1761B significantly coincides with solutions Nighthe/181756764, suryansh_2003/181762172. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Interesting how both your codes coincides with the same person (Nighthe).
Congratulations to hoodie winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.
Suprise!