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

9 years ago, # ^ |

-12

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

→ Reply

kursatbakis0

9 years ago, # |

← Rev. 2 →

-292

This contest is helpless. Because it is first of yours. Give it to a more experienced one.

→ Reply

Sawako

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

→ Reply

bodmas

9 years ago, # ^ |

+17

He's not even being a bit harsh. He's being too harsh. We have to call a spade a spade.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+12

.tx Thank you and i'm a confident that this contest will contain a nice Problems

→ Reply

jAckAL_1586

9 years ago, # ^ |

+19

And this contest really did have some good problems.

→ Reply

JeanValjean01

9 years ago, # ^ |

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.

→ Reply

Scarlet-FF3300

9 years ago, # ^ |

+33

Everyone is deserved to begin.

And you deserved to be down-voted.

→ Reply

waterfall

9 years ago, # ^ |

Seems like his spam comments have come back again...

→ Reply

9 years ago, # ^ |

← Rev. 2 →

learn English, then start judging people :3

→ Reply

9 years ago, # ^ |

-23

his English is better than yours :P

→ Reply

9 years ago, # ^ |

I didn't say mine is great :v

→ Reply

danilka.pro

9 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.

→ Reply

cup_of_tea

9 years ago, # ^ |

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.

→ Reply

I_Love_Tina

9 years ago, # ^ |

-8

Why you participate in CF contests if you can't solve div 2 D?

→ Reply

pranjal.ssh

9 years ago, # ^ |

+21

nice dp!

→ Reply

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

→ Reply

sqrtdecompton

9 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.

→ Reply

dush1729

9 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

→ Reply

9 years ago, # ^ |

-54

The comment is hidden because of too negative feedback, click here to view it

→ Reply

sorrytourist

9 years ago, # ^ |

You are a cheater!!!!!!

→ Reply

9 years ago, # |

are we gonna see another interactive problem???

→ Reply

Srikar_K

9 years ago, # |

-55

Im Gay.

→ Reply

meintoo

9 years ago, # ^ |

+25

Congrats :D

→ Reply

hmrockstar

9 years ago, # ^ |

+13

Wow! But i don't think its the right place to announce it!

→ Reply

Superstorm4242

9 years ago, # |

I enjoyed Codeforces Round #350 (Div. 2) ( 6 problems, 2.5 hours).... Will it happen again?

→ Reply

sanngu

9 years ago, # |

+25

Thanks for the contest.Excited to solve good problems.All the best everyone.

→ Reply

DoubleNy

9 years ago, # |

Good luck for everybody !!

→ Reply

xiaoai

9 years ago, # |

I wish my rating change into 1700+ ^_^.

→ Reply

9 years ago, # ^ |

Oh, it is good that you will be better than me.

→ Reply

xiaoai

9 years ago, # ^ |

Wish you improve your rating ^_^

→ Reply

9 years ago, # ^ |

+23

sorry, I will be the first of this contest!

→ Reply

xiaoai

9 years ago, # ^ |

..........

→ Reply

luoxinchen

9 years ago, # ^ |

I am very eager to see this.

→ Reply

mathon

9 years ago, # ^ |

So am I.

→ Reply

sds3031

9 years ago, # ^ |

come on, baby！

→ Reply

Abdelfatah_Elsisi

9 years ago, # |

-17

Man this is my first contest in a while. May the power of Egyptians and Indians be with me.

→ Reply

Bassel

9 years ago, # ^ |

Egyptians aren't enough!

→ Reply

AnasAbbas

9 years ago, # |

-16

may allah be with us :D

→ Reply

hasib

9 years ago, # |

← Rev. 2 →

+23

The comment is hidden because of too negative feedback, click here to view it

→ Reply

RetiredAmrMahmoud

9 years ago, # ^ |

+16

I think you mean click here to view it.

→ Reply

prrateekk

9 years ago, # ^ |

+22

→ Reply

filo

9 years ago, # |

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?

→ Reply

filo

9 years ago, # ^ |

fixed already thanks

→ Reply

khatribiru

9 years ago, # ^ |

Me too. But color still same.

→ Reply

chessmaster

9 years ago, # |

GOOD LUCK EVERYONE!

→ Reply

gmahbuhs

9 years ago, # |

feeling great!! my first ever contest on codeforces

→ Reply

9 years ago, # |

I hope greedy approach does work in C :\

→ Reply

9 years ago, # |

Anyone solved problem D using HLD?

→ Reply

nikitosoleil

9 years ago, # ^ |

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?

→ Reply

9 years ago, # ^ |

Heavy Light Decomposition

→ Reply

AshishYadav

9 years ago, # ^ |

+13

See this

→ Reply

9 years ago, # ^ |

Wow, that is awesome!

→ Reply

nikitosoleil

9 years ago, # ^ |

Oh, I never heard about it yet.

→ Reply

chaosagent

9 years ago, # ^ |

← Rev. 2 →

+31

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 ;)

→ Reply

9 years ago, # ^ |

Thanks chaosagent.

→ Reply

tenshi_kanade

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

tenshi_kanade

9 years ago, # ^ |

← Rev. 2 →

Your idea is on the right track. After the contest, I found the simple solution that I was supposed to find during contest.

Let D_v 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 D_v 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

→ Reply

iliekcomputers

9 years ago, # |

Welp, I'm fucked. Pupil status, here I come. :/

How to solve B and C?

→ Reply

dush1729

9 years ago, # ^ |

Me too. ;)

→ Reply

iliekcomputers

9 years ago, # ^ |

Next one goes better hopefully. At least we'll have nothing to lose. :D

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+13

For B, for a = 0 to 1000, b = 0 to 10⁴, 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.

→ Reply

m.khooryani

9 years ago, # ^ |

for a and b: 0 to ...

→ Reply

tamirOK

9 years ago, # ^ |

How to prove that C is correct?

→ Reply

9 years ago, # ^ |

← Rev. 6 →

Here is the language for the proof.

We have 3 possible operations O = {I, R, G} (I = Insert, R = Remove, G = Get).
O₀ = {I, R} $\text{[math]}$ O — mutating operations ( make change ).
O₁ = {G} $\text{[math]}$ 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] = [a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈, a₉, a₁₀]

Then we go through all 10 elements and choose the value a_i $\text{[math]}$ O randomly.
There are 3¹⁰ = 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 O₀ = {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.

→ Reply

iliekcomputers

9 years ago, # ^ |

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.

→ Reply

AtomRush

9 years ago, # ^ |

← Rev. 2 →

I used Linear Diophantine Equations >.< only to realize this was an overkill CODE edit: GOT WA ;_; anybody who used Diophantine and got AC?

→ Reply

chiragjn

9 years ago, # ^ |

← Rev. 3 →

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

→ Reply

9 years ago, # ^ |

Man, 1234567 is not prime!
Look 127 × 9721 = 1234567.

→ Reply

chiragjn

9 years ago, # ^ |

Corrected, thanks.

→ Reply

prrateekk

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

Can you give me his nick or tell afterwards if his solution passed the final tests?

→ Reply

prrateekk

9 years ago, # ^ |

nick — biltharesatyendra

→ Reply

I_Love_Equinox

9 years ago, # ^ |

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.

→ Reply

9 years ago, # ^ |

-6

Aren't max(a) = 811 && max(b) = 8101?

→ Reply

I_Love_Equinox

9 years ago, # ^ |

Yes, I thought that'd be obvious. My loops ran from 0 -820 and 0 -8200

→ Reply

rahulkhairwar

9 years ago, # ^ |

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. :(

→ Reply

linkret

9 years ago, # ^ |

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)

→ Reply

tamirOK

9 years ago, # |

How to solve D?

→ Reply

9 years ago, # ^ |

Check that each node wants to gift either itself or the same as its parent. Then sort all preferences by decreasing depth and uniquealize.

→ Reply

achaitanyasai

9 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

9 years ago, # ^ |

I got WA on 6 when I made unique wrong.

→ Reply

9 years ago, # ^ |

Which condition is guaranteed? It is only guaranteed that a guy wants to gift his ancestor, not his direct parent.

→ Reply

achaitanyasai

9 years ago, # ^ |

← Rev. 2 →

"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."

→ Reply

9 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.

→ Reply

ace_pocket

9 years ago, # ^ |

and how do we check the condition is satisfied or not

→ Reply

ashish1610

9 years ago, # ^ |

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.

→ Reply

ace_pocket

9 years ago, # ^ |

or just I need to check

either gift[i]==i or gift[i]==gift[par[i]]

BTW nice dp :P

→ Reply

lature

9 years ago, # ^ |

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.

→ Reply

9 years ago, # |

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

→ Reply

loser21

9 years ago, # ^ |

You are not checking whether the node is the root of the tree or not before calling dfs.

→ Reply

LSY_is_retired

9 years ago, # ^ |

I used the same algorithm as yours and WA on #5 too……

→ Reply

cdkrot

9 years ago, # ^ |

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.

→ Reply

9 years ago, # |

← Rev. 2 →

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..

→ Reply

P___

9 years ago, # ^ |

← Rev. 4 →

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).

→ Reply

9 years ago, # ^ |

Nice observation

→ Reply

travelers

9 years ago, # |

How to solve div2 B i got hacked two time:(

→ Reply

m.khooryani

9 years ago, # ^ |

bruteforce

iterate among possible a and b, then if c exists: yes

→ Reply

9 years ago, # ^ |

I saw a person who iterated a, b and c! I wonder if he will get TL in the end.

→ Reply

9 years ago, # ^ |

He has to.
5¹¹ operations is huge.

→ Reply

9 years ago, # ^ |

But he didn't.

→ Reply

9 years ago, # ^ |

-10

Then we have only 2 options:
1. Magic happens.
2. Sometimes compiler does a good job with optimization.

→ Reply

9 years ago, # ^ |

Я думаю, дело в том, что там есть выход из циклов, когда ответ находится, и ответ для всех чисел находится быстро.

→ Reply

9 years ago, # ^ |

Not if the bruteforce is optimized through reverse order --> http://codeforces.net/contest/681/submission/18473017

→ Reply

musa.cse12

9 years ago, # ^ |

← Rev. 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

→ Reply

9 years ago, # ^ |

Why value of a cannot be greater than 811 ? how i can see it during contests ?

→ Reply

musa.cse12

9 years ago, # ^ |

bcz 1234567 * 812 > 1e9

→ Reply

send_nodes

9 years ago, # |

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?

→ Reply

P___

9 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

9 years ago, # |

Stupid mistake with C coasted me 9 WA!!! i fell sad, and stupid :(

→ Reply

double301

9 years ago, # ^ |

Mind saying what it was ?

→ Reply

9 years ago, # ^ |

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

→ Reply

radicalachraf

9 years ago, # |

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 .

→ Reply

dush1729

9 years ago, # |

problem c testcase 10?

→ Reply

akvasha

9 years ago, # ^ |

Try this one. I found it, corrected the mistake and got passed. 3 insert 10 getMin 0 getMin 4

→ Reply

OMGTallMonster

9 years ago, # ^ |

← Rev. 2 →

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...

→ Reply

apple_tree_34

9 years ago, # |

Why did I get Wa6 on D? http://www.codeforces.com/contest/681/submission/18466813

→ Reply

mostafa_9a7c2

9 years ago, # ^ |

← Rev. 4 →

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.

→ Reply

DoubleNy

9 years ago, # |

+87

One second erfaniiyan , one second. . .

→ Reply

9 years ago, # |

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....

→ Reply

double301

9 years ago, # |

Anyone have tricky test for C? =)

→ Reply

brucewayne123

9 years ago, # ^ |

4 insert 5

insert 4

removeMin

getMin 2

→ Reply

_index

9 years ago, # ^ |

I can't understand what is tricky there.

→ Reply

shadowfax

9 years ago, # |

+44

Took me 15+ minutes to understand problem D (english version). Such description... much wow!

→ Reply

fr0st

9 years ago, # |

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...

→ Reply

tjn

9 years ago, # ^ |

3 2 is the value of n and m :P

→ Reply

fr0st

9 years ago, # ^ |

LOOOOL. Thanks.

→ Reply

ankeet

9 years ago, # ^ |

← Rev. 2 →

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

→ Reply

9 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.net/contest/681/submission/18470158.

Change the submission id accordingly and have fun !!

→ Reply

Far

9 years ago, # |

Thanks for the contest guys. It would be better if the stories were not that long.

→ Reply

9 years ago, # |

how to solve B ?

→ Reply

Mucosolvan

9 years ago, # ^ |

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.

→ Reply

aHsirG

9 years ago, # |

+26

Very nice sample!

→ Reply

iriszero

9 years ago, # |

-45

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

include <stdio.h>

include

include <assert.h>

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(); }

→ Reply

9 years ago, # |

What is up with the super strict TL on B?

My solution using 10⁸ operations got Time limit exceeded. This is really unfair, this is expected solution, it should pass.. :/

Submission: 18459463

→ Reply

9 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

9 years ago, # ^ |

But 10^8 operations always work easily on CF in a second.. :/

→ Reply

9 years ago, # ^ |

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.

→ Reply

anh1l1ator

9 years ago, # ^ |

← Rev. 3 →

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!

→ Reply

kefaa

9 years ago, # ^ |

Maybe 10^8 slow % operations with long long are too much even for codeforces

→ Reply

Mavzes

9 years ago, # ^ |

-10

Maybe, not %. increment is slow opertation with long long

→ Reply

kefaa

9 years ago, # ^ |

Do you want to say + is slower than %?

→ Reply

Mavzes

9 years ago, # ^ |

How I say, yes. But it was my mistake. % is slower than increment. I think that % isn't use in all operations in code.

→ Reply

microtony

9 years ago, # ^ |

You are correct. % takes 49-135 clock cycles to compute.

Those division instructions alone take 10^8 x 50 / 3x10^9 > 1 second already.

→ Reply

9 years ago, # |

Problem C: WA On test 31 :( :( http://codeforces.net/contest/681/submission/18464083

→ Reply

Far

9 years ago, # ^ |

Tnanks for letting us know about that :|

→ Reply

9 years ago, # ^ |

o.O xD wanted to know the reason why!. Was too impatient to wait for whole system tests to end :\

→ Reply

pas.andrei

9 years ago, # ^ |

Because the heap is empty while it should contain 0 as the smallest number.

→ Reply

sanngu

9 years ago, # |

Wow!!!!eventually,That was very good contest with increasing difficulty.Thanks for the contest.

→ Reply

9 years ago, # |

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.

→ Reply

SarvagyaAgarwal

9 years ago, # |

priority_queue in C gave TLE :(

→ Reply

snacache

9 years ago, # ^ |

Not really, I did it with STL priority_queue too.

→ Reply

MazzForces

9 years ago, # ^ |

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..

→ Reply

OMGTallMonster

9 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.

→ Reply

thearrow

9 years ago, # ^ |

the problem statement must have at least mentioned to use fast I/O.

→ Reply

pedrohlf

9 years ago, # ^ |

← Rev. 2 →

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).

→ Reply

rok04

9 years ago, # ^ |

use "ios_base::sync_with_stdio(0);" with cin/cout. It will work more faster then normal cin/cout.

→ Reply

9 years ago, # ^ |

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. :'(

→ Reply

9 years ago, # ^ |

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)

→ Reply

http://codeforces.net/contest/681/submission/18469930

9 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.

→ Reply

ZiyaZa

9 years ago, # ^ |

← Rev. 2 →

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 :`(

→ Reply

_index

9 years ago, # ^ |

Now it got WA

→ Reply

SarvagyaAgarwal

9 years ago, # ^ |

Yeah wondering why is that ! :P

→ Reply

brucewayne123

9 years ago, # ^ |

→ Reply

Goldsmith94

9 years ago, # ^ |

← Rev. 3 →

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.net/contest/681/submission/18478570

http://codeforces.net/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://codeforces.net/contest/681/submission/18479133

→ Reply

9 years ago, # |

← Rev. 2 →

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

→ Reply

Bedge

9 years ago, # |

+26

It is like

smurfs everywhere :'(

→ Reply

9 years ago, # |

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.

→ Reply

9 years ago, # ^ |

Same here, I suggest rejudging for problem C but has that ever happened before?

→ Reply

_index

9 years ago, # ^ |

← Rev. 3 →

Maybe you used slow input? I used multiset and still got accepted.

→ Reply

I_love_Hoang_Yen

9 years ago, # ^ |

You have TLE because you used cin cout endl.

→ Reply

9 years ago, # ^ |

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.

→ Reply

I_love_Hoang_Yen

9 years ago, # ^ |

+10

What is mostly passed? You can never print 10⁶ endl on Codeforces. You also can not print 10⁶ lines using cout on Codeforces. I don't see any reason why your code would get AC.

→ Reply

9 years ago, # ^ |

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.

→ Reply

I_love_Hoang_Yen

9 years ago, # ^ |

-12

Since we are talking about this specific problem, of course I meant you can never print 10⁶ lines in 1 sec.

→ Reply

9 years ago, # ^ |

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.

→ Reply

ashish1610

9 years ago, # ^ |

My code with cin, cout. I used multiset to solve the problem.
Code

→ Reply

9 years ago, # ^ |

966 ms, well.. that was between life and death :)

→ Reply

9 years ago, # ^ |

I pushed even strings into the vector, which kind of pushed me over the edge :P

→ Reply

ashish1610

9 years ago, # ^ |

Yeah, didn't notice the time before posting. :/

→ Reply

astrid15

9 years ago, # ^ |

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?

→ Reply

pulkitmehta

9 years ago, # ^ |

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.net/contest/681/submission/18471145 : TLE

After contest same submission : http://codeforces.net/contest/681/submission/18480337 : AC

→ Reply

9 years ago, # ^ |

← Rev. 2 →

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

→ Reply

snacache

9 years ago, # ^ |

Did you try replacing cin/cout with scanf/printf? That may improve the runtime

→ Reply

9 years ago, # ^ |

I think it will pass with that.

→ Reply

anakot

9 years ago, # ^ |

Same here, multiset give tle, was using cin and cout. It could be a good idea to have pretests with large input.

→ Reply

Dongmin

9 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

9 years ago, # ^ |

@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)?

→ Reply

Dongmin

9 years ago, # ^ |

← Rev. 2 →

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).

→ Reply

9 years ago, # ^ |

Oh ok, got it. Thanks !!

→ Reply

pulkitmehta

9 years ago, # ^ |

← Rev. 2 →

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.net/contest/681/submission/18471145 TLE http://codeforces.net/contest/681/submission/18480337 AC

I feel so bad. I did not change a single thing.

→ Reply

Dalisyron

9 years ago, # ^ |

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.

→ Reply

kshitij_jain

9 years ago, # ^ |

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. :(

→ Reply

Ishan.nitj

9 years ago, # |

can someone tell me why my submission is getting WA on testcase 10: http://codeforces.net/contest/681/submission/18477598

→ Reply

latvian

9 years ago, # ^ |

I'm getting exactly the same incorrect output 18478661 and am also wondering, what is wrong.

→ Reply

9 years ago, # ^ |

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.net/contest/681/submission/18477972

Also, please indent your code in future, it makes it easier to debug the code. :)

→ Reply

loser21

9 years ago, # |

+10

How to solve E?

→ Reply

amsen

9 years ago, # |

← Rev. 4 →

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!

→ Reply

rajat1603

9 years ago, # |

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?

→ Reply

hex539

9 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.

→ Reply

rajat1603

9 years ago, # ^ |

thanks

→ Reply

Reckt

9 years ago, # |

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

→ Reply

krock21

9 years ago, # |

How this passed system tests?

→ Reply

quailty

9 years ago, # |

← Rev. 2 →

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.

→ Reply

krock21

9 years ago, # |

← Rev. 5 →

-6

неправильно предсказывает новые звания, Эксперт -> Cпециалист, Специалист -> Эксперт, Ученик -> Новичок

Исправлено

→ Reply

Emilbek

9 years ago, # |

How to solve C with priority_queue?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

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;

→ Reply

code_astra

9 years ago, # |

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.net/contest/681/submission/18478591

→ Reply

vopros Prostite pozhaluista lqqbxt343

9 years ago, # ^ |

map and set do NOT store duplicates, but you need to be able to store the sequence: (1, 1, 1).

→ Reply

KirillB

9 years ago, # |

+11

Who are this users? Their nicknames construct a sentence in russian. I think they should be deleted from ranklist.

→ Reply

9 years ago, # |

-10

How to get rid of TLE in C? What am I doing slow? Looks pretty straightforward for me :/ http://codeforces.net/contest/681/submission/18478954

→ Reply

sidgairo18

9 years ago, # ^ |

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!

→ Reply

http://codeforces.net/contest/681/submission/18480178

9 years ago, # ^ |

I see successful solutions with cin. And I don't see your successful solution without cin. :/

→ Reply

sidgairo18

9 years ago, # ^ |

← Rev. 2 →

Try this.

→ Reply

9 years ago, # ^ |

And? There is no successful C.

→ Reply

Mucosolvan

9 years ago, # ^ |

I have a succesful C with cin/cout, after adding ios_base::sync_with_stdio(0) and cin.tie(0) it passes in 982ms.

→ Reply