Thank you for participating in our round! We hope you enjoyed the problems.
2257A - Creating Abbreviations Idea: egorka5opka
Note that adding abbreviations to the set $$$S$$$ does not create any new possibilities for creating new abbreviations, because a word starting with that letter already exists. Therefore, for each of the 26 letters, we can remember that there is a word that begins with it, and then go through all the abbreviations and check each letter.
2257B - Gigantomachy Idea: egorka5opka
On each turn, the height at which the giant stands decreases by exactly $$$1$$$, except in cases where he changes mountains.
Thus, the first giant will lose after $$$((a_1 - a_2) + 1) + ((a_2 - a_3) + 1) + \dots + ((a_{n - 1} - a_n) + 1) + a_n = a_1 + n - 1$$$ moves.
Similarly, the second giant will lose after $$$b_1 + m - 1$$$ moves. All left is only to compare these two numbers.
Time complexity: $$$\mathcal{O}(n)$$$.
2257C - Spying on the Beaver Idea: egorka5opka
Suppose we have placed some cameras and remove the corresponding edges from the tree. If all the dams are now in different connected components, we can always uniquely determine where the Beaver went. Conversely, if there is a component containing two dams, we cannot distinguish between them.
Since the original graph is a tree, it is necessary and sufficient to remove $$$m-1$$$ edges.
If the root contains a dam, we can take the edges leading directly to all the other dams, obtaining a set of size $$$m-1$$$.
If the root does not contain a dam, we take the same edges but skip one of them. It is important that we cannot skip just any edge: we must choose a dam such that there are no other dams on the path from the root to it. We can take the dam with the smallest depth or vertex number. In this case, we do not even need to run a DFS.
Time complexity: $$$\mathcal{O}(n+m)$$$.
2257D - Bermuda Rectangle Idea: pskobx, oblememan, egorka5opka
Before processing the queries, let us perform some preprocessing. Find all pairs $$$(a, b)$$$ such that $$$a \cdot b = S$$$. There are $$$\mathcal{O}(\sqrt{S})$$$ such pairs, and they can also be found in $$$\mathcal{O}(\sqrt{S})$$$ time with standard algorithms.
These pairs are the top-right corners of all possible Bermuda rectangles. The union of these rectangles forms a staircase-like shape; let us call it $$$F$$$. The answer to a query is the area of the intersection of the query rectangle with $$$F$$$.
Sort the points by $$$x$$$, and for the point with index $$$i$$$, compute the value $$$P_i$$$, equal to the area of $$$F$$$ between $$$0$$$ and this $$$x_i$$$.
This information is enough to answer each query efficiently using binary search. We find the position where the boundary of $$$F$$$ crosses the horizontal side of the query rectangle and calculate the answer using the corresponding prefix areas. The exact formulas and case analysis may vary depending on the implementation.
A couple of remarks that may make implementation easier. If there is a point $$$(x, y)$$$, then there is also $$$(y, x)$$$, and since, knowing one coordinate, it is easy to compute the other. Therefore, it is enough to store just the sorted list of divisors of $$$S$$$ and treat them both as $$$x$$$ and as $$$y$$$.
Preprocessing complexity: $$$\mathcal{O}(\sqrt{S})$$$, time complexity per query: $$$\mathcal{O}(\log S)$$$.
2257E - Busy Beaver Idea: pskobx
The first step is to earn as many carrots as possible to maximize our capital. Divide the floors of each building into the shortest consecutive segments whose total profit is non-negative, and calculate the entry threshold of each such segment. The entry threshold is the minimum amount of capital required to construct all floors of the segment in order.
For example, consider two floors with $$$(a_1, a_2) = (10, 0)$$$ and $$$(b_1, b_2) = (0, 100)$$$. Constructing only the first floor is unprofitable, but constructing both floors yields a profit of $$$90$$$ carrots. However, an initial capital of at least $$$10$$$ carrots is required.
In an ordered set, we keep the next available segment for each building, sorted by its entry threshold. While the segment with the minimum threshold is affordable, we construct the entire segment, add its profit to our capital, and insert the next segment of the same building into the set. If the segment with the minimum threshold is not affordable, then none of the available segments can be constructed, meaning that we have maximized our capital.
In the second step, we independently try to continue constructing each building from its current height, floor by floor, for as long as the current capital allows. Among all buildings, we choose the maximum resulting height and, in case of a tie, the smallest index.
Time complexity: $$$\mathcal{O}\left(\sum m_i \log n\right)$$$.
2257F1 - Beaver's Jumping Track (Easy Version) Idea: pskobx, oblememan, egorka5opka
Since $$$x$$$ is small, we build a segment tree whose vertices store matrices of size $$$x \times x$$$.
For an interval of platforms, let $$$c[i][j]$$$ be the minimum penalty if the Beaver starts $$$i$$$ cells after the beginning of the interval and first lands $$$j$$$ cells after its end. Invalid starting positions are ignored.
For a single platform of length $$$d$$$ and penalty $$$s$$$,
where $$$0\le i \lt \min(d,x)$$$ and $$$0\le j \lt x$$$. The last jump leaves the platform and causes no penalty, while all previous jumps stay inside it.
To merge two consecutive intervals $$$A$$$ and $$$B$$$, enumerate the first landing position $$$k$$$ in $$$B$$$:
If $$$A$$$ contains fewer than $$$x$$$ cells, the Beaver may start directly inside $$$B$$$; in this case, we copy the corresponding values from $$$c_B$$$.
For a query $$$[l,r]$$$, obtain the matrix for $$$[l,r-1]$$$ and enumerate the first landing position $$$i$$$ on platform $$$r$$$. The answer is
The case $$$l=r$$$ is calculated directly.
Each update and query takes $$$\mathcal{O}(x^3\log n)$$$ time. Memory complexity is $$$\mathcal{O}(nx^2)$$$. Build is $$$\mathcal{O}(nx^3)$$$.
2257F2 - Beaver's Jumping Track (Hard Version)
Surprisingly, the main problem with the solution from F1 is memory, not time. A segment tree stores $$$\mathcal{O}(n)$$$ matrices, each containing $$$x^2$$$ values. For $$$x=10$$$, this does not fit into the memory limit.
To reduce memory usage, divide the platforms into blocks of size $$$B$$$ (for example, $$$B=16$$$). For each block, calculate the matrix of the entire block using the same merging formula as in F1. Then build a segment tree only over these block matrices.
For a query, at most two blocks are only partially covered by the required range. Process the platforms in these blocks separately, and use the segment tree to combine all blocks that are fully covered. After an update, recalculate the matrix of the affected block and update it in the segment tree.
For a block size $$$B$$$, the memory complexity is $$$\mathcal{O}\left(n+\frac{n}{B}x^2\right)$$$.
Each query takes $$$\mathcal{O}\left(Bx^2+x^3\log\frac{n}{B}\right)$$$.
Аnd each update takes $$$\mathcal{O}\left(Bx^3+x^3\log\frac{n}{B}\right)$$$.
Horrible contest
so bad D
interesting, i loved D! Really resembled USACO problems
nah it shouldn't be
Super fast editorial! But these statements are difficult to understand :(
bro editorial is wrong
Bad contest... but at least i gain some rating.
Can you recheck, if correct code is attached in the editorial. Seems different submission is present here pskobx
yeah I think first has nothing to do with 3 variables
type (user:XXX), if you want to ping someone. But with [], instead of (). But if you don't want to get your contribution < -100, please, don't ping someone unless necessary.
I'll fix it now, thanks
How dare you write the wrong range?
Apart from Figuring out TLE on D, everything was great!
Felt like eating shit.
My brain's full of shit.
Why was problem B so poorly written . As per the problem , one giant can hop on to another giants mountain .
Where was it ever mentioned that they can not climb another giants mountain if they are standing on something lower , or am i so dumb that i missed this in the problem somewhere , If so please point out where its mentioned.
Each giant has his own mountain range
Thanks
Hi pskobx! It looks like the code links to the wrong contest (Contest 1075) and not to the solutions for this one (Contest 1117). Is this supposed to happen?
Edit: it looks like the authors are aware of this from a different comment now, thank you.
why were all the problems so long
Back to newbie after this contest ig
I'm back to specialist too
TLE on D, QAQ
I thought it was a terrible contest, for its long statements with countless meaningless words. It would be better to provide a clear statement. What's more, I can't get any joy of solving problems during the contest.
What $$$S = 10^{12}$$$ solution did you try to kill? I believe everyone's first thought should have been just trial division to factor $$$S$$$. To me, $$$10^{14}$$$ is unnecessary and just makes constants tighter / Python fail. It also scares me because it gets really close to making int64 overflow.
For the record, I think D is a beautiful problem. I didn't read the others so I won't comment on them
python doesnt fail
There is a Sparse Segment Tree Solution that runs in $$$\mathcal{O}((\sqrt{S}+q) \cdot \log S)$$$ which would work for $$$S = 10^{12}$$$ but not $$$S = 10^{14}$$$. My solution was killed because of the constraint change :(
Here is a youtube-video about Sparse Segment Tree:
https://www.youtube.com/watch?v=XqE5T8vQX0Q
Yeah I think so too.
try learn some sparse table, its very helpful when it comes problem Like D in this contest, have a nice day ;)
sparse table is a useful structure, sparse segtree is fun but probably never useful in div2.
D in this contest solved without sparse structre, i have only prefix sum
why eveyone hates D so much . I didn't participate but it's just classical codeforces problem . I don't think many people thought about sprarse seg tree so the constraints change shoudn't be that bad
seems wrong submission link.
My Mistake I Clicked On Register Btn!!
Unrated this contest is the best choice I've ever made.
ngl good contest, although the problem statements are a little bit long (I enjoy reading them), and I might get — delta this time. I didn't attempt D so I don't know if the changes at the last moment of the contest really affect the performance
nvm I've just realized that C is trash: I've just upsolved it and everything I did is sort the array b and print the entire array except for the smallest one
C would be better if there are no constraint where $$$p_i \lt i$$$ you can't sort the array b normally, you need to sort it by the distance from the dams to the root. At lease it would need some graph skill.
But maybe stop downvoting this blog since the authors really tried their best?
Oh,no!I didn't solve problem C on on the contest.But now I know haw to solve it.XD
for D, the wrong range didn't affect my code at all, which is weird
387438160
can anyone help me with this? thk
You used a vector to store factors, and the incorrect data range has no effect on you.
F2 can be solved with a segment tree; you just don't need to store the leaf nodes. There isn't much to think about in the problems — most of the solutions feel quite natural, and the statements are also unnecessarily long.
GPT generated comment and code, wow.
The comment was translated by GPT, while the code was not.
It's amazing that 1.1e6 array can hold a 1e6 segment tree. Thanks for sharing.
bhadwa contest
+1
I don't want the round to be rated for me
meaningless problems,I think...
pretty cute animals ovo
but I can't understand what the statement of E is saying...
i think C is the only good problem.
E was just:
You are given N buildings to build. Each building has a maximum number of floors you can build, called M_i (for all 1 <= i <= N). Every floor in each building has a specific cost and profit (in carrots). The cost is A_i,j (ith building, jth floor), while the profit is B_i,j. You want to figure out the tallest building you can create with X carrots. If there is a tie, submit the smallest indexed building.
the last para of the statement
kept confusing me during the contest...
I was thinking whether it is allowed to build the floors of the same building in any order :(
since the sample tells nothing
I think you had to assume this, but they should have made it clearer.
yea,I can't fully understand E, and what's worse is that I read it in Chinese translated by AI.... and orz alb
Thick of it better than ts.
no thinking,only coding.
no wonder rating feels like gravity :(
D was some bullshit man!
bro,the code link of the problem C is wrong...
E is just a bad problem in my opinion. I had the idea immediately and the idea is so simple. just do all profitable stuff you can and then spend all the money you can on 1 building. it's literally the idea of a B problem, but it's just so so tedious to write the code for it.
can anyone explain D , also how did you get the correct intuition.
D killed me... i guess i'm back to specialist...
For F2 one can also just build segmenttree over relevant query positions.
Horrible contest！Waste my life!
Ok, I'll be honest, the contest wasn't great but wasn't bad and had some mistakes.
This is my opinion:
And 100% I'll upvote you, you tried your best
Agreed. It was so easy that I couldn't believe my first idea was actually correct.
Why F1 TL is so small... I bet there are many people like me, who didn't pass $$$O(nx^2 + qx^3)$$$ in TL
figure out idea for D in 5 minutes
spend 30 minutes implementing
WA or TLE and then limits change
C was easy to cheese...
Yeah, but my dumbass forgot about connected components, I thought my dfs would work until everything fell apart.
Look you don't even have to sort: https://codeforces.me/blog/entry/156058?#comment-1386479
Why didn’t you correct the data range in the system test for Problem D, and instead advise us to lose rating ? Do I have to write code using vector from now on just to work around faulty test data?
Problem E has very weak testcases considering how this brute force solution (Time Complexity ~ O(n^2)) passed 387466904
I think it's low-value,although I could got a high rating. D&E may lack attention,which is the hallmark of CF. only my opinion...
I don't understand where in the statement of question B does it say that when the beaver is switching from one mountain to another, his current mountain height which is the one he is switching to is not reduced by 1?
Am i just horrible at reading problem statements because same thing happened with problem A where I thought the abbreviations are sequential in nature or is this genuinely confusing when it comes to problem B?
BTW — Why can't I uphack A through D? I thought I should be able to do that once systests are done
Pretty angry to see the notice when I stuck with problem D for the whole time.I thought it would be a fun contest but it turned out to be terrible actually.
even if I didnt submit the solution for D, I still was trying to solve it and after the change in constraints lost a lot of time, so I can't get this contest unrated? Bruh
What's wrong with the wording of this contest?
I think for problem C, the answer does not even depend on the tree at all. You just need to sort all m verticies and print out all vertices except for the first one.
Code: 387466305
yes that's true and it has nice proof Initially, all m vertices are in one connected component. Removing any edge from a tree divides that component into two components. Therefore, we need to remove m−1 edges to make all vertices separate, so the tree has m−1 edges.
It works because of this constraint, (1≤pi<i; 2≤i≤n). So the tree is always ascending (a smaller value won't be a parent of a larger one).
I didn't notice that, so I ended up implementing a DP approach by calculating the depth of each of the dams using the tree.
The tree was actually absolutely useless in that problem.
yeah, that should be because of the condition 1 <= p_i < i which I didn't pay enough attention to realize building a tree and executing a DFS to check for depths was really unecessary
Actually, you don't even have to sort (tests are so bad lol): https://codeforces.me/blog/entry/156058?#comment-1386479
I have one doubt: can the final resultant be less than
m - 1?For example, consider this test case:
In this case, I think only 2 cameras should be sufficient, right?
If we place the cameras at positions 5 and 6, then:
So according to my understanding, the answer should be 2. Is this correct?
Oh,the camera can only track if the beaver pass the edge, not the node connected by the edge.
First of all, thank you for the effort you put in the contest and into trying to make statements cute, I appreciate that.
There's some feedback I would like to share with you anyway:
The general writing on the statements was a bit confusing, it took me a while to understand some parts of the statements. It's fine if you're not a native English speaker — neither am I — but I think that if this is the case, maybe going lighter on the storytelling side will benefit everyone
In problem A, I don't see much value in giving the abbreviations in uppercase, it just makes the contestant add a
tolowersomewhere. If all strings were lowercase the original idea could have worked just as fine without adding unnecessary trivial steps in the implementationIn problem B the drawing, although cute, is a bit confusing and contradicts what the statement guarantees about the order or both arrays. I'm aware the entries are marked with their correct indices but it can be a bit misleading IMO
I liked problem C though, although it sounds quite familiar.
I hope you don't get discouraged by the negative feedback.
Geometry is shit
orz contest. most of the people downvoting are just on copium from shitting the bed this contest. the problems were fine imo, though a little bit standard. I think basically everyone affected by the problem with D have a satisfactory way out (unless they got +delta and also messed up from it), and the rest are just using it as an excuse to hate on the contest more. if they weren't able to solve/impl with S leq 1e12, then they wouldn't've been able to solve/impl with S leq 1e14.
the impl for a-d seem quite easy, so long as you find the right observation, which isn't difficult due to them being fairly standard, and standard problems for a-d isn't bad in and of itself since these problems should be for ppl still getting started with cp, and dastardly derivation problems with > 1 obs shouldn't be in the pool for beginners.
I'm fairly certain most of the feedback isn't for the problems' difficulty, but rather the lengthy statements as well as overall weird designs. And personally I found B and E to be horrible for different reasons. B has a very long and confusing statement for an ultimately simple problem, and is too trivial. It is almost just a "please implement this procedure" kinda problem. E is just implementation hell and not interesting at all. You get the idea in like 5 minutes and you have to deal with implementing that bs. I legitimately just quit coding it halfway cuz it was so boring and didn't feel worth it at all. But C and D were good though, I liked them.
well implementation is a necessary skill, just like problem solving, and speed reading. e is not that bad impl imo. i think probably impl'able in at most 20-25 minutes. like its just basic pq greed. i think if your implementation skills are falling behind your problem solving skills right now, you should just grind some standard problems to improve your implementation.
exactly why was implementation of b being considered bad? You just had to sum the difference of elements for both array as s1 for a and s2 for b. Than if s1>=s2 first one wins otherwise second one wins. What is difficult in implementing this?
lol its actually even simpler, just calc $$$a_0 + n - 1$$$ vs $$$b_0 + m - 1$$$
I dunno, it was pretty simple imo. they're moreso saying that the implementation of E was cancer, while B was just really terrible to read.
I don't want the round to be rated for me
Edit: This Contest SUCKS! Just like IU SUCKS :)
Yes.
I have never meet that the date don't follow the information in the problem.That's so bad,isn't it?And I wondered why this problem wasn't be found before the contest?I think maybe the problem is come from the data creater because for me, my program have enough memory when S < 1e12,but S < 1e14.If is , you are too careless.But no more the problem on who , why this problem didn't be find?Is check really check the problem carefully?I think the contest can be a warning to others and I hope for more good contests.
I am Chinese, so please forgive me if my English is not very good.
I could have solved more problems, but I got tripped up by the confusing wording......
Hey guys, I think F1 & F2 are not bad so don't just click "Terrible" on every problem without thinking
Just an advice
Easiest F question of my life! It's just segment tree and matrices, tho dp is lowk hard and i had to rewrite like 40-50 lines of codes -_-
true, but why MLE????? I just used 1-index matrix, yet it exploded!!!
Didn't knew I was participating in english literature contest. Beaver this...beaver that lmao
Absolute HORRIBLE CONTEST, you do not even have to bother sorting on problem C and you can still get the AC: https://codeforces.me/contest/2257/submission/387474477
Counter example: 3 1 2 2 3 2
1 -> 2 (dam) -> 3 (dam). The code outputs: 2.
Clearly, putting a camera on the edge between 1 and 2 does not uniquely determine wether the beaver is at position 2 or position 3. But the contest accepts the incorrect solution.
Here's my idea of proving why the sort is necessary, (please contribute your thoughts in the comments and help me out because your favorite pupil is now a newbie again):
Since all i > pi, the smallest dam cannot have a parent further up the tree who is also a dam, thus removing the connection between the smallest dam and its parent (provided it exists) does not separate the current smallest dam from the connected component of another dam (since it literally doesn't exist further up the tree).
what? sorting is not necessary in any way. conceptually, turn the tree into a virtual tree, then place a camera above every single node except for an arbitrary root node in the virtual tree. since we can reroot the vtree arbitrarily, we can just remove a dam arbitrarily, thus just printing all the dams from index 1 to the end suffices.
Sorting is necessary: read my counter example from above, you cannot place the dam at position 2, the correct position must be at position 3.
Since the problem itself has 1 ≤ pᵢ < i, can't we just remove the location that appears first?
Read my original post please: look at the counter example I provided on why you can't just remove the location that appears first.
Doesn't your counterexample show that the first occurrence is 2 (dam)? Then if I don't keep the first one, can't I just output the next one, which is 3 (dam)?My point is, since it's guaranteed that 1 ≤ pᵢ < i, I can just mark the dam positions and then traverse from 1 to n, skipping the first one.
The "mark then traverse 1 to n" is still sorting — you still skip the dam with the smallest number. Only difference is that you use a counting sorting instead of a quick sort.
You're right, this is essentially sorting as well. But is the data really that weak? My friend didn't perform any sorting operation and couldn't pass it.
Initially when i used to solve div 2 C my rating used to increase but in this and last even after solving it is just as it is or may be it can fall...
Cheaters are increasing...
Hello! My submission of E after contest: 387471823 was absolutely wrong but got AC, which should have failed on this testcase:
1
1 15
3
0 10 15
5 0 30
Maybe the system test was still not strong enough?
I don't want the round to be rated for me
The constraint really ruined my day. I spent a lot of time deriving and eliminating cases, and I finally found a solution in O(√s × log(√s)), but when I went back to implement it, the constraint changed. So, I had to give up.
Can someone help me why my code is failing for A, its almost very similar to the editorial and I can't find the difference. 387408042
Bro you are returning without taking all m inputs
FAAAAAAAAAAAAAAAAAAAAA i'm so stupid. Thanks
Also had another doubt. I tried to simulate the game for the testcase #5
4 2
4 3 2 1
6 5
Round 3, Ver gets hit and has a height of 4, sees moutain height 5 jumps to it, then throws the boulder at Bea.
and really sad for u dude, not even a solve in Div.2 :<
So they can jump to the next mountain AND throw a boulder on their turn?
Also yeah this round went really bad for me hahahahah. Still positive delta yayy lol
yup
also u should upsolve too
I am, this is an alt account as i am too rusty and don't wanna mess up my ratings for now in main account. Once I reach expert I will start giving contests from my main. Currently I am practicing there and giving contests from here.
can i know your main account?
zero_bitches
Using alt accounts for contests is against the rules. If you don't want to mess up your rating then do virtual contests or just upsolve.
Virtual contests are boring. I never participated or would participate with both accounts at the same time. And idk but I don't think it matters when i can't even solve div2 A lol
If you can't solve div2 A then upsolve. If you think virtual contests are boring and that you don't wanna upsolve then get out of Codeforces.
ALERT!!!!! WE GOT THE CODEFORCES POLICE HERE!!!! ALERT!!
???
Telling people that you can't break the rules is
"Fun police"???
Huh?????
Is this mocking the rules or is it just "Ehhh It's not against the rules" even though it CLEARLY IS? Actually both of these are practically the same
I'm not even mad I'm confused
I like to track my improvement. According to me, and the main issue with alts is that people are smurfing and polluting the div2,3,4 rankings. But I believe i'm actually starting as a beginner once again after years, so i'm not making it unfair for anybody. Yes, there are other ways by joining virtual contests but they don't have the contest thrill and wouldn't keep me motivated for long. Also stop spamming 800 rated questions
My practice is not in the conversation right now, why are you bringing it up. Yes I know that my problem portfolio is shit but I'm training on other platforms to eventually become pupil. You could see that if you opened your eyes and clicked on my never-seen-an-update submissions page.
Regardless if you're rusty, you must use your main account to give contests. This is due to the fact that you still have some kind of experience from your main account, and thus you're smurfing. Doesn't matter if the experience is small, it still counts.
Yes write full story about everything. Please add two more paragraphs next time to problem statements.
I have this hypothesis,
Longer the problem statement, Bigger the gap between honest candidates vs AI cheaters ( AI will be faster to solve, while honest people will be scratching their heads trying to understand the bullsh*t ).
again horrible pskobx contest
ok Red John !
were all requests to make the round unrated even reviewed? i got MLE in D which may not have happened if sqrt(S) <= 1e6? i am not sure but there is a possibility. I read the problem 1 hr back and didn't see the constraints suddenly changed.
Not all requests have been reviewed yet, we are still looking into the situation
bad editorial. unnecessarily wrong words
It is such a match which makes me laugh that although I did A+B in 30 minutes,I only +2 rating,and that I spend more time on A than B.I consider C as a complex data structure problem,but it has nothing to do with "tree". By the way,when is the next CodeForces Round,and how to deal with the problem which doesn't need deep ways but needs to think a lot better?
Can somebody tell me why this gives tle ?
387481242
it lowkey doesnt look like you wrote it but an AI chatbot does, or you just give us comments to show what youre trying to immitate
yeah... , nice try Sherlock from temu
its just my gut cuz theres unneccessary spaces TuT, i wasnt trying to make war
Its all right ,dude
In your factor loop you compute i * i where i is an int, thus causing integer overflow and therefore undefined behaviour.
Got it , thanks
Problem A: Why does this submission fail? 387404047
dont exit the function after cout << "NO\n"; because you might still have some inputs left
This is really bad, I made this mistake, which resulted in A not being written
Ahh, I did such a horrible mistake :( Thanks!
I found this contest good and interesting
Can anyone explain how to solve C. I have just started Graph and have completed BFS, DFS and trees.
All what we need is to put a camera before every attended node, since if we have one camera for more than one node, we can't follow it, then just $$$m-1$$$ cameras are needed, since if we didn't record nothing it's the last node without camera, so we can just sort, and add a camera before each node except the first one, to avoid the edge case of having $$$1$$$ as a destination
I miss read D and thought it asked for the number of rectangles that totally incase the (x,y) rectangle in the query, and spent an hour writing an offline solution with coordinate compression and segment tree.
totally my fault, but would have been a cool problem lol.
Bad contest. No thinking, just coding.
In problem A, I got stuck on a mysterious question and ultimately didn't manage to solve it.QAQ
So hard to get ratings.l just solve A and B.For C,l didn't study graphs.Because of two wrong submissions l was taken some ratings. QwQ
Ah, I only solved A
You can do it!A and B didn't include difficult knowledge.
C is actually just greedy/dp, answer is quite beautiful if you think about it
Got it.I'm learning about that.
good luck!
I don't know why author write problem A and B like this. It is so difficult to understand, but when you understand, it only take one or two lines. Really reading comprehension problem in the contest.
Contest is so misunderstood, at least F is easy. Thanks for expert though
There's an edge case that seems to be missing from the statement of E: when no building can be constructed at all (height = 0), what should the index be? The intended answer seems to be 1 (the smallest index), but this is never explicitly mentioned, and the sample doesn't demonstrate it.
Stuck on it for a long time :(
I was just wondering why the statements are that LONGGGG and it really makes some trouble!!!
i too m irritated man its statement for mind woggling not baby sleep time story
Mr. pakman box please write a contest to focus a little on story and more on problem ,u r including too much story.
In question B, the TC should be O(1), and not o(N).
can anyone clarify.
bottleneck is input
Problem A highly demotivated me from continuing. Codeforces should introduce algorithmic questions a bit earlier, like in problem B or C.
Just saying.....
Editorial is not well explained. can anyone tell me how to do D?
i didn't even solve D why'd you mention me T-T
nvm
holy crap, i just fixed it!
Nice
(sorry if this is bad i'm not a very good writer)
We first preprocess all divisors of $$$S$$$, and make a list of all of its divisors. Note that the Bermuda rectangle forms a staircase shape. Each section has width $$$d_n - d_{n-1}$$$, where $$$d_n$$$ is the nth divisor of $$$S$$$, and height $$$\frac{S}{d_n}$$$.
Now, we precompute the areas of all the sections of the staircase, and store it as a prefix sum. Now, for each query, we find the largest divisors of $$$S$$$ smaller than $$$x$$$ and $$$\frac{S}{y}$$$, call them $$$d_x$$$ and $$$d_y$$$ respectively (calculus variables lol) and find the minimum of these, because $$$d_y$$$ shows how far we can go while maintaining the maximum height $$$y$$$, and $$$d_x$$$ shows how wide the query rectangle is, and multiply it by $$$y$$$.
We then use our prefix sums to calculate the sum of all complete sections up to $$$x$$$, and add it to our total. If $$$x$$$ is in the middle of a section, the remaining calculation is trivial, just multiplying the width of the section minus $$$x$$$ by the height of the section.
Time complexity is $$$O(\sqrt{S} + Q\log{S})$$$.
Thx bro
Generally speaking, difficulty is ok, and solutions of problems are good, but A and B take more time to understand the meaning than to solve them, which I don't like. The style of problem D is not similar with common problems in codeforces, but I think it's a good problem. And I love problem E.
TOO BAD CONTEST !!! WEAK SYSTEM TEST CASES FOR PROBLEM C
CAN BE SOLVED WITH O(1) SOLUTION BLINDLY WITHOUT EVEN CONSIDERING TREE! PLEASE FIX!!!
Weak system tests for Problem C (Accepted an O(1) solution that ignores the tree)
Hi everyone,I wanted to report weak system tests for this problem.
The submission https://codeforces.me/contest/2257/submission/387535811 somehow got Accepted with an O(1) solution that completely ignores the tree's edges and structure.
This is the entire logic part of the code it the submission is not visible ~~~~~ // this is the code ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t = 1; cin >> t; while (t--) { ll n; cin >>n; ll temp; for(int i=2;i<n+1;i++){ cin >>temp; tree[i].pb(temp); tree[temp].pb(i); }
ll m; cin >> m; vector<ll> vert(m); for(int i=0;i<m;i++){ cin >>vert[i]; } ll sk=0; for(int i=0;i<m;i++){ if(vert[i] ==1){ sk =i; break; } } cout <<m-1 <<" "; for(int i=0;i<m;i++){ if(i !=sk){ cout <<vert[i] << " "; } } cout << endl;~~~~~
The code essentially just prints m-1 and then blindly outputs all the target vertices except for the first one in the input array.This logic is fundamentally flawed. It only works if no beaver dam is an ancestor of another.
The system tests seem to entirely miss cases where multiple target dams lie on the same path.Here is a simple counter-test case that breaks the Accepted solution!!...:
9 1 1 2 2 3 3 6 8 5 8 6 4 5 9
The Tree Structure:1 -> 2 -> (4, 5)1 -> 3 -> 6 -> 8 -> 9(Vertex 7 is a child of 3 but not a target).
Why the code fails on this (and why the tests are weak):
The code arbitrarily skips the first target in the list (8) and places cameras on the edges directly above the remaining targets: 6, 4, 5, and 9.
If we trace the paths:If the Beaver goes to dam 6: Path is 1 -> 3 -> 6. It crosses the camera above 6. The sequence is [6].
If the Beaver goes to dam 8: Path is 1 -> 3 -> 6 -> 8.
It crosses the camera above 6, but no other cameras. The sequence is also [6].
Because destinations 6 and 8 produce the exact same sequence, they are indistinguishable. The output is invalid, yet this approach passed 100% of the system tests.I hope this test case can be added to the problem so these flawed submissions can be rejudged!
I don't think the system tests are broken though I think it is just another way to solve the problem And it's not an O(1) solution I did the same solution as yours too
No, he's correct.
The input constraint $$$p_i \lt i$$$ does guarantee that you can omit the smallest element in $$$a$$$, but because $$$a$$$ is not sorted in the input, it is not correct to simply print the first (or last) $$$m-1$$$ elements of $$$a$$$.
Your solution is correct because you explicitly sort the array before printing, but the linked submission doesn't do that. That solution is wrong, but it passes the system tests.
Oh okay
There's a much simpler solution to problem C 387432998
AC F2 without dividing platforms into blocks, 387546433
It seems we don`t have to do special calculate on the side of the question intervals, simply ask it on the segment tree is fine. 387547847
Can anyone explain the editorial of C? I didnt understand anything
I believe each query should take $$$O(Bx^3 + x^3 log\frac{n}{B})$$$, since on each query we will process $$$B$$$ platforms and each merge takes $$$x^3$$$.
We shouldn't merge each platform in $$$\mathcal{O}(x^3)$$$, because the starting position is fixed. Instead of calculating $$$x \cdot x$$$ matrix we can keep just a vector of $$$x$$$ possible positions and process each platform in $$$\mathcal{O}(x^2)$$$.
But, ofc, a simpler way to do it is to recalculate the matrix in $$$\mathcal{O}(x^3)$$$.
I see, so this removes the necessity to mutiply matrices and we only need to multiply vector by a matrix. Cool idea.
Problem D is absolutely terrible!The ranges of S and T do not make sense.If T reaches 10000 and S reaches 1e14 ,there will be nearly 1e11 to divide S in all testcases!However,the testcases turned out to be 1 in each test.So the limits actually do not play the role.
Hey there, i am just wondering if any higher ups can look into this or like some good coders as i am not that good myself. The user jaadugar251 (https://codeforces.me/profile/jaadugar251) seems to be from my college as he/she mentioned on his profile and clearly doing great in contests recently which i find very suspicious because my college doesn't have talented people like this and more practically no one even does codeforces so i am just wondering is the person cheating or is actually amazing at programming skills and like cp?
How can this such of thing be accepted by CF? Pretty many testers with out a human. How can this so big bug in D exist? And so long problem statement. Are problem setters human or AI?
I debug RE and TLE on 11 in D for an hour. I tried to submit
I don't want the round to be rated for meinAsk a questionbut nothing happened. When can CF calculate the rating again.Ahhh, when can this round be unrated for me.
https://codeforces.me/blog/entry/156058?#comment-1386547
10 days over but I was still rated for this round.
in first problem is it me or did somebody else as well suspect that they used words and letters in place of each other many times I think that was something, that made me think in the solution in different directions but after reading the test cases yeah, I got it but I think it's good to review the statements once before finalizing them
can anyone explain whats the point of min depth logic in C. According to me even if there is no dam at root , we can arbitrarily skip any edge with dam on one end point. My code got accepted with this logic
Lots of ppl are criticizing the test... but this is a decent test tho, except for the wrong range.
for C i just printed all the m vertices except the minimum one and it got accepted . I didn't even need the tree . Lol
Is D just prefix sums and then binary search? Oof missed it.
Are there any similar problems to D that you're aware of?
For Problem B, this was my intuition. Since the winner is determined by who ends up on the last mountain and reduces its height to zero, we can simply measure the total effort required to reach that state. We calculate $$$a_i - a_{i+1} + 1$$$ for every adjacent pair, add $$$a_{n-1}$$$, and do the same for the other player. Let the resulting values be suma and sumb. The player with the larger value wins. If they are equal, Bea wins because he moves first.
This is essentially the same idea as the editorial, but I feel my explanation is more intuitive and easier to follow. my submisson : 387686534
Another random observation: E reminded me of https://codeforces.me/problemset/problem/1912/A.
problem c was the easiest task i have ever seen. The problem statement was quite confusing
Was attending the contest as a virtual one. Spent 40 minutes on Problem C and realised this solution in the last 5 minutes. I was surprised that it got accepted
Bad F2. After finishing F1, I thought that the x of F2 would become very large. I was still thinking about how to do this. In the end, it only doubled and then examined the ability to optimize storage. It was too meaningless.
took eternity to understand what the problem was saying
E is an easier version of this problem from BOI. Just the graph is bamboo's linked together instead of a tree.
ın c problem, ı couldn't really understand by what is meant by that expression: "and then, in the same line, for each of the k edges connecting the vertices u and pu, where cameras need to be installed, output the vertex number u."
are there any magnanimous who can help me understanding?