Hello, Codeforces!
On behalf of Meet IT, I'm glad to invite you to (Codeforces Round #683 by Meet IT (Div1, Div2) which will take place this Sunday (15th November).
The round lasts 2.5 hours and is rated for both divisions.
What is Meet IT?
We are a family of enthusiastic and motivated young people passionate about programming and mathematics. We build a community where people learn together, motivate and help each other.
Meet IT family members worked hard over the last few months to provide you with our favourite challenges we came up with. We hope that you will enjoy them as much as we did :)
We are enthusiasts of short and clear problem statements, strong pretests, and happy participants!
Every effort is valuable for us, and therefore I'd like to thank everyone who has contributed to the creation of this round:
- Co-founders of Meet IT: Mateusz and Paweł for guiding Meet IT projects and making things happen.
- Maciej, Piotr and Michał. Without their commitment in early years of Meet IT the Family would not exist.
- Round coordinator antontrygubO_o for endless discussions about the problemset.
- pawelek1 for coming up with problem ideas.
- tnowak for massive support in the work on harder tasks.
- staniewzki and jjaworska for developing the most challenging problem of the round.
- pasawicki for interest in tennis which was an inspiration to one of the problems, and for preparing another problem.
- lcaonmst for preparing a problem quickly and diligently.
- Mohamed.Sobhy for coming up with a nice easy problem and preparing it.
- Amtek for enduring my repetitive reminders to prepare a problem.
- flaviu2001 for his excitement about the round after testing and help to improve the shortcomings.
- _h_ for help in providing a high-quality editorial to one of the problems.
- dorijanlendvaj for firmly complaining about one edgy problem that pushed us towards substituting it with a better one.
- kobor for providing beautiful pictures for the removed problem. :(
- Devil for coming up with the substitution problem :), without you we would be still finalizing the problemset.
- arsijo for paying special attention to statements clarity during testing.
- zdolna_kaczka for winning the virtual contest among testers.
- Anadi for inventing an alternative solution to one of the hard problems as well as his kind comments and suggestions.
- Farhan132 for his ideas on how to improve the problemset in the second division.
- Linkus and ZenekMartyniuk for showing the need to reduce the round difficulty a bit.
- The Army of Testers: ffao, RetiredPlayer, Retired_cherry, Whistleroosh, ijontichy, coderz189, AwesomeHunter, H4ckOm, TeaTime, hg333.
- MikeMirzayanov for the amazing platforms Codeforces and Polygon.
- all the people who strive for Meet IT Family to grow.
- Last but not least, my dear wife Marta who was very supportive throughout the long process of preparing the round.
UPD
I'm also thankful for Swistakk for testing the round thoroughly. Sorry for forgetting! I wrote the announcement sometime before that. I totally don't get why he got downvoted, please give him as much contribution as he deserves!
UPD 2
There will be $$$6$$$ problems in each division, with $$$4$$$ problems shared. One of those will have a subtask!
We strongly recommend to read all the problems. You have been warned :)
Scoring:
Div 2: 500 — 1000 — 1250 — 2000 — 2250 — (2500 + 750)
Div 1: 500 — 1000 — 1250 — (1750+750) — 3000 — 3000
UPD 3
We would like to host a stream shortly after the contest. We haven't yet figured out the details, you can expect some backstage stories about the round, Meet IT, and casual discussion. Stay tuned!
UPD 4
We've added the link to the stream which shows on the Streams pannel on the right. You're more than welcome to join our stream
UPD 5
UPD 6
We hope you've all enjoyed the round despite some minor issues. Congratulations to the winners!
Division 1:
Division 2:
I was aiming to reach red before this round so that this announcement looks more serious, but my attempts ended up with almost falling to purple and I'm very happy it's only almost.
It might be helpful if you write the date and time rather than "this Shnday", since it appears to people that this blog was posted 3 weeks ago. I almost thought this was for an old round, but I realised otherwise once I saw the lack of comments.
This is confusing. The post was created 3 weeks ago indeed. But it was published 20 minutes ago (Wednesday evening).
I understand, but at the top of the page, it still shows 3 weeks ago as the date, so it'll probably be helpful if the wording is changed from "this Sunday" to "Sunday the 15th of November" or something similar to avoid any confusion :)
Sure, Done!
Behind the scenes: they were talking about this round for almost a year, so if it won't be good then I don't know how much time you'd have to spend to make a good round.
I am sure it will be a great round. kpw29 and rest of the team were very excited about making it :D
weird flex but ok
look at the bright side, at least, you have the freedom.
Don’t you think that saying who won virtual contest, who developed which problem or who came up with which problem is a small hint for everybody who know these people?
In some way maybe, but not much bigger than just revealing writers of upcoming round which is done on daily basis.
I don't think that any of the descriptions gives any advantage at all. In fact, many of the problems were invented by a person other than the one who developed the problem package.
As an unmentioned tester let the community repay me this lack of gratefulness with contribution from them. Upvotes — come forth!
I'd participate in the round if I wasn't mentioned as a tester.
I think it is more about whether you have seen any of the problems before?
I think it is more about mentioning people who spent their time to test your round.
To not be misunderstood, I don't really care that much, just messing around
Looks like you almost got more upovotes than the round itself :D
As a first time tester I'd like to say unlike kpw29 I have solved the tasks twice now. Also a great round is waiting for you all :D
Nice to see the contributions of each tester and setter being elaborated :)
Is it rated?
Yes, the round is rated for both divisions.
Plot twist: the comment above gets many upvotes. What about making today a kind day for muchieej_orz? Community, I believe in you!
Hooray! 2 contests in three days!
Brace yourselves for another antontrygubO_o show:)
Do we really need these LONG LONG comments to all contributers and testers??
As some comments provide little hints, in some sense we're forced to read it and it's an annoying work for me. (like "inventing an alternative solution to one of the hard problems" is some kind of hint)
I'm sorry if you don't like those :(
"(like "inventing an alternative solution to one of the hard problems" is some kind of hint)" I don't think so. Most of the problems have alternative solutions, don't they?
"most of the problem have alternative solutions" — agree. though, the information which this comment provides is not only "the existence of the alternative solution" but "the existence of alternative solution which is easy to come up with and worth to mention in editorial".
Do you still think this is no hint?
Yeah. Your conclusion might be wrong. Let's come back to this after the round!
You can just choose not to read that.
I'm sure you won't be at a great disadvantage, and you also won't waste your time:)
maybe you're right, but I'm not so brave or strong enough to forgo may-be hints in front of me :(
please, don't get unrated again...
Congratulations on your marriage! So happy for both of you <3
Thumbs up
This is the most wholesome round announcement I have ever seen. Well done, see you on the scoreboard!
Now this my friend is what you call an announcement
This guys H4ckOm was plagiarised a few rounds before in Codeforces Raif Div1+Div2 and still he testing rounds? Seems risky.
I hate problems
[Deleted]
[Deleted]
I'm not sure how you counted Anadi, arsijo, zdolna_kaczka, Swistakk and a few reds among writers to be the same person :)
be aware they will have odd, even number type questions, as the rounds are going as 13,15,17.19,21(Div2), Hoping that this series will continue after 21.
"Last but not least, my dear wife Marta who was very supportive throughout the long process of preparing the round." .this line touched my heart.
"We strongly recommend to read all the problems. You have been warned :)"
I wonder how to interpret these words :/.
It seems unrealistic but
2500 + 750looks interesting in F1-F2(Div. 2) problems. Maybe F2 should be the easier variety of F1?)No, you can picture this as: F1 is already quite hard, and you get bonus points for something on top of that. In other words, F1 is a substantial part of the whole problem.
got it, thanks)
Usually (something+something) are easy version and hard versions. Hard versions may be stricter in constraints or have additional variables.
In this case maybe F1 is already hard enough and F2 is just a small optimization of something.
excited to participate in this round...
One of the best contest i ever gave, enjoyed a lot! Thanks for the interesting tasks!
https://www.youtube.com/watch?v=jRKSlI-Qvcc
That feeling of the rise in difficulty from D2C/D1A to D2D/D1B is a killer. The round had sexy af problems. I wasn't able to solve D and above but I really liked thinking about them and how I was thinking about them. Thank you for the amazing round setters and testers <3
Agree that round was amazing :)
But on the other hand, because D2C/D1A was more ad-hoc and D2D/D1B is a slight modification of classic LCS dynamic programming, I found D2D easier.
Thanks, nice to hear that!
What is pretest 6 for div-2 D?
Pretest 6 was cancer man
One of my submissions failed on pretest 6, because it allowed negative dp values (in the LCS-like dp such that $$$dp[i][j]$$$ is the maximum possible similarity score of substrings C, D such that C ends at i and D ends at j).
Given that you can always choose empty substrings, the dp entries obviously have to be non-negative.
Is there any particular reason for putting 256 MB memory only in div1D?
No, it's the default one. We haven't had any solutions which was close to that :/
How to Solve Div-1 D??
How to solve div-2 E ?
When you insert any good sequence into a trie, for all vertices one of the sons will have <= 1 vertices in subtree. You can calculate cost to convert trie into a good one with dp.
How to solve Div2-D ??
Nice problems. Was there some reason for choosing 4*LCS — |C| — |D| instead of just LCS — |C| — |D| in D?
because then the answer would always be 0
Yes, cause in other case answer is 0
Oh yes just realised that. So any factor would have worked as long as answer is non trivial. Thanks.
It can be shown that the optimal solution for LCS — |C| — |D| is just two empty substrings :)
I'm guessing 4 was chosen to facilitate generation of strong testcases (too large a constant would probably allow scams based on just finding the LCS of the strings, too small a constant and you may not be able to easily generate non-trivial large testcases)
how to solve div 1 c ? i understand that graph is a forest but what is the answer
how to solve div2 B?
notice that an even number of negative number can change to all positive
If there is a zero in the grid, you can always make all elements positive.
If the number of negative elements is even, you can always make everything positive.
If the number of negative elements is odd, one of the elements will always be negative in the end after all operations. Try making this negative value as the one with smallest absolute value among all numbers.
what's wrong in this implementation for B? https://codeforces.me/contest/1447/submission/98492176
notice you can also change a negative number to a positive one
I know it, so what's the problem in code? If there's no zero and odd count of negative numbers I'm looking for smallest in absolute negative number to subtract from sum
You have to subtract it twice. Because sum is already sum — min number.
in that case you have subtract twice of that number cause you already added it in your sum once
I'm subtracting it twice in line 41
sum += 2 * list.get(0);listat this time is sorted in descending order solist.get(0)is smallest by absolute negative numberyou are not getting it right you have to take minimum in not just negative but positive also so that its absolute has minimum value
like in 1 -2 -4 2 5 the minimum is 1 but in your case its -2
now I get it. Thank you!
First time got TLE on using long long in place of int ( in DIV2D or DIV1B ).
d1 F was same as this problem with solution described in this blog.
Fortunately it was on HackerEarth so probably nobody except you knew xD
And I still couldn't do it anyway because I didn't open it during the contest thinking that one was probably different. ;_;
I hate this "you need to log in" shit. I didn't open any HackerEarth problem in a long time because of that.
Any help on Div2E/Div1C, I think we need to group those numbers with same most significant bit, since they will choose to connect other members in that group, like [0 1 5 2 6] -> [0 0 2 1 2]. Then we sort the number of members for groups, like [0 0 2 1 2] -> [1 2 2]. Then we remove the smaller groups (except last one) to only one member, so [1 2 2] -> [1 1 2]. So answer is 1. But I get wrong answer, anyone can help?
After you group the number with the same most significant bit, they still don't make a connected component. For example, add to all the numbers in your example 2**31. It will not change the graph, and they will still not form a connected component.
Oh you are right. I made a very bad assumption. Thanks!
Can anyone tell me why my memoized code failed for Div 2-D?
It should be only twice as slow, as the recursive version needed another dimension
98483763
It took me about half an hour or more to convert that code into it's iterative version.
98491583
There's a recursive version of the solution without the extra parameter. It passes pretests in about 500ms, so I can see the extra x2 factor giving TLE.
Basically, the observation is that "started" is useless because you can determine where to start by whether you can get a value greater than 0 by continuing to take letters.
Code: 98454285
I see, thanks a lot!
In my case , i changed long long to int and TLE was removed. long long uses more time .Also recursive calls have more overhead. But in my case it worked with int and recursion.
Great contest! Problems were great and well written!
I especially liked Div2E which was a beautiful problem with a beautiful solution, and solving it saved my rating from dropping to LLONG_MIN :P [couldn't solve that damned div2D :( ].
can you tell me why resulting graph do not contain cycle??
Write down what happens with a triangle and eventually you get:
a+b>a+c>b+c>a+b. And you get a+b>a+b, contraditction.
The inequalities are correct because (by order of them):
1. a chose b over c
2. c chose b over a
3. b chose c over a
You can apply it to any cycle
i didn't got what is a+b or what does these inequalities say?? can you explain little more??
by plus I meant xor (I should have used ^)
Thanks i got it now :)
didn't see this comment in time XD
Say you have a cycle in the graph of size 3 (a triangle), and it's made of three nodes (numbers) — a,b,c. suppose the direction of the triangle is
a->b->c->a.
That means a chose b over all other numbers, b chose c over all other numbers, and c chose a over all other numbers.
So far so good? I think I'm being pretty clear so far.
Now, what does this mean for their xor values?
because a chose b instead of c, you know a^b < a^c
because b chose c instead of a, you know b^c < b^a
because c chose a instead of b, you know c^a < c^b.
from these inequalities you can build the following inequality (which actually means my inequaility was wrong in the last comment):
a^b > b^c > a^c > a^b
Thus you get a^b > a^b which is not possible.
Yes i got it Sir :) Thanks for such a amazing explanation.
I am talking ABOUT XOR TREE PROBLEM
Solution to problem C (Div. 2) was mentioned here.
Not sure which solution you're referring to, but the solution for problem C was O(n) and I didn't see one in your link, because the problem is more specific here.
BTW you failed the pretest because you need to do what you did in decreasing order (you sorted in increasing order and that doesn't work).
https://codeforces.me/blog/entry/82067 Copied from stream lol
Can anyone please tell how to solve Div2D ?
https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ read this and try to adapt it to the problem
Got a color change on atcoder today and now expecting the change at codeforces too. Happy Day :)
Isn't the only difference between div1D1 and div1D2 that we want to consider subarrays where everything occurs very few times? After all, for a given $$$f$$$, only values that occur $$$\ge f$$$ times in the whole array are important and there are at most $$$N/f$$$ of them. For $$$f \ge 2,000$$$, it reduces to D1.
I haven't solved D1, but if I did, then D2 would be easy. If $$$f \le F \approx \sqrt{N}$$$, and we fix $$$A_{l-1} = v$$$ with $$$l \gt 1$$$ (optimally $$$v$$$ should occur $$$f$$$ times), we know the optimal $$$r$$$ for a subarray $$$[l, r)$$$ that contains at most $$$f$$$ occurrences of each value and only need to check that it contains at least two values $$$f$$$ times.
Yes, I solved D2 this way and don't get how you can solve D1 but not D2.
Most testers reasoned this way, too! But there were some technical difficulties in coding this which apparently stopped most people. Maybe there were just trying themselves with E,F.
Initially we wanted the problem without the easy subtask. That would not be a good decision...
You could have flipped the subtasks. Then it would've had an easy subtask. This way it has a hard subtask and a slightly harder full solution, not an easy subtask.
How do you flip the subtasks? Let the easy subtask be $$$f \le 100$$$ instead of $$$a_i \le 100$$$. Flip the scores too. It's a bit of an in-your-face hint that the hard part is for large $$$f$$$, but that's fine.
I thought it's better this way. The interesting part of the problem needs to be solved by everyone, the more technical bit can get you some additional points if you spend more time on it. I'm against obvious subtasks in hard problems which require just coding. In the end the ratio of solves C/D1 is not too bad! :)
Then you pretty much get one either way and just choose if you want it to "unlock" after solving a harder problem / hard subtask (D1).
Do you like (D2 minus D1) as a separate problem in this problemset? Why/why not? These reasons don't change whether it's a subtask (in any order) or a separate problem.
The initial problem was D2, we've added D1 because we (correctly) predicted it's going to be too hard. Would you rather have only D1 instead of the full problem?
There are a couple of things which make implementing D2 more difficult than solving just D1 and I think it's fair to give some additional points for those who can do that. D1 is interesting on its own, but D2 is more natural.
Not sure if that answers your question though
Yeah, I'd rather have D1 if the main reason for splitting is implementation difficulty. This middle way feels like combining the worst of both ways: neither discarding a problem because it's implementation-heavy nor using it despite that.
As for what's more natural... well, D1 must be natural enough to use because it was used. It's normal for problems to have constraints like $$$1 \le K \le N \le 10^5$$$, $$$K \le 100$$$. You might as well have left D2 as a simple bonus/challenge in the editorial. Instead of this "haha you might know how to solve it but can't".
I figured out how to solve the whole problem shortly after; I'll try implementing after I wake up and tell you how hard I found that for each half.
Alright, so D2 has short implementation: process values from left to right, for each value, maintain the list of last $$$\le \sqrt{N}$$$ positions and for each $$$f \le \sqrt{N}$$$, maintain the smallest 2 of the values at $$$f$$$-th index in those lists (pad with $$$N$$$); usually, we'd need a set to update the smallest 2 values, but since all elements in those lists can't increase, we actually need just the smallest 2 as some kind of mini-heap.
I think people were just discouraged by D2 being the second subtask. It's very straightforward and I wouldn't use it at all.
I solved D1 in 100 * n, and I don't see clear way to generalize it for harder version.
I described one in my comment. Basically, you don't generalise, just solve it separately — that's applicable to every problem with subtasks.
Very nice questions
In problem Div2-C, looking for programs that have been scored as correct, I see that all of them considered half of W as [W/2+1], but in the text of the problem it was clear that the condition was [W/2] <= C <= W. So, if W=101, a sum of 50 was within of the constraints of the problem.
Don't you agree?
read about ceil and floor of a number. In the problem was ceil(w/2) not just (w/2)
You are right, I didn't know the difference between that notations, and even though I realized that the floor supposition didn't make much sense, I took it for granted. Frustrating, but I've learned something new...
Thanks!
Could somebody explain the problem with my Div2C code?
https://codeforces.me/contest/1447/submission/98479826
What the code does:
Sort weights For each weight from least to greatest: if adding this weight causes the sum to be > W, continue else if adding this weight puts the sum in [W/2, W], we're done else if adding this weight makes it impossible to get a sum in [W/2, W], continue else, add this weightIf there is a single value in range W/2,W we can use this single element.
I tried such a case:
Output:
So I don't think that's the issue
I did not inspect the code, but if it does what you wrote above, then it will fail on cases like
w/2,w=5,10
items: { 4, 7 }
It outputs:
Which seems to be correct
Your code seems to also check the next element when trying to add the current element in. Try this case:
n = 3, w = 10 items = [2, 2, 9]
Got the issue now. Thanks!
Ok, what about this one: { 4, 7, 11}
It seems you have that speacial case for the last element of the items, but that is not good. It might work if you throw away all items >W in the first place.
The main error in that code is that it is horrible complecated.
In the end you need to check if a prefix sum is in the range or a single element. There is no need for anything complecated.
Can anyone give a hint on div2 D?
https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ read this and try to adapt it to the problem
thanks, I saw your submission also, now I understood.
Lot of people failing on test 10 in D2B. What is that test ?
can anyone tell me what was the pretest 6 of problem D div 2 ... thanks
some like 3 3 abc xyc
A great problem set — brief and to-the-point problem statements (no verbose descriptions or bad attempts at humor) — nice twists to traditional problems that tested concepts down to the fundamentals (knapsack that doesn't use DP, LCS with a twist, etc.) No glitch during the contest either.
Nicely done, problem authors and testers!
For others who tried to solve div2E by grouping the numbers by their binary length like me: it's wrong, since $$$(1000)_2$$$, $$$(1001)_2$$$, $$$(1010)_2$$$ and $$$(1011)_2$$$ do not make a tree.
If they don't form a tree, then make them by solving the group. Eliminate the msb of each number and call the solve function on this group.
That may be a good idea. I (and some of my friends) mistakenly think that what are in the same group always make a tree:(
Finally I understood your algorithm. It's awesome!
Nice tests in D1/D2 https://codeforces.me/contest/1446/submission/98467159 https://codeforces.me/contest/1446/submission/98467235
Lol what is this .. same code passes at one place and fails at other ?
Is it normal that the same solution passes a complex D2, but does not pass a simple D1? 98467235 98467159
Hi gamegame.
I feel really sorry for gamegame. The tests of D1 were mostly created by taking only D2 testcases which matched D1's input constraints and a few other testcases to make up for that. It looks like one of those killed your submission :/
Ok.
@kpw29 , In Div1 B, I've got TLE on Pretest 12 in my 2nd submission: 98466019
Then I optimized that & it passed the pretests with 920 ms runtime: 98466474. Now in system test, it got TLE on test 12. But test 12 was under the pretests. What's wrong here?
Edit: Same code got accepted when I submit it after the system test. Submission: 98495086 . Was CodeForces' judging server slow while performing the system test? If that's the case, please rejudge my submission.
We'll look into this, no worries.
Thanks a lot
kpw29 I think it is reasonable to rejudge my submission for problem F. During the contest, my program passed pretest with maximum 7238ms. But during system testing, my program got TLE on test 38, which is a part of the pretest, 98482510. In contrast, I know some contestant who passed pretest with maximum 7488ms but passed system test. I think this is due to instability of judging machine and is not fair. Please rejudge my submission, thanks! By the way, I submitted the same code for 5 times after system test and they all passed. 98494884 98495166 98495208 98495243 98495274
I remember this happening to Marcin_smu. Shit happens. I don't think this pretest-tle-during-systest thing should be rejudged whenever a participant asks for that. In the future though, it would be nice not to get pretest run again at all.
As a writer, I believe this is quite unfair and I hope Mike will agree to rejudge these TLE solutions. We have set pretests=tests in that problem so that nobody fails F on systests...
But you could as well have a few more max tests and it's perfectly possible that one of them hits running time bigger by 0.1% than his maximum from pretests. However stupid this sounds, we can now assume that every pretest is doubled and one instance is in final systests only, so it isn't that bad.
Basically, a participant should optimize their solution if they get 99.9% of TL in pretests or in custom invocation. Unless they accept the risk.
(but yeah, in the long run this should be fixed)
If rejudging isn't the solution, what about making the contest unrated for them if they want? Thus, they won't suffer from this unexpected event.
Problems were great, no changes in problem statement, well balanced problems, short queue, strong pretests and fast editorial . I think we got a perfect round after a long time, thanks for the contest.
My contest submission for Div2 D gave TLE on system test 12. I submitted the same code post contest 5 times, and it passed all 5 times. 98495870, 98498360, 98498305, 98498285, 98498574. If its possible to rejudge my submission, please do so.
Congratulations to jtnydv25 for IGM.
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
If programmers were tools:
How do you like it, kpw29? Your round is a real shit.
Thanks for an honest opinion. What didn't you like about the problems?
Be considerate; this was a good round.
I don't remember last time where something made me laugh so hard as your meme xDDD.
But problems were nice anyway ;). And D was actually quite tricky, I needed to think for a bit about it as well, no reason to be salty for not solving that ;)
I hope the authors will appreciate some feedback.
D1A: Standard. It is the first google result for the search "subset sum problem greedy".
D1B: Standard. It is a minor variation over the longest common subsequence problem.
D1C: Nice, maybe a bit easy but it is not an issue.
D1D: Wonderful problem, I enjoyed thinking about this one a lot. In my opinion, this is one of the rare cases where putting two subtasks was a really good idea (maybe because I solved only the easy subtask...). I spent fundamentally all the contest on this problem and thus I enjoyed the contest! For me, it was super-satisfying to notice that the most common number is the most common also in (one of) the longest "good" substring. Moreover, I like that this single observation is not sufficient, it is also required to understand how to use the observation. Last but not least, the statement is so simple that it gives you the feeling "how is it possible that I never thought about this question?". A wonderful problem.
D1E: Not read.
D1F: Okayish problem, very easy as F. Binary searching the answer and stating the problem as "count the number of segments intersecting a circle" is immediate. The remaining part is harder but not so hard (looking at the tangents is very natural). I am a bit curious on how it ended up as the last problem. Was it very hard for testers?
Let me add that I consider perfectly fine to give somewhat standard easy problems (so the fact that D1A, D1B are standard is ok).
Overall, I enjoyed participating in the contest. Thanks to the authors!
Thank you for such a nice feedback. We really appreciate to hear that!
I am the author of problem F. For both myself and kpw29 geometry is not the strongest suit so we were confident that the lemma needed to solve the problem was very hard.
"Was it very hard for testers?" — no, it was not ;p. I was pushing swapping E and F and didn't succeed, but at least I managed to achieve that their scores were made equal :P
By the way, I really love problem B, I think it is very cute
Hi! Thank you for the comments. From the standings it looks like D1E was significantly harder than 1F. We just thought it's not the case :)
"D1E: Not read." — sad! It's almost as good as D in our opinion (D is my favourite too), we encourage you to take a look and find out by yourself whether it is really that hard.
Btw, your recent contests were great, too!
TIL: After failing 6 times on pretest 3 for DIV2-C, int and long int have the same range. Just had to change long to long long. Got accepted after time.
But can some one tell why do long int and int have the same range when the size of a long(8 bytes) int is double of an int(4 bytes). And long long int and long int have same size but different range ?
geeksforgeeks-c-data-type-ranges
cppreference on fundamental types
It is not guaranteed that long int is 8 bytes in every implementation. In fact, the standard only guarantees that it has width of at least 4 bytes. If you want something guaranteed to have a width of 8 bytes, use long long.
I'm not very sure that the article you linked is correct when it states the range and size of long int. From my knowledge of how signed integer implementations work, the range they gave seem more in line with a 4-byte long implementation. An 8-byte long implementation would have the exact same range as long long in most modern computer systems.
Can someone please tell me why is my code getting TLE on 3rd case? https://codeforces.me/problemset/submission/1447/98493657
auto it = lower_bound(s.begin(), s.end(), p);
change into:
auto it = s.lower_bound(p);
You should use builtin set lowerbound function (log N). This way you're using a default STL one, random access on a set is not supported so it ends up just scanning linearly through the set and whoops, O(n).
.