Привет, Codeforces!
Рад пригласить Вас на увлекательный (а мы постарались его сделать таким) Codeforces Round 748 (Div. 3) — раунд для третьего дивизиона, который состоится в 13.10.2021 17:35 (Московское время). Это раунд, сделанный мной (MrPaul_TUser), существенный вклад в его создание которого также внесли MikeMirzayanov и BledDest.
Этот раунд содержит 6-8 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать сильные тесты — так же как и Вы будем весьма удивлены, если у многих попадают решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Огромная благодарность _c_k_r_, Vladosiya, Ahmed_Salama, BitHashTech, powergee101, ncduy0303, ashmelev, God_Of_Code, OlegZubkov, mahade31, arjunsanjeev7, и SmartCoder за помощь в тестировании раунда и улучшении задач.
Всем удачи и хорошего настроения!
UPD Разбор задач
Looking forward to an interesting round!
Yeah Ofcourse !! good luck man.
Good luck bro!!!
This was really interesting round !! it has created confidence to continue competitive programming...
Hoping for a good contest :)
Looking forward to change my color :)
vrintle to vrintle
Plot twist:
Didn't expected this would be my last Div3 round..
Plot twist again:
Got hacked on E! T_T
I like your confidence, All the best
Where are rest of your heads ? reference
Actually, he is frightened coz dussehra is coming !!! :)
cracked me up lol. good one.
@coder_ravan
You didn't get his joke. Just check the spoiler .. lol
brilliant, bro!
My first unrated round.
Nevermind, but can someone remove cheaters in last round
+1
I know bro... I feel sad a bit and very unfair
Now, I am feeling it . :(
That's not true, in the round before the last one, I got +24 after the contest, getting to 1599, and then, cheaters were caught and I hit 1600! Additionally, seeing this comment, we can conclude that cheaters have been/are being caught for the last round as well. Codeforces staff puts in a lot of effort, please don't belittle it with baseless accusations/claims.
Could anyone explain me about what happened in the last round?
apocalypse and destruction
I became eligible to participate in this round. :P
Hello everyone! Good luck to everyone to write this contest and adjust the rating well!)
-1
VERY UNPAIR
It would be nice to recalculate the rating for honest users.
+1
It is sad(
Did you just say "Shame!!!"? What in the world do you think gives you the right to say that? Even you know that it's not a right thing to say, else you wouldn't be cowering behind an alt.
Please don't ruin the comments section of every blog you see. If there are some issues, create a blog or comment on blogs that already exist for that issue.
-1
Where did you see him say it is fair not to remove cheaters ? Aren't you making up the truth? Do you think it's fun to deliberately destroy the environment of the comment section? Aren't you ashamed of yourself? And you just put the blame on Codeforces?
Don't you know that admins have to do a lot of things every day? And how can you be so confident? Less than an hour? Don't you know how much manpower and material resources it takes to run a website? Do not know how cumbersome it is to process all the competition information of more than 20000 contestants and then calculate the rating? Take your brain before you talk, and don't talk nonsense if you don't understand these things, okay?
Also, can you stop yelling "Remove cheaters! Remove cheaters!" in the comment section of each official blog? You think admins doesn't know these things? Don't know how many contests recently? Don't you know how much admins workload? Please, be considerate of others. You're happy to make others hate you, aren't you?
I didn't want to say anything at first, but I can't stand seeing the comment section like this. I hope this is the last time I get angry about such kind of shitposts.
Sorry for my bad English.
As an ex-admin of several huge online projects, I would like to agree with EasonCF: you can't imagine what enormous amount of work such kind of projects require.
And the subject of the problem is insanely ridiculous: cheaters? Does it really bother you??? Rating? Are you serious?
You've got a lot of great CP problems WEEKLY! Great tests, fantastic database of solutions and editorials, archive, and what are you talking about: cheaters and rating??? Be ashamed!
Big fan of all the positivity you just radiated :)
Can you create a blog for this problem??
Despite my earlier criticism , I have come to appreciate naman1601's light hearted memes under every contest announcement. I would request him to bless us with another light hearted meme.
P.S. He just became purple again. Everyone please upvote him as a congratulations.
Looking forward to increase my rating.
In div-3 do all questions have same score? Like A and F have same value upon solving?
no, rating distribution will be updated later most likely.
no, in Div 3 and Education rounds the scores for all tasks are the same.
oh, right my bad.
It really hurts when rating is exactly 1600 :(
And now you're 1599 lol
Can't say I understand but I guess I can
Hoping to be a blue coder to change my profile picture xD
ah yes, all that's left is to convince my parents to let me stay up till 1am.
Or do I speedrun solving 2 problems in 1 hour, and get deleted?
Best of luck to everyone on this round!
But what if you're a beginner like me who hasn't taken part in two rated contests yet?
it says it'll be rated anyway. we're just being excluded from the official standings, i don't think it'll affect us in any way tho
True.
yes,
I hope everyone can raise rating
That's impossible.
can i get green tonight ?
Only if You're able to solve Problem G (XD)
?
Allfather bless me so that my color changes (to the better side) this time.
Hi, Im New, but what languages will be accepted, like python c++?
both, my dear friend! There are still more language available for you :)
Today is my birthday, and I will participate in this round.... Yoooo
Wish u Happy birthday and High ratings too.
Happy birthday!Good luck!
Wish you a very happy birthday! May you acheive high rating!
Hope my color changes after this round ! )
It's cool that the penalty for a wrong attempt will be 10 minutes
I hope to stay newbie after contest :)
You are an inspiration truly! You are trying hard and didn't give up! [user:Khedr_]Best of luck!
Good luck.
Hoping for change my color =))
As a tester, I tested…
GL&HF
I hope that the penalty of all contests will be 10 minutes instead of 20, not only Div3
I'm not reading Announcement comments anymore.. Man I feel too old
You're old in this platform.
I hope my rating will reach 1900 after this contest Good luck !!!!
lắc lắc con cac nha anh
Any hints on F?
I think it can be solved using digit dp.
solved G faster than rainboy pog
btw G felt too easy for its position...
can you give me idea how to solve G, i got stuck on it used dfs and take max depth of node , give me bad output.
edit my bad i mean problem E sry
dfs? how?
my $$$O(n+q)$$$ solution for pG:
note that we can change between $$$($$$ and $$$)$$$ (similarly, $$$[$$$ and $$$]$$$) at no cost, let's transform $$$($$$, $$$)$$$ into $$$a$$$ and $$$[$$$, $$$]$$$ into $$$b$$$
then we can subdivide each even length substring into blocks of length 2. there are 4 possible blocks: $$$aa, bb, ab, ba$$$.
A block of $$$aa$$$ or $$$bb$$$ cost 0, while $$$ab$$$, $$$ba$$$ cost 1. $$$aa, bb$$$ cancels themselves, and $$$ab, ba$$$ cancels each other. (both $$$abba$$$ and $$$baab$$$ cost 0) so the problem reduced to find how many $$$ab$$$ and $$$ba$$$ blocks are there in a range, and cancel them while possible.
the answer is the difference between the number of $$$ab$$$ and the number of $$$ba$$$ in a given range, using prefix sum can solve each query in $$$O(1)$$$ time with $$$O(n)$$$ preprocessing.
Thanks bro!I never imagined G could be that easy so never gave it an honest try T_T
in pE do DFS $$$k$$$ times result in a worst-case $$$O(nk)$$$ time complexity, it occurs when the tree is also a "chain" (edges are $$$(1, 2), (2, 3), ..., (n-1, n)$$$)
Is D2 about iterating over the numbers which have more than half of the bits set in $$$[1,2^{N}]$$$ ?
you should just get the difference of between every 2 elements in the array and try all of their divisors
Yeah dumb of me to not notice that, btw please accept my apologies I hacked your E :(
That's the evilest thing I have ever seen
How is it TLE when I'm moving from the leaves directly to the next operation leaves
Edit OMG I forgot to add break after i edited my code the last time it was correct
My method:
If any element appears >= n/2 times, answer is -1.
Otherwise: for each choice of reference value a(i) from the array, consider the set of differences abs(a(j) — a(i)) for all j. Where the difference is 0, increment a counter z. Otherwise find the factors of abs(a(j) — a(i)), which can be done in O(sqrt(max(a))) time. Keep a count of how many times each factor occurs. Any factor such that count(factor) + z >= n/2 is a possible answer, and the max of these candidates is the final answer. Remember to reset the factor counter for each choice of reference value a(i). Total time complexity O(N^2 * sqrt(max(a)) )
Solution: link
Nice :)
this was my exact solution lol
hoooolly shit that was intense i accidentally solved D1 like how it should be solved in D2
:( ? Why D1. n<=40 but sum (n) <= 100 ?
Any idea how to do D1? I tried doing it by taking the GCD of all the differences of pairs but I was getting WA on test case 3
first find the minimum element, then take GCD on the difference between the minimum value and each element (except the ones with minimum value).
output -1 if all elements are same.
I guess you forgot to sort array
Sorting array is unnecessary. Any member of the array can be used as the reference value.
You are also required to check if all items are equal. In such case, answer is -1(Infinite)
I checked your solution here https://mirror.codeforces.com/contest/1593/submission/131802472
and you have an integer overflow issue as you use
vll a(n);which expands tovector<ll>of whichllexpands tounsigned long long int.When you perform
a[i] - a[j]and it is unsigned, you must take extra precaution.Quite interesting problemset! Thanks for this round!
Really nice D2
How did you do it?
What the heck is this second test for E?
Edge case when $$$n \lt = 2$$$, output should be 0
My output is 0 for this...
have you checked?
me and my friend have lost this case:)
Not in mine too..
n = 5, k = 1; 1 5; 1 5; 2 5; 3 5; 4 5;
That helped me
Case when 3(or more edges are outgoing from a single edge). Consider the case: 7 2 1 2 2 5 5 6 2 3 3 4 4 7 Removing the first set of leaf nodes, shall not make node-2 as leaf. Your solution does. I had the same problem, figured out but couldn't implement. Your Answer — 1 Expected Answer — 2
oh, yes, it makes sense, thank you!
can someone help me by telling what i am doing wrong in Problem-E
solution link : https://mirror.codeforces.com/contest/1593/submission/131852543
Draw the following case on paper.
1
6 2
2 5
4 3
6 2
1 5
4 5
consider this example.
n=6 k=2
Correct answer:
Answer is 1
Your answer
Answer is 0
I liked the problems, but this is really irresponsible behaviour. I understand sometimes issues may escape the testing phase too, but quietly changing the statement without announcements trying to not address the that there was an issue is not acceptable. I spent a lot of time trying to debug my initial submission, and finally when I couldn't believe that this was incorrect, I tried refreshing the page.
Following up on this, problem E did not have limit of sum of K over test cases, neither had tests which had this large sum. I don't understand why authors didn't put max tests? Weak tests in general on many problems, as you can see from the number of hacks and FSTs.
Isn't this solution correct for problem E
Number of nodes left = total nodes — number of nodes which have distance less than equal to k to the closest leaf node.
Your answer should be 1, but using the above logic, you will get 0
Got it. Thanks
How to solve C?
the cat moves exactly $$$n-1$$$ times, so the total times you can move a mouse is also $$$n-1$$$.
To save as many mice as possible, always move the mouse nearest to the hole first. You can sort the array of the distance of each mouse to the hole, then try to save the mice from the nearest until the total distance exceeds $$$n-1$$$.
Looking at the hacks, I foresee many TLEs on E, especially for those that BFS from leaves and keep track of degree of the nodes
If done smartly this approach is fine. Only perform updates when a node is trimmed, and the total number of updates is equal to the total number of edges, which is N-1. Why should that TLE?
Ok looking closer at the ones that got hacked and unsuccessful hacks by galen_colin (don't wanna tag for no reason), during one cycle of BFS they push the next elements into a separate queue/DS, and then replace the queue/DS. Maybe overhead from replacement is causing the TLE.
Yes I see. I just used a priority queue and did it Djikstra-style to avoid anything like that. That's not to say I won't be hacked though — who knows :)
I think the problem is that sum of k is not bounded and many people (including three of my div 1 Ukrainian friends and myself) just had a
while(k--)loop or something similar.The problems were good but the samples were really weak
samples are not supposed to be strong lol... what's next? all tests are opened?
They could've added a test case for -1 in problem D1
imo, finding of cornercases must be a part of a solution
Imo there is no need for pretests at all let hackers do the deed.
Seriously this round is a joke.
samples!=pretests
They did, I forgot that, got WA on pretest-6.
I know you are impatiently waiting for the editorial, so I've decided to share with you my easy-to-understand solution for problem A.
Wow, very simple and efficient code. But I write all possible way with if else statements that what newbies do.
Can someone help me figure out why am I getting a different output (which is one more than the required output) when on codeforces judge, but when I run it locally on my compiler it gives the correct output for the same test case.
Here is my submission
Because you are including death[0] in your answer. death[0] is not set anywhere, so its value on your local machine may differ to that on the server.
Nice catch, but after fixing that, I have a similar problem but this time a 3 instead of 1, I tested it on my compiler and it gives the correct result,
Submission
PS: I have realised my solution is incorrect but I still want to know the reason for the inconsistency in the outputs for future reference.
It's very difficult to say for sure but I have (recent) experience of similar things and my finding has always been that I've been accessing something that I didn't mean to, or that I didn't think was there, by mistake.
A hypothesis might be that your adj is not resetting itself in the same way online (since you are not explicitly clearing the elements). But I confess I cannot say for certain.
You're setting some
death[i]to be 1, but I think you might be assuming that the others would be 0, which is not correct.Why multisource bfs isn't working in E?
Reading your code, your method appears to be "ans(node) = min distance from node to any leaf". This method is not correct. Consider why this is incorrect with the below case, to which the answer is 1 but to which your code gives 0. During the 2nd iteration, node 1 remains.
1
6 2
1 2
1 3
3 4
1 5
5 6
Got it. Thanks
Can Anyone Help Me Out to find why am i getting wa for problem E ,My Submission : 131857557
You also fail the case mentioned in this comment
These types of Solutions are getting hacked with TLE, but it doesn't seem to exceed TL. This is O(KlogK) solution. Perhaps this is because of Java?
Correct me if I am wrong. Thanks.
I don't use java much but Arrays.sort(a) in java has worst-case time complexity of order n^2. Therefore the worst-case time complexity of your program is n^2 which gave tle.
You can read more here
Oh okay, thanks for the information. So there are more chances of java solutions getting hacked whenever sorting is needed in the solution, right?
Yes, you are correct. I have seen tons of solutions in java getting hacked on codeforces due to Array.sort(a). You should switch to Collections.sort(a) or suffle array before using Array.sort(a)
Array.sort(a) uses quick sort only on primitive data types. So if there is no primitive data type Array.sort() is ok.
An example of Collections.sort() can be seen here in the SecondThread solution
Notice that he uses collections.sort and fastio for speeding up the code. Collections.sort() wont get hacked as the worst case of it is nlogn
Anyone else with the following on Test case 2 for E
wrong answer 37th numbers differ - expected: '1', found: '0'?What is this test case possibly? I did multi-source bfs starting with all the leaves of the tree.
I have this WA too, but i did dfs from a random leave
Yours gives 0. Ans should be 1
Edit: My bad k >= 1
1 6 2 1 2 2 5 5 6 2 3 3 4 The ans should be 1. Multisource bfs gives 0
Can't understand the test case. What is n and k here ?
6 and 2
try only pushing those nodes which are connected to the current node being processes(u) after removing u from the tree in the multisource bfs. If you didn't do it this way!
Video Editorial of E (Gardener and Tree)
It seems that D2 has many suceesful hack. Is pretest weak or some conercase ?
when I run this code on some other compilers like gfg ide, visual studio I get correct O/P for sample test case 1st but on codeforces I am getting W/A on test case 1st, IDK how this happens ??
Code:
https://ide.geeksforgeeks.org/zN7ERcyWaB
Try with language GNU G++17 9.2.0 (64 bit, msys 2) .
Anyone solved E in O(n) by finding 2nd largest length from every node to leaves?
Nice idea :)
I think your algorithm is actually O(K + N log N) though. You use set (insertion log N). I think this explains your long run time — set is slow and you perform a lot of insert and erase operations.
If you wanted this to be truly O(N) you could store, for each node, just the two greatest distances you currently have, and update them in place without need for actually sorting (either through use of set or otherwise).
I brute forced like everyone.
Yup! I did just now
Why there is so much hacking in E? Which test case it is failing???
The majority of hacks seem to be time limit related, where the user has, K times over, created a whole new queue which could have size of up to N.
How though? I believe only the new leaves would be added to the queue and that should be of the order of the nodes since any leaf would be added at most once.
Sorry for the poor variable naming. Link to submission
Nice problems, but weak testcases. Thanx.
Were the weak tests on D1 and D2 on purpose? MrPaul_TUser
Some people hacked a lot of solutions, it's hard to read a lot of solutions (at least for me) and find which ones can be hacked and which ones are not.
I think there is a way to test a lot of solutions automatically. Is that true ? and is it allowed ? and do you have any idea how to do that ? it would be great if you can help.
I got wrong on TC2 on C (my submission).... Please help!
If you would like a testcase that fails:
10 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999It has to do with not checking for your vector being out of bounds when you incremented
i.Here's my Solution to E 131874293. Do you guys have a better approach or this solution is fine.
I think the algorithm itself is fine, and the implementation has room for improvement.
degis not necessary, you can usear[i].size()instead.leafsandnew_leafscan actually bevectorrather thansetAnd consider output
'\n'for new line instead ofendlsinceendlflush the output buffer each time, which may make the running time longerYou can refer to my submission, which has basically the same algorithm as yours and has 3x faster in running time.
Thanks for your time, also isn't set better for removal of leaf nodes.?
But in
leafsandnew_leafs, all removals are removing all elements, which is actually clear the set.If you need to remove individual elements, using
setis better (so we usesetnotvectorfor the adjacency list in this problem).I have a serious concern about the problem A.
Is it fair to allow such submission getting AC?
To compare, this one gets TL. Of course, the only difference is the line 3:
#pragma GCC optimize ("O0")I guess that checker must prohibit the loop elimination explicitly when compiling the solution, because that's what GCC does in this case.
Would be nice to listen to the contest authors' opinion. cc MikeMirzayanov MrPaul_TUser
Well, I'm kinda confused with people's reaction. Could somebody from those who downvoted to comment on that?
Why in the world would getting AC by this submission not be fair? Modern compilers nowadays apply an overwhelming number of optimizations, you cannot know all of them for sure. Which of the optimizations must be considered "unfair"?
Loop elimination is one of the simplest optimizations a compiler can do. If G++ is able to do it while others are not, well, one has to blame the other compilers for that.
I didn't tell the optimization itself was unfair. And I know well what compiler optimization is.
Also, I didn't participate the contest and I don't ask for some other people's solutions to be retested, etc.
I'm just pointing out that the solution which presumes 10^13 operations to be performed gets AC verdict.
Moreover, it does perform those when being compiled with -O0 or -O1. I guess, there's also some sort of flag to disable such optimization while having -O2 or -O3 enabled too.
So my intention was to raise a question about potential elimination of those optimizations while testing a solution.
Why? Because the compiler must not influence the correctness of the solution. And the solution above is wrong indeed, it must not be accepted as a valid one, IMHO.
The solution is not wrong. It gives correct answers for all the tests. If it is compiled without optimizations, then it will get TLE, but it does not mean that it's wrong.
But the question is: where is the margin between optimizations which influence correctness and optimizations which do not?
If you really want to be sure that your code will not be affected by obstinate optimizations, then write code in the assembly language. The processor will unquestioningly execute all the instructions you would write.
After all, this is not a theoretical olympiad in informatics where participants are supposed to describe the algorithm and prove its complexity. If we code in high-level programming languages, then it's essential for a compiler to speed up the code wherever it's possible.
The fact that it gets AC for all test doesn't mean it's not wrong.
Of course we can't answer this for sure, but at least loop elimination prohibiting could be a good place to start.
I don't insist on it, I was just curious of the authors' opinion.
Anyway, what motivated me to start this conversation was getting AC by the wrong solution, and I'll keep claiming it is wrong just because it's not completely correct (whether or not you agree with such interpretation).
Once again: the solution is not wrong. It's slow. It's a slow correct solution. Not all correct solutions are supposed to fit into the time limit, as well as not all slow solutions are supposed to be rejected. Some of them may pass, though.
Sorry, but this is not a constructive way of discussion.
Here is the discussion on turning on some optimization flags (-O3, -funroll-loops etc.) for G++ by default on Codeforces. You can't stop progress.
Has anyone done F using meet in the middle technique, instead of using normal dp. In which divide the string into 2 parts and checking each part individually ? I tried but got TLE in TC 7. Though I think it will pass if 2s is given as approx complexity is $$$O(2^{n/2}*{n/2})$$$
Can 131830101 be hacked? I didn't stop the
while (k--)loop even after the queue (qin my code) is empty and my solution has extra $$$\log N$$$ factor because ofstd::set.after
qbecomes empty thewhile (k--)does nothing (and won't consume a lot of time) because thefor (int sz = LEN(q); sz > 0; --sz)inside yourwhile (k--).Can somebody please explain where I am going wrong in problem E?
My Submission
This code is giving wrong answer on Test 3.
My Approach:
First, I found the centroid of the tree. Then I ran a DFS from this centroid and maintained an $$$ans$$$ vector where $$$ans_i$$$ will store the number of operations after which $$$i^{th}$$$ node will be removed.
1. ans[leaf node]=1.
2. ans[node having only one child] = ans[child]+1.
3. ans[any other node] = Second_Max(ans[all children])+1.
I am taking second maximum because for a node having $$$C$$$ children, atleast $$$C-1$$$ of its children must be removed for this node to become a leaf node(removable).
Final answer will be number of nodes having $$$ans[node] \gt k$$$.
Thanks in advance.
oooooh! Don't know where is the error but the logic is extraordinarily..
Can you prove that taking the centroid of the tree is always correct in your solution?
Well, it was kind of a intuition. But I think about it this way, since centroid is kind of a balance point because it divides the tree into forest of subtrees with size at most half of original, so centroid must be last one to be removed if we follow the procedure from the problem. Please correct me if I'm wrong.
Hello everyone here, Yesterday I solved 3 problems and got an accepted verdict. Today about half an hour back it still showed an accepted verdict. But now 2 out of 3 problems are showing a queue verdict. May I know the reason for this?
Just system testing all the submissions. Don't worry.
We tried to make really strong tests — just like you will be surprised if many solutions fail after the contest is over.
You intentionally gave n <= 40 in d1 where O(n) soln is easily working just to mislead participants in directly using brute force without much thinking , however if u would have given n in range 1e5 then this thing wouldn't have happened , so it is really not expected from ur side , And also in problem C , u gave time limit 4 seconds and as a result of which some O(1e9 range) solutions got accepted and now they failed system tests.
Just because of your really strong tests i got +2000 my expected place since i solved d1 before b and c so it was really disheartening to see :(
Those who are downvoting will get to know how it feels when it happens to them :)
That's your problem. They all remind that passing pretests doesn't mean to pass system judge :))
When you will be at the receiving end you will understand. I hope you will remember what you preached at that moment.
Accepted.
TLE.
Just changed vector with array and now it is accepted. It feel very bad (T_T) During the contest my solution was accepted and after systest it gave TLE). First time I had got under 2000 rank. It was meant a lot for me. And now this happened because of vector vs array:|
Always, prefer to use arrays rather than vectors.
PS: Do anyone know how to use vectors as fast as arrays?
PS: TLE code
acceptedon removing#define int long long.PS: But, creating dynamic array example:
int*m = new int[k + 1];gives MLE. 131911303PS: Global vector working fine.
By the way nice contest ^_^. IMO there should have such testcases during the contest so that we can correct this things during the contest.
You were using a map, not vector.
Dear MrPaul_TUser and MikeMirzayanov
Testing the D2 question cases seems very inappropriate !
See my submission , it gets wrong on test 56! While it received accept in pretests. It costs me a sharp drop in rankings so from near 1500 i become 3500 because of weak testcases! So i really please you to reduce the testcases for D2 and rejudge this question.
131848968
You mean your code fails on a certain testcase meaning that your code isn't correct within the given constraints and hence the testcases which your code can't handle should be removed?
Nice
Can anyone explain why my submission causes RTE, please? 131823111 Same code in Python3, I passed test
Technically, in C and C++ (and most other languages I guess), any integer other than 0 is considered true, so your comparator function that you passed into the sort function to sort your input in descending order is not working as intended, I replaced
return a.first - b.first;withreturn a.first > b.firstand the code worked perfectly.I can't get over this that was my best performance since I started on this site I had a break command in my previous WA submission for E and i fixed everything but deleted the break by mistake it passed and got hacked :'( I could have reached expert without that stupid break command went from 250 to 670 someone give me 10 bags of tissues :'( :'( :'(
Don't worry man. Just do your best next time.
dont worry bro! soon u ll become expert
When will the rating changed?
When will the rating changed?
System testing has not finished yet for God's sake!
I just saw it finish, and now it 99%.
Why do I see this contest in my unrated contest. My rating is < 1600
The rating hasn't updated yet. You need to keep waiting for a while until the rating get updated.
You may be not a trusted participant because you played only one rated round before this one.
Sorry, now I see you have already played 2 rated rounds.
I often see it is written in the open hack or system testing phase that only trusted participants. What does this mean?
Read the announcement carefully and you'll find:
When will the editorial be released Waiting for the explanation of D2 and E problems
Well, I have waited for 4 hours from the open hacking ended. However, I didn't see any signs about rating. I'm very nervous and I want to ask when will Codeforces rate? Thanks and I know a lot of people are waiting like me =))
Now it has been updated :)
i am wondering(HELP) what is the significance of n is even in D1 problem
Nothing. This detail is more important in the harder version, D2.
.
Can we use meet in the middle for D2??
Possibly someone smarter than me will have a way but I can’t see it. For me this is brute force over all possible smallest values of your set where you try to find the largest factor which exists in N/2 of the differences with that element (itself included).
Now, I think that (meet in the middle one)approach would result in TLE since in that approach you will divide the array into 2 equal sizes and look for all possible subsequences that would result in TC(2^20) which is roughly 10^6 and if you try all possible values of k you will get TLE
No, that’s not how it works. See this comment
In problem C: "The actions are performed until any mouse hasn't been hidden or isn't eaten."
That should be while not until. Every programmer should know it regardless of English proficiency.
Congratulation @Viettran, 8528190072TuanHD
It's sad to see that top1 and top2 in div3 are cheaters (U need to use unofficial leaderboard to see them). They have multiple submissions to different problems within one minute using completely different templates xD MrPaul_TUser maybe something can be done about that, althought I doubit it.
I have given all three rounds made by you MrPaul_TUser and personally found all this rounds very interesting now I am excited and waiting for your next rounds and thanks alot for writing such nice and interesting problems:)
I have solved the problem E in the following way, however getting TLE #4. Here's the solution.
I'm maintaining a sorted set of pairs of vertexId and its adjacency list (in fact, set in the implementation). In each operation, removing pairs from the set where the adjacency list size is one. And also removing it from its the only neighbour. And this solution gets timelimit but I believe it shouldn't have very bad complexity.
Actually the constraints of n and k both are 10^5 . But the interesting thigh which we have to notice in question is that author only given that the sum of n over all test cases will not exceed 4×10^5.So if you solve this problem in O(n) then it will be O(n) only but if you will solve this question in O(k) so actually you are solving it in O(T*k). That's why your code is getting TLE. I hope that I cleared your doubt if not then let me know I will try to elaborate it or simply it.
Well, when the sorted set is empty, I break, it shouldn't go over n, even n/2 operations as in each operation there are at least 2 leaves/vertices erased. I think my solution is O(nlogn) due to the sorted set.
Yes, Actually sorry I didn't read your code completely so I thought you are not breaking that for loop of k. If you will get the reason for which your code is getting TLE then please also let me know. It will be informative and helpful for me also :)
When will the editorial be released?
There is a brute force solution for D2 that passes https://mirror.codeforces.com/contest/1593/submission/131966435 . Did you intend for optimally written brute force to pass for D2 ?
ok
Your comment was very funny, so I checked your profile out of curiosity. Useless code inserted to avoid plag checker (successfully in many contests). I didn't expect you were a cheater. What a plot twist.
According to here, the editorial should be posted no later than 1 day after a round. So why the editorial of this round hasn't been posted yet?
just my opinion nothing else:
G would have been worth of its position if the changes made in the initial queries were permanent and had to be carried on for the next queries , bcz at present its very ez and can be solved with just a prefix array after getting the basic intuition , should have gone to G instead of F during contest :sob
thnx for the contest authors! eagerly waiting for editorials :D
Can anyone help me why this 131912878 fails for problem E ?
Editorials???
No Editorial till now
2 days and still no editorial . WTF!!!
I hope to be blue before the editorial is published
someone know why I get TLE for this java submit 132153643?
It's totally same solution with my c++ submit -> 132153310
It's java Multi-dimensional array performance issue. See this stackoverflow page
Get AC for java by this submit also 132176082
Both this announcement and the editorial do not seem to be attached to the round.Thanks for the round!Update: fixed already.
why rating havn't change after remove cheaters? i think it should increased a bit
About my code similarity with user "grafOn". That is my second account that i use for checking if my code is right and right after that I submit that code on my profile. I didn't know that was breaking the rules. I am sorry for that. I don't know how to prove to you that it is my second profile. Please tell me if i broke the rules of CF.
read the
Terms of agreementI read it, but there was nothing about having two accounts at the same time. I just don't understand why i can't submit the same code on two accounts during the contest. After all this two accounts are mine and there is no second person that coding and submitting the same code as mine.
I just don't understand why every LGM does not make 10 alt accounts and stay on top of the leaderboard themselves :)
Well you yourself are the second person. What you are doing is checking if your submission is correct so you don't get a penalty on your original and can stay on top of the leaderboard. You are registered as 2 different people in the contest.
Next time when you click register for a contest, try reading what the box above it says.