내가 돌아왔다! (Hello, Codeforces!)
I am thrilled to introduce you to Codeforces Round #633. Followings are basic information:
- This contest will take place on 12.04.2020 17:05 (Московское время).
- 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, Ari, benson1029, khulegu, Sad_reacts_only, TselmegKh
- Phase 3 (Before few days to the round): mohammedehab2002, Kuroni, xuanquang1999, JettyOller, 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
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 announcementThe 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.
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)
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 contestHopefully 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
Very interesting blog! Good coordinators help organize high-quality rounds in Codeforces and I am grateful.
Hope that codeforces won't shut down tomorrow :)
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.
If your answer was 1, he would said "I accept 1 of your problems".
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...
Just look at the number of upvotes for the announcement of the contest. It is way more than average.
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.
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.
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.
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.
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 :)
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 01and the right col like00 11 01 10And 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?
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.
log2is 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_clzbecause 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.
>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 = 2ton = 3and 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
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..
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 variablekis also used to denote the number of indices chosen. This statement led me to think that you could only performkoperations at thekth 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.
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 1and 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 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....? :/
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.
Print it in binary.
Div1
C: godforsaken pattern searching, dumb luck
D: provide some trivial constructs on 4d space to analyze
this is what happens when yo make a div2 round a div1 one
So that is why you just don't participate??
I think I don't need the examples and descriptions of problems!
Solving div1B (minimizing part) was extremely discouraging for me.
I got to the claim that the answer couldn't exceed 3. I spent 20 minutes proving this, and in the end, I was very proud of the proof I got.
After getting AC, I see that it 800 contestants had solved it. I got really disappointed, because I knew like 99% of them didn't prove anything. They just came up with the claim, prayed a hail mary, and submitted. This was very depressing because I really felt I performed well in that problem, but I was beaten by hundreds out of mere luck.
agree. the proof part is much harder (and more interesting) than the guessing part. However, proof part worth 0 points :(
If the problem had involved reconstructing the answer, I bet you anything the AC's would be half what they actually were.
yeah, this modification would make this task better. Though i don't know if it is doable for maximum case, as my construction is using some really big integers(like $$$2^{K}-1$$$ where $$$K$$$ is a large integer). but the construction of minimum case is really cool imo.
Why is this downvoted? I am in Div 2 and I spent one hour trying to find construction for the minimum case, tried sorting by preorder and looking for something, tried assigning 1 to everything and then "fixing" by changing leaf edges.
I could have just assumed something labeling with 1, 2, 3 will work and got AC. Can someone share core ideas of proof? I couldn't do it.
Pick a leaf as the root, DFS, keep the root-to-current-node prefix xor, try to keep it non-zero before you reach the leaf. When traversing through an edge, pick any number different from your current prefix xor so the new prefix xor is still non-zero. When you reach leaf, pick the number equivalent to your prefix xor.
Why would you come to that conclusion? You came up with the construction yourself, and probably half of the Div1 folks who solved B are rated higher than you.
I'm not saying rating is absolutely indicative of strength, but why are you underestimating everyone else?
My point is not related to skill. I was pretty sure the claim was correct the second it came to mind, out of "intuition". But I didn't submit because I don't like to send something I'm not sure about. Others (maybe more skilled than me) just didn't care, and went for proof by AC.
And you're right, reconstruction was not impossible and most people might have come up with it eventually, but they would've taken longer. Instead I just got more penalty than them for trying to be thorough.
Notice I'm not complaining. "I got really disappointed" were my exact words. I wanted to express my experience and see if anyone else felt the same way.
Come on, it's not so hard to prove compared to guessing. 3 seems so random to me, I would never be able to "guess" it just because it was in the samples or something. IMO you need some insight to the problem to understand where the 3 would come from. And the construction that always gets 3 is not that far from there anymore.
I am quite sure your claim with 99% is way off. I actually think it would be hard to get enough understanding of this problem to get it accepted but not being able to prove that answer does not exceed 3. But maybe I am missing something.
EDIT: Ah, ok. Distinguishing the case with f=1 is pretty obvious and if you keep your finger crossed that f is never two and doesn't exceed 3 you are good to go.
let the value of leaf be 0, and do black and while colorings for remaining vertices. (black=1, white=2). value for edges are the xor of corresponding vertices.
I agree. If anything I think finding the maximum is a bit more susceptible to proof by AC, but I don't think it's easy to guess that the minimum doesn't exceed 3 without more or less having an idea of how it should be done.
The proof consists of 3 steps
Observe the cases that 1 is not enough
Observe that 2 is also not enough for the case
Show that 3 is enough for this case
The third step is not that trivial, but it seems very likely that it's correct after you get 1 and 2. It's easy to prove, but it's even easier to guess without proving.
Why would you just guess "oh answer is not 1 or 2 so it must be 3"? It seems like total nonsense to me unless you have some sort of idea of how 3 can be achieved.
I have a and b, I notice that I might need a^b sometimes, I don't know if there's any corner cases which might cause some problems, but it's not unreasonable to guess that "it just works"
Edit: To clarify, I proved it. But before I proved it I already expected it to be correct.
Well, imo if you're already thinking that you should use a, b, a^b as weights you're not unreasonably far from a proof, but sure, if you disagree I see how this problem can feel "guessy".
The problem itself is interesting so I don't think being a little guessy makes the problem bad. I'm just saying this guy's point is not unreasonable, especially when speed matters a lot.
Still I'm happy with the fact that I proved it.
I thought about this for past several days. I am sorry about this.
I will force participants to make certain constructions in this kind of problems next time, so I can give much more advantages to who prove this.
Thank you.
I want to highlight that the problems were interesting and the contest was very nice. And I always appreciate the hard work problem setters do voluntarily for the community. My comment had the sole intention of sharing what I felt while participating. So absolutely no need to apologize.
I'm very impressed that even having done such a good round, you still take the time to think about how to improve even more. You're a clear example of what a great problem setter should be like.
Did everyone understood Div2A? I just made a guess of printing the input itself after trying to understand the question for more than 1 hr and was shocked too see it passed the pretests.
From what i got , a normal diamond(no rotation)can be fixed in n positions and if we fix that diamond , we are forced to use others , we can't vary any other positions. So a filling can have only 1 normal diamond . We can vary its position , from first to last giving us n
Am I the only one who solved Div2C using Binary search? After reading other solutions,mine seems like an overkill.
Div2A — There will always be exactly one vertical diamond. Therefore the answer is just n.
Div2B — Sort the array. Then the answer is a[1], a[n], a[2], a[n-1], a[3], a[n-2], and so on reversed.
Div2C/Div1A — Using our moves, let's change every number from a[x] to max(a[1], a[2], ... a[x]). The answer is then equal to the highest bit that is found in any of max(a[1], a[2], ... a[x]) — a[x].
Div2D/Div1B — If the parity of the depth of all leaves are equal, then the smallest value of f is 1; otherwise it is 3. To compute the maximum, observe that if two leaves have the same parent, the the values written on the edges associated with these two leaves must be equal. All other edges can have different values.
Div2E/Div1C — Write a brute-force solution which prints answers in base 4, and look for a pattern after grouping the output into triples.
I do not know yet how to solve Div1D and Div1E.
Can you please explain
If the parity of the depth of all leaves are equal, then the smallest value of f is 1; otherwise it is 3Well if there exists a path from one leaf to another leaf having odd length, the answer is 3 else it is 1.
How did you come up with this?
XOR-ing the same value an even number of times gives 0, so if there are only even length paths, you can give all edges the same weight and you are done.
For an odd path, for example of length 5 $$$a \oplus b \oplus c \oplus d \oplus e$$$, obviously a single value $$$x$$$ is not enough (because the xor sum will be $$$x \neq 0$$$). If you try to do it with 2 values, you'll split the odd length into an even length and an odd length (for example, you assign $$$a = b = c = x$$$ and $$$d = e = y$$$) and, as previously noted, add odd path cannot be done with a single value. Therefore, 2 is not possible either.
It is always possible with 3, by picking all but 2 values to be the same, for example $$$a = b = c = x$$$, then $$$d = y \neq x$$$, and finally $$$e = x \oplus y$$$.
there are many leafs how do i find distance between each pair or is there any smarter way?
That was a tricky part!
That's why the above guy talks about parity, the thing is that you needn't find distance between every pairs, but only from one leaf to all others, if this leaf has even distances from all other leaves, all pairs would have even distances (this is easy to see why).
Moreover, for the max part, if two leaves are at a distance of 2, then they would have same parent(a leaf has only one parent :). So you find out parents for all leaves and simply sort them and voila!
Hope it helps :)
ok, for the first part. just asking, did you figure it(even distance part) out during the contest or did you know that thing before the contest?
Sorry, I didn't get the sorting part. Why do we sort them? and you asked for finding the parent of all leaves(only leaves not other nodes) right?
Suppose, in my dfs function, I choose a leaf node as the parent node, then do i need to take it's parent too? I don't think so. What do you say?
Yeah, I did figure it out during the contest itself, that was simple because I couldn't do B and misunderstood C as well so all my time went on D :D.
You only want to know how many leaves have same parents. That is easiest to do in $$$O(n log n)$$$ by sorting and then comparing successive values.[We don't want $$$O(n^2)$$$ :]
A leaf can't be a parent of another leaf simply because n is atleast 3.
The last part that I was asking that I'm calling my dfs function with dfs(1) (I'm assuming 1 as the root of the tree) but this 1 can be a leaf node.
For eg — 1 2 2 3 3 4 2 5 5 6
So, I'm calling dfs as dfs(1)(considering 1 as the root of the tree), but 1 is leaf so technically 2 becomes the child(although not a leaf) but in doing this way I miss 1 as being a leaf. So, should I also take care of this thing too(that dfs for that node should be called which is not a leaf)?
A leaf is only adjacent to one vertex so that must be the parent, so you don't need to do a dfs :)
Can you please explain Div 2 C in detail? Thank you.
Just keep the track of maximum element traversing array from start,If the current element is smaller then the maximum than compute the power of 2 greater than or equal to the difference and keep track of such powers and output the maximum power among them. For reference- https://codeforces.com/contest/1339/submission/76379511
what will be the answer to the test case: 8 7 8 7
|8-7| = 1 (7 needs 1 to satisfy a1<=a2)
|8-8| = 0 (8 needs 0 since a2 will be 8)
|7-8| = 1 (7 needs 1 to satisfy a3<=a4)
max = 1 (taking max because ques asked for minimum time required)
log2(1) = 0 + 1 (+1 since 2^(x-1) where x>=1)
ans = 1 seconds
If max is odd, just use ceil(log2(max)) (seconds can't be in floating points)
if max is even, use log2(max)+1 (since 2^(x-1))
could be 8 8 8 8 thus on 1st second
in Div2D can you explain why for maximum we give all other edges can have different values?
There are infinitely many possible weights I can put on. Suppose, there is a leaf to leaf path where I have already put weights like... 2-3-5-1-x-6, now, you need to fix a value for x. to make 2^3^5^1^x^6 = 0, x should be 2^3^5^1^6^0 = 3. Now you see, I have already used 3, so what...now I decide that I'm not gonna use 3 there and change the value to maybe 10...which has not been used yet. So, now x shall be 2^10^5^1^6^0... I'm gonna use such a number for which I get a completely different value of x. This is possible as we can infinitely many options of weight.
I got it thanks bro so much
ok seems fine. what if some 2 leafs have distance = 2. Then we'll have to use the same edge weight.
Yeah... I omitted this part as its obvious...
Shouldn't the answer for B be the reversed order?
No. Try this case. 1 2 3 4 4 5 your answer --> 5 4 4 3 2 1--> difference= 1 0 1 1 1(Does not follow the condition)
No you misunderstood my idea. My answer would be 3 4 2 4 1 5.
Sorry, it has been fixed.
any reason that the edges associated with the 2 leaves must be equal?
Another round with zero solution-hacks! Missing those golden days when hacks used to be a key point in getting a good rank. Hoping for a round full of hacks in near future.:p
I hope it wont happens but having no solution-hacks is not acceptable.
Hi,
In the original problem statement for A, there were two
ks: the first one for the size of the set you choose, and the second one for the number of seconds you used. These two k's were the same (both lowercase) and nothing differentiated them. As a result of this issue, I was unable to solve A until they fixed the problem statement later in the contest (changed onektoT) and ended up with a lot of extra penalty due to this. There was also no announcement stating that this was changed. Would it be possible to unrate me?I'd also like to point out that I solved C before A, which should serve as some sort of evidence that I was affected by the statement :(
Thanks!
Thank you McDic and antontrygubO_o for making problems in such a way that minimizes checking time and making such nice problems for D2A-D2B-D2C, sadly D2E wasn't as good as expected, the problem was fine but not the gap, hope you will decrease thinkforces for your next rounds.
nice contest
Good round, great problems! But weak pretests on D. Test 31 is very short, but wasn't used in pretests...
When I solve B and C but unable to solve A
McDic tzuyu_chou Is it allowed?
Another one (Same Handle)
No.
What's wrong?
Unacceptable! but it's kind of hard to be detected.
Quarantine effect :3
Nothing to do at home? Create cf handles and hack yourself, get some points...stay newbie!
QUick Check tourist is gonna take the throne again.
tourist is back to 1 .woah.
Not yet.
For good or for worse the contest (at least div 2) is an implementation-light, mathy contest. I personally enjoyed it. Others may not have. But it's hard to deny that McDic, in his contest style and his detailed editorial, showed the spirit of a person who is truly passionate about the art of problem setting.
Where is the editorial
Editorial
Am i the only one who misunderstood the statement of problem C? The whole contest I believed that the indices should be consecutive xDDD.
I made like 4 wrong submissions before i realised lol
no you aren't the only one and it got me wrong on pretest 3(wasted almost one hour and 35 minutes on the same problem). The statement was very confusing and it's written in such a way that it leads people to believe that the indices are consecutive. If the statement was clear , I would have definitely tried maximum gap of power of two :-(
Oh My God. I was trying for the past 2 hours , wasted an hour in the contest, read the editorial.Then randomly started viewing the comments and now I realized that. Thanks Man!
This guy register another account for him to hack, check this out 76401969 and 76394268. That's not nice!
it was a second round with problem A harder then B+C for me... it isn't good(
****great contest i hope if every contest have this style****
Good statements, no bullshit
76379586 what is wrong with this? I lost so many points because i did not solve problem B and i don't know why...
I started with div2 C & got confused on statement because of k which is later changed with T. I lost 1 hour because of it and also got two wrong answer. Later I solved it in 19 minutes. That was a bad contest for me. I got so unlucky today. Hopefully i'll do better in future. BTW, great problems.
Everybody got confused I guess including me
Yeah, I didn’t even reload. But they are human too. They did great. It’s common to have some issues. They will do better for sure.
I have been wrongly accused of submission of similar code for Problem D.
Your solution 76385031 for the problem 1339D significantly coincides with solutions Kimur/76379805, overstart/76379879, Gaas/76379895, ChudiChudiTeriMaaChudi/76379984, abc090/76380479, genndq/76380572, tecca/76380750, c0d3mu/76380908, darshan___/76381314, bokunopico/76381382, driver425/76381996, Sardar_Ji/76382048, use_me/76382134, rustic_coder/76383553, teri_maa_ka1/76384665, amishbharti1999/76385031, robinsharma1599/76388701, xDxD/76388978, rmodi9942/76392243, asdfghjk123456/76395936, akshay_kumar646/76397440, sir_dawnblade/76398130, ppulkit2707/76399332, ashtechinc/76401095, ankush_3107/76401176, anupamsri/76402758 **** I don't code on any online compiler with public access. So I don't understand the Coincidence of any similarity with such a large no. of people. Admin please see to it since all my submissions for the contest has been skipped.
Did you take a look at the submissions by the users you mentioned? Do you find any similarities?
And also, I see that some of those submissions listed were made before 76385031.
2^30 = 1073741824 which is bigger than 1000000000 . so should be enough
sorry corrected the testcase ..plz tell now
2^0 + 2^1 + .. . 2^30 = 2^31 -1 which is bigger than 2*10^9
in 30 seconds we increase by 2^31 — 1
[deleted] Wrong blog
HELP!
Hi, everyone! My friends has some trouble in his solutions, He has submitted this solution 76367506 during the round, However, after the system pending test, He did not get an AC, but still the Pretest passed. The score for this problem was not added to my friends. He has submitted totally the same code just now, 76438866, and get an AC. Why did this happen? It has effected on my friends ratings, Where can I find the administor to solve the trouble? (sorry for my poor english)
MikeMirzayanov
Also pedromm reported me this. Can you please have a look? MikeMirzayanov
nice!
I solved B C but didn't get the meaning of A TAT, by the statics I know outputing the input directly...Could anyone explain it? Thanks!
When I click on the handle of sorry_dreamLolita from this blog's top rankers, why does it redirect to dreamLolita ? I'm not getting it.
One of the Best Contest I've ever had. :)
I see many people aren't satisfied with the pattern finding solutions of Div2D/Div1B and Div2E/Div1C. Here are some ideas:
Div2D/Div1B:
Let's give each vertex $$$u$$$ a value $$$f(u)$$$, having the property that weight of edge $$$u-v$$$ is equal to $$$f(u) \oplus f(v) $$$. Observe that fixing the values of $$$f$$$ for all vertices gives unique values of edge weights and for each way of fixing edge weights, we have some corresponding values of $$$f$$$ (Infact fixing all edge weights and $$$f(u)$$$ for a single vertex produces a unique graph).
This trick of converting edge weights to vertex weights and vice versa is quite useful in lot of tree problems.
Now, observe that $$$\text{xor}$$$ along all edges of any path from $$$u$$$ to $$$v$$$ is equal to $$$f(u) \oplus f(v)$$$. Thus, if we want $$$\text{xor}$$$ along path between any $$$2$$$ leaves to be $$$0$$$, then values of $$$f$$$ for all leaves must be same, let's set them equal to $$$0$$$. Now, we can give any value for all non-leaf vertices, so long as no $$$2$$$ adjacent vertices have the same value (as edge weight cannot be zero).
Now, it's not that hard to see that if we assign, say the value $$$2^i$$$ to the $$$i$$$th non-leaf vertex, then all edges between non-leaf vertices will be distinct. So, this way we can calculate answer for the max case. For the min case, we "color" the non-leaf vertex with $$$2$$$ colors. If only one of these colors is ever adjacent to a leaf, we can let the other color be equal to the color of the leaf vertex, thus, all edges will be of the same weight. Otherwise, all $$$3$$$ colors come in contact with each other, so we have to use $$$3$$$ different edge weights for each pair of colors.
Edit: Deleted Div2E/Div1C explanation because it eas wrong.
As I described in update 4, check some of excluded problems at here!! Thank you!
Too Easy Div_1 A if that was not excluded by coordinator.
Can anyone please help me figure out why my Python solution of Div 2 D gets a runtime error on test 6? I've even tried generating random trees and running my program on them and never got a runtime error. Been trying to fix it for the whole day :( You can look at submission 76578084, for example. I've determined that the error happens somewhere in
min_fmethod, but haven't figured out where.The problem was I was using a recursive algorithm to find all distances from root to leaves, and python cannot into many recursion layers. Rewrote it to use a while loop with a stack, and now it works.
Is it just me or this submission https://codeforces.com/contest/1339/submission/76360407 shows pretest passed as verdict?
Can we expand the 1D to the ordinary undirected graph？
Wow, I didn't seriously tried, but sounds hard problem.
Is this handle tzuyu_chou and this are/is the same people?