Hi everyone!
Codeforces Round #357 (Div. 2) will take place today on the 14th of June at 19:35 MSK.
I am the author of all the problems, and this is my first round on Codeforces. I hope you will enjoy it.
I'd like to thank Gleb GlebsHP Evstropov and Dan danilka.pro Sagunov for helping me in preparing problems, Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms, and also Demid BLIZZARD Kucherenko for writing alternative solutions.
There will be five problems and two hours for solving them. The scoring distribution will be announced later.
UPD
Scoring: 500-1000-1500-2000-2500
UPD
Congratulations to winners!
Div. 2
Div. 1
UPD
Good luck, high rating and good mood to everyone!!
Exactly, short and pretty much sums up everything!
Why this comment be deny as Negative?
Because big font is too ugly.I guess it.( ´థ,_‥థ`)b
This contest is helpless. Because it is first of yours. Give it to a more experienced one.
Everyone's got to start somewhere; I think you're being a bit harsh.
You should applaud his effort, and judge him when you actually see the quality of the questions. If they don't fulfill your expectations, then I would recommend giving constructive criticism so that he may improve in the future.
That being said, thanks for the contest, .tx and others!
He's not even being a bit harsh. He's being too harsh. We have to call a spade a spade.
.tx Thank you and i'm a confident that this contest will contain a nice Problems
And this contest really did have some good problems.
No he is not being harsh he is just a troll I suppose if you do not believe me then look at his past blogs.
Everyone is deserved to begin.
And you deserved to be down-voted.
Seems like his spam comments have come back again...
learn English, then start judging people :3
his English is better than yours :P
I didn't say mine is great :v
This way no contest would be ever done, cos' at the very beginning there were no experienced ones. Just think about it.
If problems were this bad, I think GlebsHP and danilka.pro would have enough experience to knowing it and would advise .tx to change them.
And even if the contest has a different difficulty from previous rounds, you can't make perfect contest having always the same distribution of solved problems. Some contests will have really hard problems and some will have easier problems who privilege fast solving.
Why you participate in CF contests if you can't solve div 2 D?
nice dp!
If you think I will get the first rank in this contest, please vote me. If you don't think so, please vote me too!
It seems to me like you're intentionally trying to tank your contribution, you're already the individual with the 15th lowest contribution score...and now you're tied for the 14th lowest.
Please edit your template. From previous round it says "The contest duration is 2.5 hours, it will contain 6 problems." :D
The comment is hidden because of too negative feedback, click here to view it
You are a cheater!!!!!!
are we gonna see another interactive problem???
Im Gay.
Congrats :D
Wow! But i don't think its the right place to announce it!
I enjoyed Codeforces Round #350 (Div. 2) ( 6 problems, 2.5 hours).... Will it happen again?
Thanks for the contest.Excited to solve good problems.All the best everyone.
Good luck for everybody !!
I wish my rating change into 1700+ ^_^.
Oh, it is good that you will be better than me.
Wish you improve your rating ^_^
sorry, I will be the first of this contest!
..........
I am very eager to see this.
So am I.
come on, baby!
Man this is my first contest in a while. May the power of Egyptians and Indians be with me.
Egyptians aren't enough!
may allah be with us :D
The comment is hidden because of too negative feedback, click here to view it
I think you mean click here to view it.
Any news for those who had their rating mysteriously decreased?I was in div1 but after decrease I am in div2,how will this contest affect me?
fixed already thanks
Me too. But color still same.
GOOD LUCK EVERYONE!
feeling great!! my first ever contest on codeforces
I hope greedy approach does work in C :\
Anyone solved problem D using HLD?
My topological sort passed pretests, but I hope it won't pass systests, because this is really silly and weird solution approximately in O(N2) I guess. And, by the way, what is HLD?
Heavy Light Decomposition
See this
Wow, that is awesome!
Oh, I never heard about it yet.
You didn't need to find LCA (or compare nodes depths).
Firstly, one can prove that anyone who receives a gift must give a gift to himself. If not, the person this person received a gift from would end up giving it to the person this person is going to give a gift to, as an ancestor of an ancestor is an ancestor.
Secondly, we can prove that there are no receivers between a receiver and its givers in the ancestry tree. If there were, this receiver in the middle would either intercept the gifts from the higher receiver's givers (being on top of the list) or become a giver to the higher receiver (which is impossible if he is a receiver, as receivers must give to themselves).
Thirdly, we can prove that there are no gaps between receivers and givers. The case of a receiver in the middle is covered in the second step. If a giver were to be in the middle, the giver's receiver would necessarily be an ancestor of the original receiver. This would either intercept the original receiver's gifts (being on top of the list) or be intercepted by the original receiver (being below him). Therefore, as neither givers not receivers are allowed to be between a receiver and its givers, we can conclude that there are no gaps between receivers and givers, and that a receiver and its givers produce a complete tree.
Therefore, it is sufficient to check whether each giver of a receiver's parent in the ancestry tree is either another giver (for this receiver) or the receiver and that each receiver is not in turn a giver.
After that, a simple bottom-up (in the ancestry tree) printing of all the receivers suffices.
I'm not totally sure if I'm correct, but I guess systests or one of you might point out a problem with my proof ;)
Thanks chaosagent.
I ended up solving it using preorder traversal + segment tree, though I was sure there were simpler solutions.
However, my first solution involved HLD but didn't pass pretest #5 because I didn't do DFS properly from the roots.
Here's the corrected solution using HLD: 18478224
Mine got TLE cause it's a little bit slow(constant factor may be). My Idea was first sort the gift array based on each node's level. Then check for every node from left to right if it has an ancestor(except itself) who received a gift before. After checking I update the current receiver node.
UPD: There were some bugs on my code and my idea was not properly correct at all.
Your idea is on the right track. After the contest, I found the simple solution that I was supposed to find during contest.
Check out code for more clarity: 18483927
Welp, I'm fucked. Pupil status, here I come. :/
How to solve B and C?
Me too. ;)
Next one goes better hopefully. At least we'll have nothing to lose. :D
For B, for a = 0 to 1000, b = 0 to 104, find c and check the condition will work.
For C, a simple greedy sort of thing will work. Keep processing the queries in order, and do the most natural thing that you should do.
for a and b: 0 to ...
How to prove that C is correct?
Here is the language for the proof.
We have 3 possible operations O = {I, R, G} (I = Insert, R = Remove, G = Get).
O — mutating operations ( make change ).
O — accessor operations ( without change ).
O0 = {I, R}
O1 = {G}
All the operations can be viewed as a list:
Operations[10] = [I, R, G, I, I, R, G, I, R, G]
We can imagine that the list Operations was generated randomly.
That is, at first we have a list of size 10 with empty elements (placeholders):
Operations[10] = [a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
Then we go through all 10 elements and choose the value ai
O randomly.
There are 310 = 59049 possible lists of different sequences of size 10.
The minimum number of new operations that we need to introduce is 0 (when the sequence of Operations is valid).
Otherwise we have to insert ≥ 1 mutating operations from O0 = {I, R}.
Now, what is the maximum number of new operations? (0 ≤ optimum ≤ maximum)
These operations are not setting any constraints for us:
Operations[10] = [
I
, R, G,I
,I
, R, G,I
, R, G]The other operations want us to satisfy some constraints.
Man, I kept messing around with Linear Diophantine Equations for B, but couldn't get much from it. :/
I think I was doing the same for C but kept getting wrong answer. I think not getting B might have messed me up.
Ah well, next one I guess.
I used Linear Diophantine Equations >.< only to realize this was an overkill CODE edit: GOT WA ;_; anybody who used Diophantine and got AC?
same, thought Bezout's or gcd will get me the answer, but realised 1234567 was
primecoprime with other two and plus problem needs non negative solution.It was too late and I resorted to brute, and got TLE on system tests
C, implemented in last 10 mins in hurry,I pushed insert operation to my answer vector, forgot to perform it on multiset, WA
Instant AC after the system tests with the correction.
I need to practice a lot
Man, 1234567 is not prime!
Look 127 × 9721 = 1234567.
Corrected, thanks.
there was a guy in my room who used 1000 and 100 instead of 10000 and 1000....he got the pretests passed....I tried to hack him but unsuccessful :(
His Code
Can you give me his nick or tell afterwards if his solution passed the final tests?
nick — biltharesatyendra
max(a) could 10^9/1234567 = 810 , max(b) = 8100 , iterate two loops for a and b for (0 to max(a)) and (0 to max(b)), check n — a*1234567 — b*123456 for being divisible by 1234.
Aren't max(a) = 811 && max(b) = 8101?
Yes, I thought that'd be obvious. My loops ran from 0 -820 and 0 -8200
I had first tried bruteforcing with a, b, c in loops in that order, but got TLE.
Then, I solved by taking c in the outermost loop, b in the middle loop, and a in the innermost loop and passed the pretests. I just hope it gets accepted. :(
For B, you can just brute it, but skip the 3rd for/while loop because it's enough to ask if((n — a * 1234567 — b * 123456)) % 1234 == 0) {cout << "YES\n"; return 0;}
Since n <= 1e9, a will iterate aproximately n / 1234567 iterations, which is about 10^3, and b about n / 123456, which is about 10^4, so the overall complexity is in the worst case O(10^7)
How to solve D?
Check that each node wants to gift either itself or the same as its parent. Then sort all preferences by decreasing depth and uniquealize.
My idea is same at yours but I didn't take care of checking your first condition since it's guaranteed. But I got wrong answer on test 6.
I got WA on 6 when I made unique wrong.
Which condition is guaranteed? It is only guaranteed that a guy wants to gift his ancestor, not his direct parent.
"The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n), ith of which means that the man numbered i wants to give a gift to the man numbered ai. It is guaranteed that for every 1 ≤ i ≤ n the man numbered ai is an ancestor of the man numbered i."
Sort the a array in decreasing order of levels. After that you should just check whether the condition mentioned in the problem is satisfied or not. If no, print -1, otherwise output the sorted a array.
and how do we check the condition is satisfied or not
Once you get the order, iterate through the order i = 1 to k and keep filling the answer as order[i] for the subtree of order[i]. Once you have done this just check if answer[i] is equal to gift[i] or not.
or just I need to check
either gift[i]==i or gift[i]==gift[par[i]]
BTW nice dp :P
I have an idea but could not implement it in time. The sufficient condition for the answer to exist is for each node u, the path between u and target[u] does not contain another target of another node. If the condition is satisfied, just print the target nodes decreasing depth.
Why is this wrong for D?
Check for all nodes i that none of their ancestors have a A[node] lower than A[i] in the tree, if so, print -1. Otherwise, sort A[node] according to their depth in tree in reverse order, and print them. This gets WA on #5. Why? Code: 18475103
You are not checking whether the node is the root of the tree or not before calling dfs.
I used the same algorithm as yours and WA on #5 too……
It is here:
You want to start dfs'ing from the sources (vertices, which has no parents), otherways you will be unable to compare vertices correctly.
Same error hit me too.
Making an array unique is so hard :/ costed me 8 WAs in D
First I haven't read "distinct" in output format, and then I sorted nodes by depth and somewhy assumed that std::unique will do the job. But if e.g. 1 and 2 have same depth then 1,2,1 will not work for unique..
You don't have to make it unique — you traverse from the leaves and once you reach the vertex, where gift[nr] == nr you add it to the end of the list — complexity is O(n) but I used set in my solution for simplicity :)
Edit — and obviously when you go from the leaves, you just check if the relationship is ok and you add to the result once you reach an appropriate node (which gives a gift to himself).
Nice observation
How to solve div2 B i got hacked two time:(
bruteforce
iterate among possible a and b, then if c exists: yes
I saw a person who iterated a, b and c! I wonder if he will get TL in the end.
He has to.
511 operations is huge.
But he didn't.
Then we have only 2 options:
1. Magic happens.
2. Sometimes compiler does a good job with optimization.
Я думаю, дело в том, что там есть выход из циклов, когда ответ находится, и ответ для всех чисел находится быстро.
Not if the bruteforce is optimized through reverse order --> http://mirror.codeforces.com/contest/681/submission/18473017
n = a * 1234567 + b * 123456 + c * 1234
If u look closely , then u will get that the value of a can not be greater than 811 and the value of b can not be greater than 8110 , so use nested loop and then try to check if ( n- ( i*1234567 + j*123456) )%1234==0 : then YES
Why value of a cannot be greater than 811 ? how i can see it during contests ?
bcz 1234567 * 812 > 1e9
For D, I think it's correct that each guy must either prefer himself or his parent. Furthermore, if a guy prefers the parent, then that parent cannot prefer his parent. So you just get the BFS order of the nodes, reverse that, process in that order, be mindful of these impossibility conditions, and add a node to the list whenever someone preferred it. Also, the initial graph is a forest, so you should run this process on each tree.
Is this correct?
The guy can prefer his ancestor, and all other guys between him and that ancestor (including him) must prefer the same guy — basically every node on the path between the preferring and the preferred must prefer the same guy.
Stupid mistake with C coasted me 9 WA!!! i fell sad, and stupid :(
Mind saying what it was ?
getMid x
if x is greater than the previous min, i kept deleting numbers from my priority_queue until it is empty :(
I should have kept deleting until (-qq.top()>x) and then checking if pq.top()==x
Nice Problems altough some are hard but it was a nice experience couldn't manage to solve them but learned some stuff on the way .
problem c testcase 10?
Try this one. I found it, corrected the mistake and got passed. 3 insert 10 getMin 0 getMin 4
FWIW, I failed pretest 10 on my first submission using Java. Switching out Scanner for FastIO was enough for me to pass (982 ms!).
Edit: TLE on test 10 during system tests though...
Why did I get Wa6 on D? http://www.codeforces.com/contest/681/submission/18466813
I think the vector apot is not guaranteed to be sorted because for each vertex verat you reach you push back a[verat] (if it's not already there) which can be at any level higher than or equal to verat's level.
consider this case :
3 2 1 2 1 3 1 1 3
In the previous case if you reach vertex 2 before vertex 3 then vertex 1 will appear before vertex 3 in the vector apot which will give WA.
One second erfaniiyan , one second. . .
I think there will be quite a lot of fails on C due to absolute value as 10**9. Many had minimum as 0 :s I was gonna hack such solution but i locked during last few minutes....
Anyone have tricky test for C? =)
4 insert 5
insert 4
removeMin
getMin 2
I can't understand what is tricky there.
Took me 15+ minutes to understand problem D (english version). Such description... much wow!
Can anybody explain the statement of D, please. From the statement — "Each man has at most one father". Further — "The next m lines describe family relations: the (i + 1)th line consists of pair of integers pi and qi (1 ≤ pi, qi ≤ n, pi ≠ qi) meaning that the man numbered pi is the father of the man numbered qi".In first test case we have input 3 2 and 1 2. It means the man numbered 2 has 2 fathers. I don't undestand this...
3 2 is the value of n and m :P
LOOOOL. Thanks.
The first line "3 2" are the numbers n and m respectively. The next m lines are the family relations, that is:
Btw, just sharing a trick with you to view submissions even when system testing is pending and viewing solutions is disabled with normal UI.
Just copy the submission id from status, or get it from click on the link showing number of submissions against the problem. e.g. anta's E submission id is 18470158.
Now open the url http://mirror.codeforces.com/contest/681/submission/18470158.
Change the submission id accordingly and have fun !!
Thanks for the contest guys. It would be better if the stories were not that long.
how to solve B ?
Check every combination of a and b (a is up to ~810, b is up to ~8100) and then check if (n — a * 1234567 — b * 1233456) % 1234 == 0.
Very nice sample!
Does anybody have an idea of the following code that occurs memory exceeded?
include <stdio.h>
include
include
include
include <assert.h>
include
include
include
using namespace std;
typedef long long int lld;
void solve() { int N; scanf("%d", &N); vector<pair<char, int>> res;
} int main(void) { solve(); }
What is up with the super strict TL on B?
My solution using 108 operations got Time limit exceeded. This is really unfair, this is expected solution, it should pass.. :/
Submission: 18459463
It wasn't very strict. In your code if you use 1234567*i<=n instead of x or calculate the maximum which is only about 810, the operations are less than 7*10^6.
But 10^8 operations always work easily on CF in a second.. :/
I would argue that for a 1 second problem 10^8 is pretty pushing it to the limit. You could have checked for the worst case before hand, i.e. not use the return 0 and use clocks.h or GetTickCount() of windows.h to get the time.
You pushed the limits even further by using long long rather than int. My code and your code is almost same. 18464576
I was worried about failing the system test but luckily I didn't!
Maybe 10^8 slow
%
operations withlong long
are too much even for codeforcesMaybe, not %. increment is slow opertation with long long
Do you want to say
+
is slower than%
?How I say, yes. But it was my mistake. % is slower than increment. I think that % isn't use in all operations in code.
You are correct.
%
takes 49-135 clock cycles to compute.Those division instructions alone take 10^8 x 50 / 3x10^9 > 1 second already.
Problem C: WA On test 31 :( :( http://mirror.codeforces.com/contest/681/submission/18464083
Tnanks for letting us know about that :|
o.O xD wanted to know the reason why!. Was too impatient to wait for whole system tests to end :\
Because the heap is empty while it should contain 0 as the smallest number.
Wow!!!!eventually,That was very good contest with increasing difficulty.Thanks for the contest.
Example input data for prob. A
Applejack 2400 2400 Fluttershy 2390 2431 Pinkie_Pie -2500 -2450
I wonder if the other pretests have the other Mane six.
priority_queue in C gave TLE :(
Not really, I did it with STL priority_queue too.
Leave aside C++, Priority Queue based solution passes in other slower languages too..I solved it in Java using PQ. There is some other issue regarding ur code..
Maybe I'm just a "purist", but I don't think the difference between a TLE and a correct solution in an algorithmic programming competition should be caused by IO or other constant factors.
It's quite disheartening to come up with the right solution but then have it judged incorrect.
the problem statement must have at least mentioned to use fast I/O.
I got AC with STL priority queue. My solution is really similar to yours, the only difference is that I used scanf/printf and you used cin/cout (with endl).
use "ios_base::sync_with_stdio(0);" with cin/cout. It will work more faster then normal cin/cout.
No, not priortiy queue, cin/cout gave TLE. I too used priority queue during the contest and got TLE in the final systests. Resubmitting with scanf and printf gives AC. Some have used sets for this but even they got TLE because of cin/cout. The time limit was too strict. :'(
When using input/output functions at most 10^6 times, you really shouldn't be using cin/cout even with std::ios::sync_with_stdio(false)
In my opinion, when one has got the right complexity, the solution should get accepted irrespective of whether you use cin/cout or scanf/printf.
I got TLE too :( with cin/cout but now I had resubmitted the same code with this 2 lines:
and I got accepted :`(
Now it got WA
Yeah wondering why is that ! :P
http://mirror.codeforces.com/contest/681/submission/18469930
I passed it with 982 ms, so close! I checked a lot because I saw I was doing the same thing as everyone else. And the culprit was to_string! When I changed my code to not use to_string it suddenly ran all the tests in 200ms!
just see the small difference here:
http://mirror.codeforces.com/contest/681/submission/18478570
http://mirror.codeforces.com/contest/681/submission/18478627
EDIT: Deleted this link as this was me doing a test with string streams instead if ever needed to do stringcasting later. This was also faster, but still costly
http://mirror.codeforces.com/contest/681/submission/18479133
I think the data for D is too weak. My submission should get a wrong answer but survived to remain correct in the final standings. I made a mistake with taking care of my dfs in the main function, exist should have been initialized as true, and later become false if one of the dfs returns false. Mine just takes the value returned by the last tree. In a test case with multiple trees with the wrong tree being in the middle, and the last tree being correct, this solution would still say that a list exists.
18470729
It is like
smurfs everywhere :'(
My problem C got TLEd. I was using multiset. I have seen other solutions which have passed. I strongly feel that my solution should ideally be accepted. Time limit was strict in my opinion. In the contests where feedback about problem is shown at the end of the contest and solution was well under the time in pretests, it is really tough to figure out these kind of things.
Same here, I suggest rejudging for problem C but has that ever happened before?
Maybe you used slow input? I used multiset and still got accepted.
You have TLE because you used
cin cout endl
.I have mostly got my solution passed with cin, cout, and endl. I get really sad when I get TLE due to these issues. People are generally supposed to think that these things are fast enough.
What is mostly passed? You can never print 106
endl
on Codeforces. You also can not print 106 lines usingcout
on Codeforces. I don't see any reason why your code would get AC.What do you mean by you can never print? It can be printed, just that it will require more time. e.g. it runs in around 2 secs on my system. I suppose it can also run on codeforces system within 2 or 3 secs at most.
Since we are talking about this specific problem, of course I meant you can never print 106 lines in 1 sec.
I am sorry, I totally misinterpreted you. For this problem considering it was a C level, I knew the idea and did not even care to see the time limits after seeing solution pretest passed.
My code with cin, cout. I used multiset to solve the problem.
Code
966 ms
, well.. that was between life and death :)I pushed even strings into the vector, which kind of pushed me over the edge :P
Yeah, didn't notice the time before posting. :/
My c++ soln http://ideone.com/3gyHx5 got a tle on the 11th case. I have seen a soln exactly similar to mine which has passed all the testcases. Can someone please tell me what is wrong with my soln?
I suggest you to resubmit your same code. I also had TLE in 11th test case.
Because this is what got me convert a TLE into AC.
During contest submission : http://mirror.codeforces.com/contest/681/submission/18471145 : TLE
After contest same submission : http://mirror.codeforces.com/contest/681/submission/18480337 : AC
Even worse code(I use string instead of int unlike him) using scanf+cout combo passes in 451ms. Interesting how much difference I/O can make in a contest. 18465826
Did you try replacing cin/cout with scanf/printf? That may improve the runtime
I think it will pass with that.
Same here, multiset give tle, was using cin and cout. It could be a good idea to have pretests with large input.
You are using cin/cout plus O(log N) delete operations instead of amortized O(1), so it's not a big surprise since there's about 10^6 operations. Also C++ containers are pretty slow.
@Dongmin: I did not get what do you mean by O(log N) delete operations instead of O(1) amortized? Are delete operations in multiset amortized O(1)?
In your code, this line is amortized O(1)
st.erase(it);
but the previous one is O(log N)
auto it = st.find(toRemove[i]);
So the overall complexity is O(log N) per operation. Instead, you could erase the top element one by one, and each operation st.erase(st.begin()) would be amortized O(1) (because st.begin() return an iterator).
Oh ok, got it. Thanks !!
My submission to C got TLEd. So i was a little surprised because I was not expecting that. So I resubmitted the solution after the contest. The very same code and it got AC.
These are the links to the two submissions : http://mirror.codeforces.com/contest/681/submission/18471145 TLE http://mirror.codeforces.com/contest/681/submission/18480337 AC
I feel so bad. I did not change a single thing.
Server speed varies from time to time (not significantly though). You can make your code more efficient by removing the "to_string" parts and storing answers in a std::vector<pair<string,int>> instead of std::vector< string> OR you can use a faster int to string conversion method.
Moreover, such test cases should have been in pre-tests and not in system tests. I use scanf/printf every time but since C++ doesn't support scanf/printf for Std::String in a direct way, I specifically used cin/cout for this problem. :(
can someone tell me why my submission is getting WA on testcase 10: http://mirror.codeforces.com/contest/681/submission/18477598
I'm getting exactly the same incorrect output 18478661 and am also wondering, what is wrong.
I had a brief look at your code. Try this, whenever you pop out elements from the priority queue when a>pq.top(), check if pq.top() is equal to a after the end of while loop. You can see my submission here: http://mirror.codeforces.com/contest/681/submission/18477972
Also, please indent your code in future, it makes it easier to debug the code. :)
How to solve E?
Hi all. i'm getting wrong answer 6 in problem D and i change my code i get AC.
i don't know whats wrong with my second code!
can you help me?
my codes: 18478142 & 18478267 .
UPD: i unserstand my mistake.
thanks!
In my code for div2E Link
In line 43 i am calling a function subtend(point p1, point p2) which accepts 2 objects of class point , but while calling it i bymistakely typed '0' instead of typing 'o' . But it did not get a compile error at it still works perfectly fine on sample .
Any idea why?
Because you declared this constructor:
point(double _x = 0 , double _y = 0)
The single 0 matches that signature, C++ helpfully interprets it as a constructor call.
thanks
in problem B i didn't see the sentence " there is a triple of (non-negative) integers a, b and c " and it costs me almost 300 points!!
How this passed system tests?
Nice problems. I have stuck into problem D for nearly half an hour for finding an easier way to implement it. Also, here is a slightly easier version for problem E.
неправильно предсказывает новые звания, Эксперт -> Cпециалист, Специалист -> Эксперт, Ученик -> Новичок
Исправлено
How to solve C with priority_queue?
You have 2 options:
1. Negate numbers before
pq.push(-n)
and negate them when getting back:n = -pq.top()
.2. Use a different comparator:
priority_queue<int, std::vector<int>, std::greater<int>> pq;
Hello all ! I am getting WA on 10 th test case in the C problem .I have not implemented priority queue as most of you have done , i have used set and map. I cannot find the bug , if any of you could i would be grateful! http://mirror.codeforces.com/contest/681/submission/18478591
map
andset
do NOT store duplicates, but you need to be able to store the sequence: (1, 1, 1).vopros Prostite pozhaluista lqqbxt343
Who are this users? Their nicknames construct a sentence in russian. I think they should be deleted from ranklist.
How to get rid of TLE in C? What am I doing slow? Looks pretty straightforward for me :/ http://mirror.codeforces.com/contest/681/submission/18478954
Remove "cin" from your code and change it to "scanf" and "cout" to "printf". Also stop comparing strings e.g. "s == removeMin" replace it with a char and use "( c =='r')" . something like this.
I too got a TLE in the same problem. But making the above changes gave me AC. Lesson learnt the hard way!
I see successful solutions with cin. And I don't see your successful solution without cin. :/
http://mirror.codeforces.com/contest/681/submission/18480178
Try this.
And? There is no successful C.
I have a succesful C with cin/cout, after adding ios_base::sync_with_stdio(0) and cin.tie(0) it passes in 982ms.
Ok. Look like I should use priority queue instead of list.
What made my code run in 998 ms was using to_string, when I took that out it ran in 200ms
Who also thought, that STL priority_queue top() return MIN value?))
You were once in Div1 and still did not know that the default STL priority queue is a maxHeap. LOL :P
You know this if you use it. Quite often set/multiset is enough.
statement confused me )
Perfect problem complexity for first four problems. It happens not often for div2 contest. Thank you!
Test data for problem D is weak. I sent this solution (18480432) and it got Accepted. Then I found a bug (on my way from the leaf to the root, I only updated parents with values of their children instead of keeping the minimum along the path to have the minimum of the whole subtree). A simple test like this one breaks the solution.
The Accepted code reports there's a solution, while in fact there isn't.
Hello i am newbee here. So i have a question about A tast, i gues my code runs perfect, and in testing room it has passed all pretests, but when i have sent it, it could not past second preset, can you help me please, what is wrong with it? var n = readline(); var flag = true; for(i=0;i<=n;i++){ var y = readline(); y = y.split(" "); var handle = y[0]; var before = Number(y[1]); var after = Number(y[2]); if(before >= 2400 && after >2400){ print("YES"); flag = false; break; } } if(flag === true){ print("NO"); }
I changed your for condition to: for(i=0;i<n;i++)
Before it was: for(i=0;i<=n;i++)
But this solution is still getting WA because of two details:
Your 'if' condition is partially wrong. It should be: if(before >= 2400 && after > before);
The output is either 'YES' or 'NO'. And you don't print a 'NO' anywhere in your program.
Hope this helps.
A small English suggestion: in problem A you have
"his performance in the rated contest to be good if he outscored some participant, whose handle was colored red before the contest and his rating has increased after it"
Note that the first and second "he" refer to Anton while third "he" is some participant, I think this is confusing. For this reason I would try to avoid pronouns in statements unless there is only a single possibility for each one of them.
I think you should check the test again. With this code http://mirror.codeforces.com/contest/681/submission/18485550 and the Input: 5 4 1 2 2 3 3 4 4 5 1 1 2 3 4 I got this Output: 4 4 3 2 1 (It's wrong, I think the correct answer is -1) But this code still get Accepted.
Good Contest For me as for the first time my rating has increased
What can I do to optimize this solution. It gives TLE 18488801 in Div2C.
Use scanf and printf instead of cin and cout. also You can use int in this problem,No need of long long.
I am having some trouble understanding problem D:
"if there is no ancestor of a person in the list, he becomes sad and leaves the celebration without giving a gift to anyone"
But according to definition every man is his own ancestor..so person must never feel sad
Also, for sample test case 1 why is the following sequence incorrect? k=2
2
1
(we dont put 3 in the sequence)
3 gives a gift to 2 and wants to 1.