.tx's blog

Codeforces Round #357 (Div. 2)
By .tx, history, 8 years ago, translation, In English

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

  1. pozhaluista
  2. Bedge
  3. jerjerisfat
  4. Huyum_nik
  5. OnlyYuju

Div. 1

  1. uwi
  2. anta
  3. kmjp
  4. ngfam_kongu
  5. BigBag

UPD

Editorial

  • Vote: I like it
  • +301
  • Vote: I do not like it

Comments Comments (237)
| Write comment?
»
8 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Good luck, high rating and good mood to everyone!!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    Exactly, short and pretty much sums up everything!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Why this comment be deny as Negative？

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -292 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        And this contest really did have some good problems.

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Everyone is deserved to begin.

    And you deserved to be down-voted.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    learn English, then start judging people :3

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      his English is better than yours :P

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't say mine is great :v

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    This way no contest would be ever done, cos' at the very beginning there were no experienced ones. Just think about it.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like 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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it -30 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +11 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Please edit your template. From previous round it says "The contest duration is 2.5 hours, it will contain 6 problems." :D

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

are we gonna see another interactive problem???

→ Reply
»
8 years ago, # |
  Vote: I like it -55 Vote: I do not like it

Im Gay.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Good luck for everybody !!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

may allah be with us :D

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like 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?

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

GOOD LUCK EVERYONE!

→ Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

feeling great!! my first ever contest on codeforces

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope greedy approach does work in C :\

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Anyone solved problem D using HLD?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +31 Vote: I do not like it

    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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

How to solve B and C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Me too. ;)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      for a and b: 0 to ...

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to prove that C is correct?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 6   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got WA on 6 when I made unique wrong.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          "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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and how do we check the condition is satisfied or not

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          or just I need to check

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

          BTW nice dp :P

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bruteforce

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Mind saying what it was ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

problem c testcase 10?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +87 Vote: I do not like it

One second erfaniiyan , one second. . .

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone have tricky test for C? =)

→ Reply
»
8 years ago, # |
  Vote: I like it +44 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    3 2 is the value of n and m :P

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Very nice sample!

→ Reply
»
8 years ago, # |
  Vote: I like it -45 Vote: I do not like it

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;

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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you want to say + is slower than %?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Tnanks for letting us know about that :|

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

priority_queue in C gave TLE :(

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not really, I did it with STL priority_queue too.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now it got WA

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

It is like

smurfs everywhere :'(

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have TLE because you used cin cout endl.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -12 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              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
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @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
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E?

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How this passed system tests?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
»
8 years ago, # |
← Rev. 5   Vote: I like it -6 Vote: I do not like it

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

Исправлено

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C with priority_queue?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

vopros Prostite pozhaluista lqqbxt343

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

→ Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok. Look like I should use priority queue instead of list.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What made my code run in 998 ms was using to_string, when I took that out it ran in 200ms

    → Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Who also thought, that STL priority_queue top() return MIN value?))

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You were once in Div1 and still did not know that the default STL priority queue is a maxHeap. LOL :P

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You know this if you use it. Quite often set/multiset is enough.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      statement confused me )

      → Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Perfect problem complexity for first four problems. It happens not often for div2 contest. Thank you!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you should check the test again. With this code http://codeforces.net/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.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good Contest For me as for the first time my rating has increased

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What can I do to optimize this solution. It gives TLE 18488801 in Div2C.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use scanf and printf instead of cin and cout. also You can use int in this problem,No need of long long.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3 gives a gift to 2 and wants to 1.

    → Reply