### .tx's blog

By .tx, history, 6 years ago, translation,

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

Editorial

• +301

 » 6 years ago, # |   -30 Good luck, high rating and good mood to everyone!!
•  » » 6 years ago, # ^ |   -29 Exactly, short and pretty much sums up everything!
•  » » 6 years ago, # ^ |   -7 Why this comment be deny as Negative？
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -31 The comment is hidden because of too negative feedback, click here to view it
• »
»
»
6 years ago, # ^ |
-12

# Because big font is too ugly.I guess it.( ´థ,_‥థ｀)b

 » 6 years ago, # | ← Rev. 2 →   -292 This contest is helpless. Because it is first of yours. Give it to a more experienced one.
•  » » 6 years ago, # ^ |   +66 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!
•  » » » 6 years ago, # ^ |   +17 He's not even being a bit harsh. He's being too harsh. We have to call a spade a spade.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +12 .tx Thank you and i'm a confident that this contest will contain a nice Problems
•  » » » » 6 years ago, # ^ |   +19 And this contest really did have some good problems.
•  » » » 6 years ago, # ^ |   +9 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.
•  » » 6 years ago, # ^ |   +33 Everyone is deserved to begin.And you deserved to be down-voted.
•  » » » 6 years ago, # ^ |   +3 Seems like his spam comments have come back again...
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 learn English, then start judging people :3
•  » » » 6 years ago, # ^ |   -23 his English is better than yours :P
•  » » » » 6 years ago, # ^ |   0 I didn't say mine is great :v
•  » » 6 years ago, # ^ | ← Rev. 2 →   +14 This way no contest would be ever done, cos' at the very beginning there were no experienced ones. Just think about it.
•  » » 6 years ago, # ^ |   0 oooooh I get it now you are here to take back your last place in the contribution list from the person who stole it.
•  » » 6 years ago, # ^ |   +6 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.
•  » » 6 years ago, # ^ |   -8 Why you participate in CF contests if you can't solve div 2 D?
•  » » » 6 years ago, # ^ |   +21 nice dp!
»
6 years ago, # |
-30

### 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!

•  » » 6 years ago, # ^ | ← Rev. 4 →   +11 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.
 » 6 years ago, # |   +16 Please edit your template. From previous round it says "The contest duration is 2.5 hours, it will contain 6 problems." :D
•  » » 6 years ago, # ^ |   -54 The comment is hidden because of too negative feedback, click here to view it
• »
»
»
6 years ago, # ^ |
+1

# You are a cheater!!!!!!

 » 6 years ago, # |   +9 are we gonna see another interactive problem???
 » 6 years ago, # |   -55 Im Gay.
•  » » 6 years ago, # ^ |   +25 Congrats :D
•  » » » 6 years ago, # ^ |   -9 Congrats for what ??
•  » » 6 years ago, # ^ |   +13 Wow! But i don't think its the right place to announce it!
 » 6 years ago, # |   0 I enjoyed Codeforces Round #350 (Div. 2) ( 6 problems, 2.5 hours).... Will it happen again?
 » 6 years ago, # |   -30 .tx did you arranged any contests on other sites Like TOPcoder-HackerEarth-Hackerrank ?
 » 6 years ago, # |   +25 Thanks for the contest.Excited to solve good problems.All the best everyone.
 » 6 years ago, # |   +4 Good luck for everybody !!
 » 6 years ago, # |   0 I wish my rating change into 1700+ ^_^.
•  » » 6 years ago, # ^ |   0 Oh, it is good that you will be better than me.
•  » » » 6 years ago, # ^ |   0 Wish you improve your rating ^_^
• »
»
»
»
6 years ago, # ^ |
+23

### sorry, I will be the first of this contest!

•  » » » » » 6 years ago, # ^ |   0 ..........
•  » » » » » 6 years ago, # ^ |   0 yes you will be the first to shitpost. lololololol.
•  » » » » » 6 years ago, # ^ |   +3 I am very eager to see this.
•  » » » » » » 6 years ago, # ^ |   +2 So am I.
•  » » » » » 6 years ago, # ^ |   0 come on, baby！
•  » » » » 6 years ago, # ^ |   0 wish you improve your english
•  » » 6 years ago, # ^ |   0 Good luck.
 » 6 years ago, # |   -17 Man this is my first contest in a while. May the power of Egyptians and Indians be with me.
•  » » 6 years ago, # ^ |   0 Egyptians aren't enough!
 » 6 years ago, # |   -16 may allah be with us :D
 » 6 years ago, # | ← Rev. 2 →   +23 The comment is hidden because of too negative feedback, click here to view it
•  » » 6 years ago, # ^ |   +16 I think you mean click here to view it.
•  » » » 6 years ago, # ^ |   +22
 » 6 years ago, # |   +9 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?
•  » » 6 years ago, # ^ |   0 fixed already thanks
•  » » 6 years ago, # ^ |   0 Me too. But color still same.
 » 6 years ago, # |   +4 GOOD LUCK EVERYONE!
 » 6 years ago, # |   +7 feeling great!! my first ever contest on codeforces
 » 6 years ago, # |   0 I was not able to submit solution for the first problem even after 10 minutes of the start of the contest and I registered for the contest in the registration time period.
•  » » 6 years ago, # ^ |   0 Same here , Codeforces having a lot of bug lately!
 » 6 years ago, # |   0 And I again forgot to register :(
 » 6 years ago, # |   +3 I hope greedy approach does work in C :\
 » 6 years ago, # |   +6 Anyone solved problem D using HLD?
•  » » 6 years ago, # ^ |   0 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?
•  » » » 6 years ago, # ^ |   +7 Heavy Light Decomposition
•  » » » 6 years ago, # ^ |   +13
•  » » » » 6 years ago, # ^ |   +3 Wow, that is awesome!
•  » » » » 6 years ago, # ^ |   0 Oh, I never heard about it yet.
•  » » » 6 years ago, # ^ |   +3 Thanks chaosagent.
•  » » 6 years ago, # ^ |   0 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
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Your idea is on the right track. After the contest, I found the simple solution that I was supposed to find during contest. Let Dv be the depth of the node that v will be giving gift to. Then, process the nodes in reverse order (starting from the leaves) and "pushing up" values Dv as we go (we always keep the minimum one). Finally, check for every receiving node (people who receive gifts) if the value we stored at it in the previous step is less than its depth. If so, there' no answer. If there's an answer, we can find it by adding receiver nodes in order of descending depth. Check out code for more clarity: 18483927
 » 6 years ago, # |   +3 Welp, I'm fucked. Pupil status, here I come. :/ How to solve B and C?
•  » » 6 years ago, # ^ |   +3 Me too. ;)
•  » » » 6 years ago, # ^ |   +1 Next one goes better hopefully. At least we'll have nothing to lose. :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 6 years ago, # ^ |   +1 for a and b: 0 to ...
•  » » » 6 years ago, # ^ |   0 How to prove that C is correct?
•  » » » » 6 years ago, # ^ | ← Rev. 6 →   0 Here is the language for the proof.We have 3 possible operations O = {I, R, G} (I = Insert, R = Remove, G = Get).O0 = {I, R} O — mutating operations ( make change ).O1 = {G} O — accessor operations ( without change ). 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.
•  » » » 6 years ago, # ^ |   +4 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.
•  » » » » 6 years ago, # ^ |   0 Hahaha I feel you, struggling on problem B really shook me up too xD
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I used Linear Diophantine Equations >.< only to realize this was an overkill CODE edit: GOT WA ;_; anybody who used Diophantine and got AC?
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 same, thought Bezout's or gcd will get me the answer, but realised 1234567 was prime coprime with other two and plus problem needs non negative solution.It was too late and I resorted to brute, and got TLE on system testsC, implemented in last 10 mins in hurry,I pushed insert operation to my answer vector, forgot to perform it on multiset, WAInstant AC after the system tests with the correction.I need to practice a lot
•  » » » » » 6 years ago, # ^ |   0 Man, 1234567 is not prime!Look 127 × 9721 = 1234567.
•  » » » » » » 6 years ago, # ^ |   0 Corrected, thanks.
•  » » » 6 years ago, # ^ |   0 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 from sys import stdin n = int(stdin.readline()) ans = 'NO' for i in xrange(101): a = i*1234567 if a>n: break for j in xrange(1001): b = j*123456 if a+b > n: break rem = n-a-b if rem%1234==0: #print i,j,a,b,rem,rem/1234 ans = 'YES' break if ans=='YES': break print ans 
•  » » » » 6 years ago, # ^ |   0 Can you give me his nick or tell afterwards if his solution passed the final tests?
•  » » » » » 6 years ago, # ^ |   +1 nick — biltharesatyendra
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Newbie status, here I come!
•  » » 6 years ago, # ^ |   +1 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.
•  » » » 6 years ago, # ^ |   -6 Aren't max(a) = 811 && max(b) = 8101?
•  » » » » 6 years ago, # ^ |   0 Yes, I thought that'd be obvious. My loops ran from 0 -820 and 0 -8200
•  » » 6 years ago, # ^ |   0 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. :(
•  » » 6 years ago, # ^ |   0 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)
 » 6 years ago, # |   +1 How to solve D?
•  » » 6 years ago, # ^ |   +6 Check that each node wants to gift either itself or the same as its parent. Then sort all preferences by decreasing depth and uniquealize.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 6 years ago, # ^ |   0 I got WA on 6 when I made unique wrong.
•  » » » » 6 years ago, # ^ |   0 Which condition is guaranteed? It is only guaranteed that a guy wants to gift his ancestor, not his direct parent.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 "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."
•  » » 6 years ago, # ^ |   +11 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.
•  » » » 6 years ago, # ^ |   0 and how do we check the condition is satisfied or not
•  » » » » 6 years ago, # ^ |   +3 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.
•  » » » » » 6 years ago, # ^ |   0 or just I need to checkeither gift[i]==i or gift[i]==gift[par[i]]BTW nice dp :P
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +1 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
•  » » 6 years ago, # ^ |   +3 You are not checking whether the node is the root of the tree or not before calling dfs.
•  » » 6 years ago, # ^ |   +3 I used the same algorithm as yours and WA on #5 too……
•  » » 6 years ago, # ^ |   +3 It is here: if(!visited[i]) dfs(i, 1, -1); 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.
 » 6 years ago, # | ← Rev. 2 →   +3 Making an array unique is so hard :/ costed me 8 WAs in DFirst 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..
•  » » 6 years ago, # ^ | ← Rev. 4 →   +8 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).
•  » » » 6 years ago, # ^ |   +8 Nice observation
 » 6 years ago, # |   0 How to solve div2 B i got hacked two time:(
•  » » 6 years ago, # ^ |   0 bruteforceiterate among possible a and b, then if c exists: yes
•  » » » 6 years ago, # ^ |   0 I saw a person who iterated a, b and c! I wonder if he will get TL in the end.
•  » » » » 6 years ago, # ^ |   0 He has to.511 operations is huge.
•  » » » » » 6 years ago, # ^ |   0 But he didn't.
•  » » » » » » 6 years ago, # ^ |   -10 Then we have only 2 options:1. Magic happens.2. Sometimes compiler does a good job with optimization.
•  » » » » » » » 6 years ago, # ^ |   0 Я думаю, дело в том, что там есть выход из циклов, когда ответ находится, и ответ для всех чисел находится быстро.
•  » » » » » 6 years ago, # ^ |   0 Not if the bruteforce is optimized through reverse order --> http://codeforces.com/contest/681/submission/18473017
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 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
•  » » » 6 years ago, # ^ |   0 Why value of a cannot be greater than 811 ? how i can see it during contests ?
•  » » » » 6 years ago, # ^ |   +5 bcz 1234567 * 812 > 1e9
 » 6 years ago, # |   +6 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?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 6 years ago, # |   +3 Stupid mistake with C coasted me 9 WA!!! i fell sad, and stupid :(
•  » » 6 years ago, # ^ |   +1 Mind saying what it was ?
•  » » » 6 years ago, # ^ |   0 getMid xif 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
 » 6 years ago, # |   +1 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 .
 » 6 years ago, # |   +3 problem c testcase 10?
•  » » 6 years ago, # ^ |   0 I would know it too, got TLE on the 10th pretest
•  » » 6 years ago, # ^ |   0 Got WA. :(
•  » » 6 years ago, # ^ |   +6 Try this one. I found it, corrected the mistake and got passed. 3 insert 10 getMin 0 getMin 4
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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...
 » 6 years ago, # |   +5 Why did I get Wa6 on D? http://www.codeforces.com/contest/681/submission/18466813
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 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 3In 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.
 » 6 years ago, # |   +87 One second erfaniiyan , one second. . .
 » 6 years ago, # |   0 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....
 » 6 years ago, # |   0 Anyone have tricky test for C? =)
•  » » 6 years ago, # ^ |   0 4 insert 5insert 4removeMingetMin 2
•  » » » 6 years ago, # ^ |   0 Why is this tricky test ?5 insert 5 insert 4 removeMin insert 2 getMin 2
•  » » » 6 years ago, # ^ |   0 I can't understand what is tricky there.
 » 6 years ago, # |   +44 Took me 15+ minutes to understand problem D (english version). Such description... much wow!
 » 6 years ago, # |   0 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...
•  » » 6 years ago, # ^ |   +1 3 2 is the value of n and m :P
•  » » » 6 years ago, # ^ |   +5 LOOOOL. Thanks.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 The first line "3 2" are the numbers n and m respectively. The next m lines are the family relations, that is: p_1 = 1, q_1 = 2 p_2 = 2, q_2 = 3 
 » 6 years ago, # |   +30 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://codeforces.com/contest/681/submission/18470158.Change the submission id accordingly and have fun !!
 » 6 years ago, # |   +2 Thanks for the contest guys. It would be better if the stories were not that long.
 » 6 years ago, # |   0 how to solve B ?
•  » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # |   +26 Very nice sample!
»
6 years ago, # |
-45

Does anybody have an idea of the following code that occurs memory exceeded?

# include

using namespace std;

typedef long long int lld;

void solve() { int N; scanf("%d", &N); vector<pair<char, int>> res;

multimap<int,bool> m;
int cnt = 0;
char buf[20]; int val;
while (N--) {
assert(m.size() <= 100000 && res.size() <= 1000000);
scanf("%s", buf);
if (buf[0] != 'r') scanf("%d", &val);
if (buf[0] == 'i') {
m.insert(make_pair(val, cnt++));
res.push_back(make_pair(0, val));
}
else if (buf[0] == 'r') {
if (m.empty()) {
m.insert(make_pair(0, cnt++));
res.push_back({ 0, 0 });
}
auto it = m.lower_bound(val);
m.erase(it);
res.push_back(make_pair(2, -1));
}
else {
int prv_size = m.size();
auto it_l = m.lower_bound(val),
it_u = m.upper_bound(val);
m.erase(m.begin(), it_l);
for (int i = 0; i < prv_size - m.size(); i++) {
res.push_back(make_pair(2, -1));
}
it_l = m.lower_bound(val),
it_u = m.upper_bound(val);
if (it_l == it_u) {
m.insert(make_pair(val, cnt++));
res.push_back(make_pair(0, val));
}
auto it = m.lower_bound(val);
m.erase(it);
res.push_back(make_pair(1, val));
}
}

printf("%d\n", res.size());
for (auto &r : res) {
switch (r.first) {
case 0:
printf("insert %d\n", r.second);
break;
case 1:
printf("getMin %d\n", r.second);
break;
case 2:
printf("removeMin\n");
break;
}
}


} int main(void) { solve(); }

 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 6 years ago, # ^ |   0 But 10^8 operations always work easily on CF in a second.. :/
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 You pushed the limits even further by using long long rather than int. My code and your code is almost same. 18464576I was worried about failing the system test but luckily I didn't!
•  » » 6 years ago, # ^ |   +9 Maybe 10^8 slow % operations with long long are too much even for codeforces
•  » » » 6 years ago, # ^ |   -10 Maybe, not %. increment is slow opertation with long long
•  » » » » 6 years ago, # ^ |   0 Do you want to say + is slower than %?
•  » » » » » 6 years ago, # ^ |   0 How I say, yes. But it was my mistake. % is slower than increment. I think that % isn't use in all operations in code.
•  » » » 6 years ago, # ^ |   0 You are correct. % takes 49-135 clock cycles to compute.Those division instructions alone take 10^8 x 50 / 3x10^9 > 1 second already.
 » 6 years ago, # |   0 Problem C: WA On test 31 :( :( http://codeforces.com/contest/681/submission/18464083
•  » » 6 years ago, # ^ |   +6 Tnanks for letting us know about that :|
•  » » » 6 years ago, # ^ |   0 o.O xD wanted to know the reason why!. Was too impatient to wait for whole system tests to end :\
•  » » » » 6 years ago, # ^ |   +1 Because the heap is empty while it should contain 0 as the smallest number.
 » 6 years ago, # |   +4 Wow!!!!eventually,That was very good contest with increasing difficulty.Thanks for the contest.
 » 6 years ago, # |   0 Example input data for prob. AApplejack 2400 2400 Fluttershy 2390 2431 Pinkie_Pie -2500 -2450I wonder if the other pretests have the other Mane six.
 » 6 years ago, # |   0 priority_queue in C gave TLE :(
•  » » 6 years ago, # ^ |   0 Not really, I did it with STL priority_queue too.
•  » » 6 years ago, # ^ |   0 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..
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » » 6 years ago, # ^ |   +5 the problem statement must have at least mentioned to use fast I/O.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 6 years ago, # ^ |   +3 use "ios_base::sync_with_stdio(0);" with cin/cout. It will work more faster then normal cin/cout.
•  » » 6 years ago, # ^ |   +3 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. :'(
•  » » » 6 years ago, # ^ |   +1 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)
•  » » » » 6 years ago, # ^ |   +20 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.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 I got TLE too :( with cin/cout but now I had resubmitted the same code with this 2 lines:  ios_base::sync_with_stdio(false); cin.tie(); and I got accepted :(
•  » » 6 years ago, # ^ |   0 Now it got WA
•  » » » 6 years ago, # ^ |   0 Yeah wondering why is that ! :P
•  » » 6 years ago, # ^ |   0 I got TLE as well. I use FastScanner for input and StringBuffer for output. Any ideas why?
•  » » » 6 years ago, # ^ |   0 Found it. I used contains in the priority queue :S
•  » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 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://codeforces.com/contest/681/submission/18478570http://codeforces.com/contest/681/submission/18478627EDIT: 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 costlyhttp://codeforces.com/contest/681/submission/18479133
 » 6 years ago, # | ← Rev. 2 →   +5 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
 » 6 years ago, # |   +26 It is likesmurfs everywhere :'(
 » 6 years ago, # |   +3 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.
•  » » 6 years ago, # ^ |   +1 Same here, I suggest rejudging for problem C but has that ever happened before?
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Maybe you used slow input? I used multiset and still got accepted.
•  » » 6 years ago, # ^ |   0 You have TLE because you used cin cout endl.
•  » » » 6 years ago, # ^ |   +2 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.
•  » » » » 6 years ago, # ^ |   +10 What is mostly passed? You can never print 106 endl on Codeforces. You also can not print 106 lines using cout on Codeforces. I don't see any reason why your code would get AC.
•  » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » 6 years ago, # ^ |   -12 Since we are talking about this specific problem, of course I meant you can never print 106 lines in 1 sec.
•  » » » » » » » 6 years ago, # ^ |   +3 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.
•  » » » » » 6 years ago, # ^ |   0 My code with cin, cout. I used multiset to solve the problem. Code
•  » » » » » » 6 years ago, # ^ |   0 966 ms, well.. that was between life and death :)
•  » » » » » » » 6 years ago, # ^ |   0 I pushed even strings into the vector, which kind of pushed me over the edge :P
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Mine didn't pass even after doing that :'(
•  » » » » » » » 6 years ago, # ^ |   0 Yeah, didn't notice the time before posting. :/
•  » » » » » » » » 6 years ago, # ^ |   0 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?
•  » » » » » » » » » 6 years ago, # ^ |   0 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://codeforces.com/contest/681/submission/18471145 : TLEAfter contest same submission : http://codeforces.com/contest/681/submission/18480337 : AC
•  » » » » » » » » » 6 years ago, # ^ |   0 Nevermind, got it. endl was causing it to TLE :(
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 6 years ago, # ^ |   0 Did you try replacing cin/cout with scanf/printf? That may improve the runtime
•  » » » 6 years ago, # ^ |   0 I think it will pass with that.
•  » » 6 years ago, # ^ |   0 Same here, multiset give tle, was using cin and cout. It could be a good idea to have pretests with large input.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 6 years ago, # ^ |   0 @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)?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » 6 years ago, # ^ |   0 Oh ok, got it. Thanks !!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 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://codeforces.com/contest/681/submission/18471145 TLE http://codeforces.com/contest/681/submission/18480337 AC I feel so bad. I did not change a single thing.
•  » » » 6 years ago, # ^ |   0 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> instead of std::vector< string> OR you can use a faster int to string conversion method.
•  » » 6 years ago, # ^ |   0 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. :(
 » 6 years ago, # |   0 can someone tell me why my submission is getting WA on testcase 10: http://codeforces.com/contest/681/submission/18477598
•  » » 6 years ago, # ^ |   0 I'm getting exactly the same incorrect output 18478661 and am also wondering, what is wrong.
•  » » 6 years ago, # ^ |   0 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://codeforces.com/contest/681/submission/18477972Also, please indent your code in future, it makes it easier to debug the code. :)
 » 6 years ago, # |   +10 How to solve E?
 » 6 years ago, # | ← Rev. 4 →   0 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!
 » 6 years ago, # |   +8 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?
•  » » 6 years ago, # ^ |   +21 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.
•  » » » 6 years ago, # ^ |   0 thanks
 » 6 years ago, # |   0 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!!
 » 6 years ago, # |   +1 How this passed system tests?
 » 6 years ago, # | ← Rev. 2 →   0 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.
 » 6 years ago, # | ← Rev. 5 →   -6 неправильно предсказывает новые звания, Эксперт -> Cпециалист, Специалист -> Эксперт, Ученик -> НовичокИсправлено
 » 6 years ago, # |   0 How to solve C with priority_queue?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9 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, std::greater> pq;
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Code I used simple greedy logic. If operation is insert then insert directly. If it is removeMin and que is empty then add a random number. if it is getmin pop the top element of the que till it is smaller. Sadly my code gave TLE during the contest, the code above was edited and ACCEPTED after the contest
 » 6 years ago, # |   0 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://codeforces.com/contest/681/submission/18478591
•  » » 6 years ago, # ^ |   +8 map and set do NOT store duplicates, but you need to be able to store the sequence: (1, 1, 1).
•  » » » 6 years ago, # ^ |   0 Thank you!
 » 6 years ago, # |   +11 Who are this users? Their nicknames construct a sentence in russian. I think they should be deleted from ranklist.
 » 6 years ago, # |   -10 How to get rid of TLE in C? What am I doing slow? Looks pretty straightforward for me :/ http://codeforces.com/contest/681/submission/18478954
•  » » 6 years ago, # ^ |   +3 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!
•  » » » 6 years ago, # ^ |   0 I see successful solutions with cin. And I don't see your successful solution without cin. :/
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0
•  » » » » » 6 years ago, # ^ |   0 And? There is no successful C.
•  » » » » » » 6 years ago, # ^ |   0 I have a succesful C with cin/cout, after adding ios_base::sync_with_stdio(0) and cin.tie(0) it passes in 982ms.
•  » » 6 years ago, # ^ |   0 Ok. Look like I should use priority queue instead of list.
•  » » » 6 years ago, # ^ |   0 Oh so you were using a List. Yes priority queue is faster. Anyways these are just stepping stones to Success. Happy Coding :)
•  » » 6 years ago, # ^ |   0 What made my code run in 998 ms was using to_string, when I took that out it ran in 200ms
 » 6 years ago, # |   +21 Who also thought, that STL priority_queue top() return MIN value?))
•  » » 6 years ago, # ^ |   0 You were once in Div1 and still did not know that the default STL priority queue is a maxHeap. LOL :P
•  » » » 6 years ago, # ^ |   +3 You know this if you use it. Quite often set/multiset is enough.
•  » » » 6 years ago, # ^ |   +5 statement confused me )
 » 6 years ago, # |   +17 Perfect problem complexity for first four problems. It happens not often for div2 contest. Thank you!
 » 6 years ago, # | ← Rev. 2 →   +6 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. 4 3 4 3 3 2 2 1 4 3 4 4 `The Accepted code reports there's a solution, while in fact there isn't.
 » 6 years ago, # |   0 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"); }
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Opps, in log it says: program.jsx:5: TypeError: Cannot read property 'split' of undefined y = y.split(" "); ^ TypeError: Cannot read property 'split' of undefined at program.jsx:5:10But it has been defined.I guess JS is not the best language for such kind of tasks
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I changed your for condition to: for(i=0;i= 2400 && after > before); The output is either 'YES' or 'NO'. And you don't print a 'NO' anywhere in your program. Hope this helps.
 » 6 years ago, # |   +16 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.
•  » » 6 years ago, # ^ |   0 I don't think that should matter in this particular case as the input consisted only the rating changes of the participants who Anton outscored and not of Anton himself,however in general your comment does hold true
 » 6 years ago, # |   0 I think you should check the test again. With this code http://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.
 » 6 years ago, # |   0 For problem C, I did not add the code ios_base::sync_with_stdio(false); cin.tie(0); and as a result got Time Limit Exceeded in test #11. After adding it I get all system test passed. This taught me a lesson...
 » 6 years ago, # |   0 I learnt a lesson from this contest: "Never hurry when you are typing; hackers are cruel!". I lost my points as I typed 2400 as 2500 by mistake and all pretests got passed even after that! I realized when the code was hacked! :-(
 » 6 years ago, # |   +1 Good Contest For me as for the first time my rating has increased
 » 6 years ago, # |   0 In the question B i.e. the Economy game, in the test case for value "1000000000", there isn't any solution to it and yet the Jury answers "YES". Can anyone please clarify upon this? Thank you.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 a= 0; b= 17; c= 808672. Sorry earlier I wrote 1234*808672= 997901248
•  » » » 6 years ago, # ^ |   0 997901248*1234 is not equal to "1000000000"
•  » » » » 6 years ago, # ^ |   0 It's actually a=0 b=17 c=808672
 » 6 years ago, # | ← Rev. 2 →   0 What can I do to optimize this solution. It gives TLE 18488801 in Div2C.
•  » » 6 years ago, # ^ |   0 Use scanf and printf instead of cin and cout. also You can use int in this problem,No need of long long.
 » 6 years ago, # | ← Rev. 2 →   0 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 sadAlso, for sample test case 1 why is the following sequence incorrect? k=221(we dont put 3 in the sequence)
•  » » 6 years ago, # ^ |   0 3 gives a gift to 2 and wants to 1.