내가 돌아왔다! (Hello, Codeforces!)
I am thrilled to introduce you to Codeforces Round #633. Followings are basic information:
- This contest will take place on Apr/12/2020 17:05 (Moscow time).
- The round is rated for all participants who can understand this announcement. There will be two divisions.
- There are 5 problems in each division and you will have 2 hours to solve it.
- Score distribution will be announced later.
Followings are contributors:
- Authors: McDic (All Div.2 problems and Div.1 D), tzuyu_chou (Div.1 E)
- Coordinator: antontrygubO_o
- Testers:
- Phase 1 (When this round was supposed to be Div.2): dorijanlendvaj, SoulTch, pajenegod, AryaPawn, Rahul, mcdx9524, 300iq, Nemo, tfg
- Phase 2 (Before we knew that old Div1D can be easily googled): Um_nik, Sexpert, benson1029, khulegu, Sad_reacts_only, TselmegKh
- Phase 3 (Before few days to the round): mohammedehab2002, Kuroni, xuanquang1999, Maripium, enoone
- CF Admins: Thanks to MikeMirzayanov and his team for maintaining Codeforces and Polygon. I would like to say same sentence again as I said in my last round's announcement. Polygon is super great platform to prepare sports programming contest.
Followings are some fun things:
- antontrygubO_o is the most intense coordinator I have ever met. He rejected lots of my problems. Some example of rejection comments are below:
- This problem is too standard.
- Don't ask people about theorem and formula.
- This problem is appeared in recent ptz camp with higher constraints.
- I don't like it.
- Rock Scissor Paper makes statement messy, because some people don't know about it.
- D2A should be easier than this one.
- I've found generalized version of this problem in POI.
- Isn't this obvious?
- Your proof is wrong.
- This problem is not very interesting.
- This is too (censored).
- After lots of rejections, I tried my best to make problems to be interesting. I hope you like at least some of my problems.
- This round was originally supposed to be rated for Div.2 only. However, after we completed Phase 1 testing, we found that my round is too hard for Div.2, so we added more problems and made this round to be Div.1.
- In this round, statements will be even shorter than last contest.
- Even for some of problems which my coordinator approved, there were critical issues that made problems to be excluded. I will introduce some of my rejected problems which won't be used anymore in another post, after this contest ends.
I hope everyone can enjoy my third contest. Thanks in advance!
Followings are updates:
- Score Distribution:
- Div.1: 500 1000 1500 2000 2750
- Div.2: 500 750 1250 1750 2250
- I am sorry for such Div2C/Div1A statement issue. We fixed that immediately after few minutes to the round, but we should have announced it.
- Editorial is posted: https://codeforces.com/blog/entry/75913
- I opened new mashup for excluded problems. These problems are originally approved by antontrygubO_o but excluded for some reasons.
- Binomial Determinant is old Div1D. We found this problem on google so we removed this.
- Divisible Xor is old Div1A. But since we made 3 xor problems, we removed this one.
Followings are winners:
<Div.1>
<Div.2>
In this round, statements will be even shorter than last contest.
I hope we will enjoy the problems. Thanks.
Only contest can keep us busy during this quarantine .:)
Another rated round?
hope the statements will be as short as the announcement
WOW! Statements will be short let's see :)
Is It Rated?
The round is rated for all participants who can understand this announcement.
Don't you see it !!
Can I decide after the contest if I understand the announcement? xD xD
so the round is going to be tough a bit , we are ready to face it and enjoy according to question haha.
Are McDic and dick related?
No
Yes
What is a dick???
(CENSORED)
Basically a jerk
McDic is an Irish dick based in Korea.
YES
A full trilogy of horror movie starts with this sentence...
Kind of reminds you of this
who can understand this announcement
The task conditions will only be in English?
ah, no, there will be Russian statements available too.
10 April to 15 April. There are 4 contests where I can participate. (Educational round 85,div2,div3,div2 again). Wow! Thanks to the authors who worked so hard to make our quarantine life happy. Thanks to codeforces too!
Unless if you get a rating increment after div 2 rounds such that you are no longer in div 3 :)
Be prepared for the interesting behind story of every problem :)
Just saw the contests page!! I literally got chills seeing the list of upcoming contests!! Thank you MikeMirzayanov as well as all the other writers for the upcoming contests!!
Looking forward to McDic x Twice round!
This Problem is too (censored) xD.
i hope we will enjoy this round
Everyone, Look out for the unusual start time
antontrygubO_o X McDic
https://codeforces.com/blog/entry/70141
.
is there a hacking phase after this round?And can Div3 people write it ?
Hacking phase is generally for educational rounds and Div.3 rounds as this a classic Div.1 and Div.2 round there's no hacking phase and if a hacking phase is there it would be mentioned in the announcement and yes anyone who has rating below 1900 can give Div.2 round.
EDIT: Since you seem new, people can hack each other's solution, if they're in the same room(all registrants are divided into rooms), during the contest. But after the contest there's no hacking phase.
In this round, statements will be even shorter than last contest.
And I instantly love it!
when the editorials will be published i am curious to see the editorials....Thanks in advance to the problem setters who have setted the problem so good and interesting..
Thanks to the whole team, I don't know what I'd be doing in these quarantine days if you were not there making these amazing problems!!!
Omg it's McDic round
McDic orz
(Pls don't troll me again)
I bombed my last round so I hope I can do well on this one.
Please Make strong test case ... And thanks CF for making more contest in our bad time to increase our ability..
Hope pretests are strong !!
In this round, statements will be even shorter than last contest
Hopefully longer than April fools contest.
mcdicorz
(censored)
Sauce?
was coding but going to washroom now.
"(censored)"
Perhaps you can create a Gym with the rejected problems. :)
McDic orz! Even though you were assigned such a ruthless coordinator you kept on creating problems and came up with this geniosity round. McDic is so good I wish I had 1/x where x>1e9 of McDic's problemsetting skill.
I really liked this blog and I am very excited to participate in your round after reading it!
Is it true that tzuyu_chou is the real Tzuyu Chou from Twice?)
no
Yes
Dude don't know whether you are joking or saying the truth.But I will be honest I have seen this profile and I am awestruck how fast he/she improved from the first code he/she submitted like within 2 months to international grandmaster and I wish I can have that level of motivation and dedication in this time of quarantine. Thanks tzuyu_chou for motivating me...
Whether tzuyu_chou is the singer from Twice or not, it's pretty clear that they were already highly skilled when "their first code was submitted". So it's not some 2 month newbie->IGM miracle story.
You are underestimating Tzuyu's skill. If she can sing as well as she does in Twice music, surely she has the talent to go newbie->IGM that quickly ;).
Loved the rejection comments part
I hope it will be easy so that I can enjoy the problems.
"statements will be even shorter than last contest", if so than it will be really good for everyone I hope. Cz, long statement is so boring...
hmm
isItrated
Wow, interesting "Fun" statistics! We are equally thrilled to take part in the contest :D
Haha, long queue again.
Very interesting blog! Good coordinators help organize high-quality rounds in Codeforces and I am grateful.
Hope that codeforces won't shut down tomorrow :)
hey no one has yet asked whether this contest is rated or not?? P.S — i know it is ! But some people still ask the question ;)
Well, how about a separate section for memes in code forces?
Your proof is wrong.
Well this doesn't sound like a very unreasonable explanation for rejecting a problem..
For the first time I am seeing someone coming with score distribution this early.
waiting for formula and theorem forces...
Is tzuyu_chou going to perform a private live concert for the winner of this contest (of course after coronavirus ends)?
Unfortunately, she already did it for organizers and testers of the round.
That would be the most serious I've ever been in a contest...
As some people strongly requested, I post one of archived funny conversations here:
That's just sad :(
He didn't even give you hope that all your problems are great :(
Is antontrygubO_o a weeb?
I heard he isn't
Everyone's a weeb deep in their heart.
honestly, this is trash even for a white coder sorry.
If your answer was 1, he would said "I accept 1 of your problems".
Lmao
Short statements, 5 questions. Quality will be epic! Looking forward to participating.
Is iterated?
who is nupur XDXD
it is pointer!
fan ei ae yo
After we completed Phase 1 testing, we found that my round is too hard for Div.2...
Good Luck everyone
Back to back rated contest , I am enjoying it and after knowing questions are going to be shorter as compared to usual ones ,felling more excited.
5 problems in 2 hours?? "In this round, statements will be even shorter than last contest.", i hope it would make the contest interesting.
Just look at the number of upvotes for the announcement of the contest. It is way more than average.
Lots of contest in this week ...
I am registered in Div1 and Div2 bcz of my recent rating change XD. What happens now?
I think you will be moved automatically, I'm in a similar situation.
Participate in Div1. If predictor says -ve delta just resubmit them in div2 to compensate.
(looks at 1329C - Drazil Likes Heap) That's not so impressive.
I'm sure he meant "his last contest".
Fair 'nuff.
I'm ready for the contest. Good luck and high rating !
how many questions do u need to solve to hit specialist??...in a DIV 2 contest I AM DESPERATE!!!!!!!!!
It's an ELO System, so it depends on how the others perform. To be honest, it will probably be enough to solve just one problem (or maybe 0), since the base rating is 1500.
Gulag: It's time to earn your freedom
A long queue in submissions right now. Server was down yesterday. I hope it doesn't happen in the contest.
how many questions would a pupil need to solve in a regular DIV 2 contest to hit specialist???
Either 2 problems very fast or 3 problems during contest.
2 and quick enough!
I think it is ok to take 30 minutes to solve two problems.
tourist doesn't register the contest yet ?
Will there be contest today considering the server problem?
McDic [user:MikeMirzaynov] I do not know if this is happening only with me, the submission takes a lot of time to get checked since past few days. I request you to make sure that the same does not happen when contest is running. Thanks, Kushal Shah.
good
233E - Doe Graphs
I would be more worried about the opposite thing — in such situations people sometimes want to prove that they can prepare really hard problems and eventually round becomes too difficult.
Don't forget he is the author of 3400 rated problem.
hope that the round does not turn out to be unbalanced, 5 problem contests are unbalanced more often than not :(
juicy round :)))
(MikeMirzayanov) Is it just me, or m3.codeforces.com is not working? (403 Forbidden, nginx/1.16.1)
m1, m2, and the main site are okay, though.
I predict Div2C will be a math problem and Div2D will be a graph problem.
366B - Dima and To-do List
OMG.
Can you predict Div1C and Div1D of the next round? It would be very useful to me :D
I will predict for you but first show me da money.
I hope I become specialist in this round. And expert sometime sooner.. :)
i need help. i understand the question but i fail to implement the logic and my code are never optimized.. please any suggestion.
All the best guys !!!
Hey, for some reason my registration did not work, I cannot submit!!!
:/
Speedforces
Please stop creating problems.
I accidentally upvoted this one :(
I accidentally downvoted you :)
Thor is reading F just after D.
Fill in the Blank? XOR
Statements are short, but damn are my ideas wrong.
Same feeling. I did the contest badly ;-;
ridin ba in contestaye shokhmitoon
Your problems are excellent, but please consider the difficulty distribution of the problems. I think "After Solving ABC" might appear in one of the comments after the contest.
If that's the case, then there's no solution. Contests are not meant to be solved fully by everyone smh
I hope I won't see soon more "guessing pattern shit" problems like today $$$C$$$. Other problems were nice and interesting for solving.
When the first place becomes two
Really disliked problem Div1 C. Somewhat disliked Div1 D but I haven't seen the solution yet so I am giving it the benefit of the doubt. The former was just bad, though.
Can you explain why? I think both were fine.
The simplest way to solve Div1 C is to write a bruteforce and find a pattern. This doesn't require any CS-related skills and often feels like a maths competition.
Div1 D probably boils down to some DP on a tree, and I don't mind it, but it's just not pleasant to try and figure it out in terms of these loops. It feels like it's a really straightforward solution hidden by a really unpleasant abstraction.
I think D is a really nice problem. C is not something spectacular, but I think it is refreshing to see some "code and see pattern" problem from time to time and I don't think they are fundamentally wrong.
Wtf was pretest 3 of C?
Not sure but i think it was like
9
7 6 8 7 6 8 7 6 8
What should the result be?
2
9 is size
so you can make 8 8 8 8 8 8 8 8 8
Ah shit!
RIP my rating, never deserved it anyways
Please, can you explain it why is ans= 2?
for x=1 you can make 7 6 8 8 6 8 8 6 8 from original array.
for x=2 you can make 7 8 8 8 8 8 8 8 8
gg
Tourist is back to the top.
Can someone explain why 1D was not maximal independent set on a tree? :(
Look at the sequence of bands $$$b_1, b_2, \dots, b_k$$$ that form an answer. For each vertex $$$v$$$, if $$$v$$$ is adjacent to $$$b_l$$$ and $$$b_r$$$, it must be adjacent to each $$$b_i$$$ for $$$l \leq i \leq r$$$
how to do Div2.C/Div1.E?
exchange 1 with 2.
Brute force a bunch of values and observe the pattern for all the $$$a$$$, $$$b$$$, and $$$c$$$ values separately, assuming you're talking about Div2E/Div1C.
What's the pattern? jef
The bits of the middle col go like
00 10 11 01
and the right col like00 11 01 10
And what pattern is?
I found that indices 3i forms 1, 4-7, 16-31, 64-127, and so on. But indices 3i + 1 not lies in any pattern I can assume). Indices 3i + 2 is just 3i ^ (3i + 1).
I didn't have time to figure it out completely, but the $$$b$$$ values in binary looks like this:
The bit at index $$$i$$$ has a period of $$$2^{i+2}$$$ for even $$$i$$$ and $$$2^{i+1}$$$ for odd $$$i$$$, after the first few values.
Thanks
If you print $$$a, 2 a - b$$$, you get a pattern in blocks of $$$4^i$$$.
And blocks of $$$4^i$$$ can be seen as a repetition of smaller blocks of size $$$4^{i-1}$$$.
Thanks, finally saw it
How to solve Div2 B and C?
B. just sort the array and pick "last-first", "2nd last- 2nd"....done.
C. find index 0<=i<j<n such that arr[i]>arr[j]. find Max= (arr[i]-arr[j]) over all such pair using prefix_max and then find least (k+1) s.t. 2^0+2^1+....+2^k>=Max. done!
Div2 B: Sort the array. alternatively, put the last and first element to the end of resultant array.
Div2 C: create a auxiliary lmax[], lmax[i]: max ele upto ith ele from beginning of the array. let cur[i]=lmax[i]-arr[i], res = OR of all cur[i], output the log2(res)
Could you elucidate Div2 C, please?
Notice that any integer can be formed by summations of powers of 2 (e.g. 0b1101 is just sum of 2^0 + 2^2 + 2^3 and so on) so you just have to find the max drop(i.e. max diff a[i] — a[j] where i < j). If max diff <= 0 then you already have a non-decreasing array so your done. If it's greater than zero, than just find the smallest x where 2^x — 1 >= max diff and you are done.
See Here . I hope it helps
endless XOR……
How to solve div2 D?
Video tutorial for div2C/div1A
is DIV 2 B tough or what??
Nope simple! just sort the array and pick "last-first", "2nd last- 2nd"....similarly...done.
thx man..sometimes the most obvious is the most elusive...:)
I've never seen a better/prettier Problem A. Great Job!!
How to solve? Was the answer just n?
Yes
Once you set a vertical diamond, observe that you are forced to use horizontal diamond in other places. Lets say n=3 then we will have VHH. HVH amd HHV where V is vertical and H is horizontal diamond. That's why answer is n.
Yeah and by just checking how to cover the top left triangle, you get the recurrence F(n) = 1 + F(n-1) along with F(1) = 1
Which means the answer is simply n
For Div2.C
76384708 — used log2() to find the most significant set bit. WA on pretest 3.
76387989 — Removed log2() and wrote a loop. Pretest Passed.
Why?
Floating precision errors, maybe? It's good practice to always avoid using floating point operations unless absolutely necessary.
log2
is a floating point function, so it's imprecise.Is there any other function which can be used to find the most significant set bit of a number?
31 - __builtin_clz(x)
__lg(x)
I prefer
__builtin_clz
because it's actually documented and meant to be used by programmers.I'm sorry but that sounds like a really dumb reason to not use what has been provided.
I ran a loop from j=0 to j=31 and checked if 2^j>number (where ^ here is power). It's not an O(1) thing but it's log(10^9) and doesn't increase the overall complexity by much.
You should type cast log2, otherwise, there can be overflow on converting double to long long
language precision problem —
4.0000000 can be 3.999999999
you either took floor of log or ceiling.
If floor then floor of log(5) is 2 while the most significant bit is the third.
If you took ceiling then ceil of log(8) is 3 while the most significant bit is the fourth.
same happened to me I just put (int) before log2
Same problem with me too. Loop is working
>tfw probably finished coding D minutes after the end
My idea for div1D: for a sequence of vertices on a path, get (sum of their degrees) — (number of adjacent pairs at distance 2) — 2 * (number of pairs at distance 1). The answer is the maximum of this value, simple DP.
UPD: Also minus (number of adjacent pairs at distance 3).
Sorry if I'm missing something simple, but what does it mean to be an adjacent pair at distance 2? Doesn't adjacent imply that they are at distance 1?
Adjacent in the sequence of vertices I mention — such that the vertex between them isn't in the sequence.
What an amazing contest ! Each of the problems required good thought (except maybe C). This is not the first time McDic held back some problems while setting up a contest. I look forward to hearing the remaining problems which were not published as part of this contest !
Also, can someone please share the solution for Div 2 $$$E$$$ or Div 1 $$$C$$$ ?
Brute force, print in binary, and find the pattern.
IT's a greedy solution.
you will observer that first element of triplet is all elements of even power of two, 1,-,-,4,-,-,5,-,-,6-,-,7,-,-,16,-,-...
after this you can get n lies in which triplet.
convert 1st element into binary,
subdivide binary string to set of 2 elements and replace {'11':['01', '10'], '10':['11', '01'], '01':['10', '11'], '00':['00', '00']}.
you will get what to append at 2nd and 3rd element.
and [1st, 2nd, 3rd][n%3] is your answer
my sol — 76392709
its the first time ever i got the write logic for div 2 E i m literally so fukin happy ...
Can some one suggest me some similar problems with today's div2 a, b? I didn't understand a correctly and couldn't solve b..It will be helpful. Thank you.
Never seen a task similar to
B
. I have first set constraints of what are the possible solutions to the problem and then started juggling with different ways to traverse an array. The first intuition that I got was that probably we need to sort an array (but I wasn't sure about that). Usually, when you set some structure, that simplifies your task (whatever that task is). If you just go through indices from 0 to n or in reversed order from n to 0 in a sorted array that doesn't solve the problem. I started thinking of what is breaking when you simply traverse array in a sorted order. The next thing I tried in my mind is to traverse from some other starting point from a[i] to a[n]. That also failed. Then I thought if I have set first two elements in a sequence a[i], a[i + 1] what should the third element be in order to guarantee an increasing sequence? a[i], a[i + 1], a[x???].After that, somehow my brain had aha moment and came up with a sequence a[i], a[i + 1], a[i — 1], a[i + 2], a[i — 2], ....
What is about? What does the problem even meant by "2 coverings are different if some 2 triangles are covered by the same diamond shape in one of them and by different diamond shapes in the other one."?
Oh, I also didn't understand that description and simply ignored it. I just went straight to example at the bottom and worked through it myself. Then I interpolated the example with
n = 2
ton = 3
and started thinking hard about the case whenn = 3
.D is another stupid tree dp. It seems antontrygubO_o wasn't harsh enough.
I feel like this is a case when novelty of the setting justifies a somewhat standard solution.
For me, "new but has a simple standard solution once you figure out a basic condition" isn't good enough for div1D. It depends on the condition and if it is what I mentioned above, that's at most div1C level.
aid's concern seems to be not with the difficulty, but the problem itself. Anyway, judging by the standings it doesn't seem that poorly placed after all.
Well, his comments starts with "D is", so the fact that it's D should be relevant.
We can't compare difficulties by number of solutions alone. Most people solve A-E, so the letter and difficulties of previous problems matter. Most people will be intimidated by the fact that it's D with a geometrical statement — I know I almost was. If it was B, it would've definitely had more solutions.
How else does one refer to a problem?
If you have in mind some other requirements for a problem to be suitable, say, for a div1D, I'm curious to listen. It seems to me that a lot of people expect something along the lines of "$$$\geq x$$$ lines of code/$$$y$$$ sheets of formulas", but there are so many more interesting ways to give a good challenge.
Would "A is another stupid tree DP" sound exactly the same?
X lines of code / y sheets of formulas would be just as bad, since it would still be "spot this standard thing and type fast". For me, the requirement for any problem is that the solution is sufficiently unique for people at its level. Some variation in this is okay, but such problems are still disappointing for me.
I actually guessed the pattern directly from example case 2, but proved that it makes sense just in case. That's how straightforward solving it was.
I would've swapped C and D just because of this. C wasn't that hard either but it would've probably been an interesting D for more high reds.
Luckily we're not there yet for such comments to appear. =) Anyway, I didn't mean to say I knew exactly what aid was thinking.
Totally second this, but isn't reducing the setting to familiar terms a crucial part of the solution? AtCoder problems are a great example of this, when it's smooth sailing after one good observation, but it can take ages to make.
On a different point, with problems like this perceived difficulty can vary a lot. We can agree that the solution is simple, but there are lots of high-rated people who didn't solve it with an hour to go.
My take is that the problems like this are just not commonplace, outside of the current meta. This makes discussions about "good position" and "people with high enough rating" moot since none of these correlate well enough with ability to solve such problems. I, for one, would be happy to see such problems appear more often, but that's a matter of taste, of course.
Yeah, Atcoder problems are a good measuring stick here. I can think of two that fit the "spot simple solution" mold, but have their own twists on it:
A twist like that is what I'm missing in this div1D. It's okay to have such problems, they're just not very interesting to me.
As for difficulty, if we're really going by the number of solutions, the previous D had 21 solutions in-contest and it wasn't particularly difficult, just harder to implement if you didn't have the right tools (see my solution where I just pasted my treap). The previous D in a 5-problem div1 round (618) had 28. This one had 92.
Huh, I think that understanding the setting and what the answer looks like is the main part of the problem and quite a lot of thinking. Dp is indeed extremely easy, but what's wrong with that?
Well, to me this part was just looking at the picture for the first sample carefully, so I didn't find it interesting.
All LGM testers failed to figure this for a hour.
You shouldn't judge testing by the standings alone. You didn't talk with me and I don't know what antontrygubO_o told you, but I think that total time I spend on this problem is less than one hour.
It doesn't mean I think that the problem is easy, or bad, or unsuitable for div1D position. I think it is on better side of this round.
Dp alone is of course not fascinating, but I find the understanding of the structure in this proble quite amusing (which is of course main part of the solution) and I really liked it.
My approach to solving that problem was ignoring the geometrical structure as much as possible... I guessed what to do from the sample explanation and kinda-proved that it makes sense. Basically: ok, so we want a sequence of paths with length $$$\ge 2$$$ where we can always backtrack at most 1 edge from the previous path, what happens if we backtrack more?
Another comment: job of coordinator shouldn't be to reject problems that aren't amazing, it's to reject problems that are unsuitable or obviously bad. Otherwise the bar for problems will be too high.
I just read the blog and saw these phrases:
So I had high expectations.
I disagree with this; you don't want your contests to be "solve this query on tree problem for the 13245th time with minor modifications"; that's boring to everyone involved and then the standings are just a measure of how fast you can implement tedious standard problems.
rng_58 takes the stance of not setting a contest with problems he doesn't like, and everyone not named Radewoosh seems to appreciate his coordination job a lot (both in old topcoder rounds and recent atcoder ones).
It is April and AtCoder has had how many Div1 contests this year? If I count correctly, one?
EDIT: response to below: that's partly byproduct of differences in way contest are curated, if you consider how many quality problems are featured in Div1 CF vs Div1 AtCoder in last year, CF wins at least for me. (no new comment as it's not so useful conversation)
It has been 10 years and Codeforces has had how many comparable by quality contests?
You have a point, obviously, but the other side also has.
If you want more contests with problems between a very high bar and a relatively high bar, please try our ARCs (orange-circled contests). I think they are enjoyable for reds, and sometimes not too easy to solve everything.
Of course, I'm well aware that the number of contests is not so large even if we count ARCs. I'm sorry for that — we ran out of good ideas, and I feel it's time to change the generation. So, now I'm trying to share my experience with writers and maroonrk, and next year he will give fresh ideas. I hope the situation will get better then.
Would this work in E?
First notice that for any node D, the edges induce a total order of the nodes that have edges towards D. That is due to that special property. Next, notice that any graph has at least one node with in-degree over N / 2. Choose the one with the highest degree and attempt some sort of centroid decomposition: divide the nodes in 2 halves based on whether they point towards D (set A) or D points to them (set B). The ones that point to D form a total order via above observation. There's plenty of complex case work for computing the min distances that are obtainable while using nodes from both sides. The main algorithm basically treats these cases and then recurses on B. By the choice of D, these are at most N / 2, so you have at most logN recursive calls on exponentially smaller subgraphs which amortizes to N^2. Also, note it's important in the casework part that you choose D to be the one with biggest indegree because this guarantees that all nodes in A, have at least one node in B they point to (if this wasn't so, then those nodes that are pointed to by D and all of B have a higher indegree so would've been a better choice of D). Considering the cases it appears that all min-distances will be either undefined (so 614N) or at most 5. It may also be the case that you need to first recurse and then consider paths that go through both A and B.
It's pretty easy to show that the min distance is at most 3 or it is undefined.
Suppose that the min-length path from $$$a$$$ to $$$e$$$ is $$$a\to b\to c\to d\to e$$$. Then $$$a,c,d,e$$$ will form the forbidden subgraph.
EDIT: Fixed.
$$$a, c, d, e$$$, not $$$b, c, d, e$$$
.
XorForces
Div1C is the most beautiful problem I ever solved)
UPD. OK, some people don't like 000/123/231/312 pattern
Can you explain it?
Let's notice that $$$4^n - 4^m$$$ is divisble by $$$3$$$. We can group numbers from $$$1$$$ to $$$4^{n-1}$$$ into triples.
If {$$$a, b, c$$$} is the lexicographically smallest triple where $$$a \geq 4^k$$$ then {$$$4 * a, 4 * b, 4 * c$$$} is the lexicographically smallest triple where $$$a \geq 4^{k+1}$$$.
How to find next triple after {$$$4 * a, 4 * b, 4 * c$$$}? We know that $$$(4*a) \oplus (4*b) \oplus (4*c) = 0$$$ and last two bits $$$4*a$$$ are $$$0$$$.
It means that {$$$4*a+1, 4*b+2, 4*c+3$$$} is the next triple (after it {$$$4*a+2, 4*b+3, 4*c+1$$$} and {$$$4*a+3, 4*b+1, 4*c+2$$$})
$$$x = ((k+2)$$$ % $$$4$$$)
So if we want to find $$$k$$$-th triple {$$$a1, b1, c1$$$}, we can find $$$(k+2)/4$$$ triple {$$$a, b, c$$$}, multiply it by 4 (because $$$a = a1 / 4$$$, it can be proved) and add {$$$0, 0, 0$$$} (if $$$x = 0$$$) or {$$$1, 2, 3$$$} ($$$x = 1$$$) or {$$$2, 3, 1$$$} ($$$x = 2$$$) or {$$$3, 1, 2$$$} ($$$x = 3$$$)
I have 1 hour to solve D but still didn't complete it. After discovering my first approach didn't work, i think it seems like using LCA. Hope next time :(
Did some very weird thing for div-2 D and somehow worked.
First, we find the lower bound. We claim that it's equal to 1 if all leaves are an even distance from each other (indeed, just set each value equal to each other and use the fact that aXORa =0). If any two leaves have an odd distance from each other, then the lower bound is 3 (but I don't know how to prove this -- it's probably some construction).
For the upper bound, we note that if we have a sequence between two leaves that have more than 2 edges, then we can set all the values on the path distinct. If there are only two edges, we need the values to be equal. Thus, in both cases, the upper bound is equal to n-1-k, where k is the number of pairs of leaves that are 2 edges apart.
Why is this weird? This just seems like the correct solution.
Maybe weird was too harsh -- it's just that I barely convinced myself that this worked during the contest. I took a leap of faith and it worked I guess.
Ah, the good old proof by AC. Helps for some contests but it's also useful to make sure you know the correct reasoning after the editorial comes out :)
for the upper bound why is possible to give all other edges different values?
For the upper bound, consider a case like
6 1 2 1 3 1 4 1 5 1 6
there are 5 leaves, all at a distance of 2 from each other
answer here is 1 1
Oh yeah sorry, k isn't the number of pairs. If a vertex has x children that are degree 1 and x>=2, then k+=x-1. We sum over all vertices.
for the upper bound why is possible to give all other edges different values?
.
I still don't understand what is said on D2A. I have never seen a complicated line like 3rd para in D2A
same here...
Div2-E was similar in statement like_this Div1-D but not in difficulty.
Basically, I am an author of both problems.
McDic Can you see my div2A submission record? My score is wrong?
Repeted submission will reduce your score by 50 points.
Okay, I feel very sad.
MikeMirzayanov My question A was submitted twice on the Internet, all pretest pass, the submission time of the two before and after are 10 and 11 minutes, but my score is 432, obviously 50 points less, I want to know why? These are my second submissions:633div2Athe first has been skiped
Successful resubmission will make previous submission as "failed submission" which costs you 50 points
Ok i just knew
MikeMirzayanov His two submission only differs by a new line at the end. I think this counts as repeated submission and maybe should be prevented?
The most pathetic contest I've ever seen. Now I know why they call you a dick.
Bruh whats so pathetic about logical questions? All of div2 A,B,C had barely any lines of code if you think.
I generally hate questions that are easier to solve but has heavy implementation like those with too many cases. This contest was honestly pretty amazing
Well written brief statements with nice diagrams and interesting problems!
The only thing that prevent me for 30 min to output just N in problem A was this 1e18 it's confusing Lol :"
It can be shown that under given constraints this number of ways doesn't exceed 1e18.
problem A kinda remained me of the Apirl's Fools day's problems when I found out the solution is simply output N.....
What is actually told in D2A? I understand nothing.
same here..
Basically it asks you to find the number of ways to fill up the shape the statement defines. For instance, when N = 2, we can only use one vertical diamond and two horizontal diamonds to shape that form, in this case we have 2 ways to do that. For other input N, there are N positions for diamonds to be vertical, but we can observe that if we make one diamond vertical, the rest can only be horizontal, so the answer is just the number of vertical positions which is N.
Hi setters,
I would like to be unrated this round for the following reasons. For the question div1 A, the statement was misleading before it was changed without any form of notice. The original statement had
Find the smallest number k such that you can make the array nondecreasing after at most k seconds.
. This was very misleading since the variablek
is also used to denote the number of indices chosen. This statement led me to think that you could only performk
operations at thek
th second. I had this version of the question until around 20 minutes left in the contest when I decided to reload the page. I feel like this heavily impacted my rating negatively, so I would like to request to be unrated. Thank you.Ok Boomer
I can't understand why some stupid announcements about obvious things clearly written in the statement are broadcasted pretty often, but changes in the statements are treated completely silently. I was once a victim of a silently changed faulty statements as well. antontrygubO_o any comment on this?
Now I agree that not to broadcast this was a huge mistake. The statement was corrected at the 3rd minute of the contest, and I couldn't see a way how problem could be understood in a wrong way (all our testers (of the last phase at least) didn't notice anything suspicious). So I decided that the broadcast wasn't necessary.
Of course, it's better to broadcast if there is even the slightest chance that someone might be affected, I'll do so in the future.
Sorry to everyone who was affected... But I don't see a way how we can make this unrated to those who were affected, unfortunately. I'll do my best to not let this happen again, huh
Does Codeforces not have the functionality to unrate individuals? Like most people, I joined the contest as soon as it started, and never refreshed the page (what reason would there normally be to do so). I believe changing the problem statement without notice is completely unfair, especially when the statement reuses the same variable for different purposes almost directly after each other.
There is no way we can check if someone was really affected by the issue or just doesn't want rating drop.
You have a point. Please make sure to broadcast changes to the statement in the future, especially when it is changed for clarity. If you cannot unrate this round, I do not believe it is a big deal since rating will correlate to the user's skill in the long run regardless. Anyways, thanks for noting the mistake. I will continue to look forward to future rounds.
you seem pretty smart lad. you will be up in your feet in no time. just look us poor wretched souls having a hard time..ha deary
Thanks man, I'm just extremely disappointed since I had higher expectations than -98, and I believe I could have done way better without the misleading statement :/
Good to know I wasn't the only one. I thought I might have interpreted the question incorrectly initially, didn't realize that the statement was corrected :|
Doesn't affect me a lot since anyway I didn't solve it. Had a bad day today.
no, you aren't the only one.
very bad problem C.
Did antontrygubO_o really think that Div1C was interesting?
Yes. He is one of the strongest pusher of Div1C.
That's really disappointing
McDic Are you trying to achieve komedy?
76395656 Can anyone explain for me, why I got WA on pretest 3 :(
Consider this test case
Check whether your solution satisfy the requirement.
The result for this test case is
2 4 1
and it still satisfies the conditionMy bad.
Try
Your solution should output
2 4 5 1
, which is wrong then.aaaa, i know where im wrong @@
My submission:
cout << arr[mid + 1 + i] << " " << arr[mid - i] << " ";
And just change possion:
cout << arr[mid - i] << " " << arr[mid + 1 + i] << " ";
and it ís accepted.
Tks you :(
One more reason to skip McDic rounds
Am I the only one who found div2A more difficult than B and C? I solved B in ~40 mins then stuck in A for the rest of the contest. Finally just guessed the answer and got AC. When I read C at the end, I was able to come with solution in ~20 minutes. Of course time was over. What the hell is wrong with me.
Same , i thought this can't be that hard but i moved on to B and C after doing them , came back to A and then did that. I had more than an hour for D , couldn't come up with a solution though
I am stuck in A as well.
Finally, I found that the answer is up to the number of the diamonds.
But when i noticed that the answer does not exceed 1e18 as stated in the problem, i dare not submit it...
I solved D2A like how April Fool problem were solved. Got nothing from statement. Looking for sequence on input output. Finally print n and got pretest passed.
Anyone else was confused in problem A because of this statement....? :/
Yea, I saw that and figured the output couldn't be more than 10^9. I went ahead and did B and went back to A and was trying to figure out combinations before realizing that it was just n.
IMO it was pretty misleading. TBF, the problem was 500 points, indicating an incredibly easy solution.
I was one of the people against this. lol
Maybe lost about 4-5 minutes for this line -_-
Thanks for the contest! Some notes:
Maybe we should set a limit on how many times XOR can be used in the problemset? (By the way, Russian statements for B and C probably should call it "XOR" and not bitwise exclusive OR, just for clarity)
Is there any good solution for C except printing the sequence and finding the pattern?
Probably output section in the statement should say what the output format is, not just say "Print the answer" – then we wouldn't need to reread the statement and check the samples for that.
Can you tell the pattern? I couldn't able to figure it out.