.31's blog

Codeforces Round #357 (Div. 2)
By .31, history, 10 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?
»
10 years ago, hide # |
 
Vote: I like it -30 Vote: I do not like it

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

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

are we gonna see another interactive problem???

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

Im Gay.

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

Good luck for everybody !!

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

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

→ Reply
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

may allah be with us :D

→ Reply
»
10 years ago, hide # |
← 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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

GOOD LUCK EVERYONE!

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

feeling great!! my first ever contest on codeforces

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

I hope greedy approach does work in C :\

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

Anyone solved problem D using HLD?

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

    Me too. ;)

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

      for a and b: 0 to ...

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

      How to prove that C is correct?

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

How to solve D?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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
    • »
      »
      »
      10 years ago, hide # ^ |
      ← 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
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I got WA on 6 when I made unique wrong.

        → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          10 years ago, hide # ^ |
          ← 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
  • »
    »
    10 years ago, hide # ^ |
     
    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
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      and how do we check the condition is satisfied or not

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

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

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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
»
10 years ago, hide # |
← 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
  • »
    »
    10 years ago, hide # ^ |
    ← 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
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

    Mind saying what it was ?

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

problem c testcase 10?

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

One second erfaniiyan , one second. . .

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

Anyone have tricky test for C? =)

→ Reply
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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.me/contest/681/submission/18470158.

Change the submission id accordingly and have fun !!

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

how to solve B ?

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

Very nice sample!

→ Reply
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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
  • »
    »
    10 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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
      • »
        »
        »
        »
        10 years ago, hide # ^ |
        ← 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
  • »
    »
    10 years ago, hide # ^ |
     
    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
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it -10 Vote: I do not like it

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

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

        Do you want to say + is slower than %?

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

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

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

priority_queue in C gave TLE :(

→ Reply
»
10 years ago, hide # |
← 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
»
10 years ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

It is like

smurfs everywhere :'(

→ Reply
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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.me/contest/681/submission/18477598

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

How to solve E?

→ Reply
»
10 years ago, hide # |
← 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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How this passed system tests?

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

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

Исправлено

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

How to solve C with priority_queue?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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
»
10 years ago, hide # |
 
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.me/contest/681/submission/18478591

→ Reply
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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.me/contest/681/submission/18478954

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

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

→ Reply
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
← 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
»
10 years ago, hide # |
 
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
  • »
    »
    10 years ago, hide # ^ |
    ← 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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think you should check the test again. With this code http://codeforces.me/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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
← 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
  • »
    »
    10 years ago, hide # ^ |
     
    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
»
10 years ago, hide # |
← 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