Glebodin's blog

By Glebodin, history, 7 years ago, translation, In English

Hi everybody!

On August 29, в 18:05 MSK Codeforces Round #430 (Div. 2) will be held. As usual, Div.1 participants can join out of competition.

The problems are prepared by me Glebodin and Ilya Ilua Maximov. Many thanks to Alexey Perforator Ripinen for help in preparations of the round. Great thanks to Alexey Livace Ilyukhov, Ildar 300iq Gainullin, Daniil qoo2p5 Nikolenko for testing the round, Nikolay KAN Kalinin for helping us preparing the round, Maxim HellKitsune Finutin and Ivan BledDest Androsov for testing this round and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

The scoring is : 500 — 1000 — 1500 — 2000 — 2500

Congratulations to the winners:

Div. 1:

uwi

vintage_Vlad_Makeev

natsugiri

kmjp

victoragnez

Div. 2:

fatego

sufficiently_large_boss

qscqesze6

white_flag

Panole2333330

Editorial : http://codeforces.com/blog/entry/54179

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by Glebodin (previous revision, new revision, compare).

»
7 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Wow, very short announcement and very fast publish of scoring!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    yeah, why are they always publishing the scoring distribution in the last 10 minutes.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      I think, because testers say something like "it's a bit harder, then i think" and they must wait for their decision.

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

    I hope the problems will short too :)

»
7 years ago, # |
  Vote: I like it +75 Vote: I do not like it

Obligatory comment about hoping the problem statements to be as short as announcement..

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    +Fast system test

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

      By the way. Who can explain why there is a big lag between contest finish and system testing start?

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

it is the shortest announcement I have ever seen .

»
7 years ago, # |
  Vote: I like it +151 Vote: I do not like it

Is this the best month or what!

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it

    It is nice because of many contests, but some of the contests from this summer weren't really nice. Back in autumn or winter the contests were nicer. Hopefully this will change soon because i see that people stop participating on CF. Some months ago 8000 people were registering and 5000+ were participating, but now around 3500 participate, but i love CF, it is the website were i have the most emotions while participating.

»
7 years ago, # |
  Vote: I like it +135 Vote: I do not like it

I'll leave this picture as a reminder for the russian problem setters =)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    sorry for my bad english

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

      It's completely ok that your english is not ideal. It would be nice if there was someone to review the statements before the competition starts. Non-russian problem setters aren't (as far as I know) expected to know russian well enough to write the problem statements without help. Russian problem settlers shouldn't be expected to do the same either.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    Maybe on the russian site they say the same about russian statements when there is a non-russian setter.

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

      Not at all. The Russian translations are pretty much always spot on because they get native Russian speakers to do them.

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

        But then again, native speakers can skrew up translations into Russian if the original statements were written in English.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    i love codeforces and want to see it improve day by day, and that's why i think they really need a professional English editor because i keep seeing these kinds of grammar mistakes in many problems

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      In the past, Delinur has either translated or reviewed the translations of statements in nearly every contest. Does this position not exist any more?

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Perhaps learning to capitalize your I's would be a good start.

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

        that's punctuation not grammar

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

          Orthography, you mean, which is part of grammar in the greater sense of the word.

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

      Nobody needs a "professional editor" for problem statements, a native English speaker with some CF experience will suffice.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    yes. i was going to say the same thing. and don't forget their explanation to the sample test cases were awful too. And when i asked for an explanation (this exact same problem) they told me to read the problem statement carefully. Man, because of your awful statements, i asked you for an explanation. -_- I think they should consider that CF has become a global coding contest site and so they should give more importance in their English statements. :)

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It's nice and short. But can someone tell me why can't I see the test cases in usual practice submissions? This has been troubled me for almost a week!

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Before anything else,

»
7 years ago, # |
  Vote: I like it -30 Vote: I do not like it

You didn't say if it is rated. Is it rated?

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

    finally correct is it rated? question. Yes it is.

»
7 years ago, # |
  Vote: I like it -93 Vote: I do not like it

I am a boy. I am a thirteen. I get up at nine o'clock. I have for breakfast a burger. I play a game with friends. I have for lunch a burger, a cola. I help for construction. I eat a pizza. I drink a cola. I sleep at twenty o'clock.

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

wow ............ Total: 7983 Contestants: 7600 Out of competition: 383

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

problem: C. Ilya And The Tree what it the biggest common divisor if one of the numbers are 0?

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

    If one of the numbers is 0, the GCD of both of them is the other number. You shouldn't be asking questions here while the constest was running =P Try to send a clarification next time (by the way, there was an announcement about this hahaha)

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Where is the perfect place to ask questions related to testcases?? I am trying to hack some solutions but it's giving invalid input but a/c to question it should be valid. I can't ask here Because this is public and contest is still going on so..

»
7 years ago, # |
Rev. 4   Vote: I like it -15 Vote: I do not like it

In problem D. Vitya and Strange Lesson:

The first pretest case:

2 2
1 3
1
3

The xor arrays are as follows:

[0, 2]
[2, 0]

Therefore the output should be:

1
1

And not as in the example given:

1
0

Am I correct or do I miss something?

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    1)0 2 mex = 1

    2)3 1 mex = 0

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

    "Note that after each query the array changes." So the second array will be constructed by using the XOR operator on the first array, not the original one.

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

    Seriously??? Can people comment during the contest???

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

    Why am I receiving negative votes on this comment ? I was asking a question regarding the pretest cases. Nothing relating to the solution :/

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

      I guess you will get downvotes for this complain too.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is it necessary to solve B with integer calculations only ?

i spent lots of time to solve it without doubles

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

    You can use double but don't forget epsilon

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      My faith is stronger than epsilon !

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

How to solve C and D?

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

    C : You only need to check parents and vertex divisors.

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

      Please explain.

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        You can make value g gcd of path, if it divides h(depth of vertex) — 1 or h values in the path. So it must divide current vertex or parent of current vertex. Complexity is O(N * d) where d is 480.

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

          I seem to have some trouble understanding you algorithm. Could you explain it for a path (root) 6 - 3 - 4 - 14 (leaf)?

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 3   Vote: I like it +1 Vote: I do not like it

            For 1st vertex answer is 6 because 6 divides 1 nodes.
            For 2nd vertex answer is 6 because 6 divides 1 nodes.
            For 3rd vertex answer is 3 because 3 divides 2 nodes.
            For 4th vertex answer is 2 because 2 divides 3 nodes.

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

              For 3rd vertex, you can make the beauty 3 by making it's value 0

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Len
          What about this simple solution that FAILS !!
          http://codeforces.com/contest/842/submission/29887074
          at every node we store two GCD values, valueOne with exactly one node off in the path till here, and valueTwo with no one off in the path till here.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            try this data:

            4

            12 3 4 3

            1 2

            2 3

            3 4

            The correct answer should be:

            12 12 4 3

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

              Thanks !!
              I was asking about the reason why that reasoning fails.

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

                The reason is that except the node and its parent, other nodes on the path to root can also be changed to 0. (please ignore my grammer mistakes)

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

                  But that is already incorporated in the DP right ?

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

                  The decision may change while going down the tree.

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

                  I am unable to understand that. please explain a bit more.

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

                  Let's use the previous example.. When querying node 3, the decision is changing the value on the 2nd node to 0. But when querying node 4, the decision is changing the value on 3rd node to 0. Your algorithm wasn't able to handle this case.

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

          excuse me , what does gcd mean ? i don't understand .

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

      It is possible more in detail please

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        For vertex u, record unchanged value and changed values.

        Since most changed values need to gcd with u, so the number of values will decrease to 2*root(2*10^5).

        record them and dp!

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    D can be solved by building a binary tree. Consider a tree of depth 19 where the leaf nodes represent 00...0, 00...1, ..., 11...11, i.e. all numbers of length 19 in binary. This choice is made because 2^19 is the smallest power of two larger than 3*10^5. The higher levels are represent if number p, the child nodes are 2*p and 2*p+1.

    For each x (assume the set doesn't change for a moment) the smallest number not in the set is the one most similar to x (starting from higher digits) XOR x. Therefore, we start from the top most node and if possible make the choice towards that which is the same as x. If there are no viable nodes in that direction, we go the other way.

    The value of each node is either true or false, false representing if the value is in the original set. As you move higher up the tree the value of the nodes are defined so node p is true if either 2*p or 2*p+1 is true.

    You don't have to change the set but keep XOR-ing each successive query. Total complexity is O(n + A + m log A).

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

      Why don't have to update the entire array, can elaborate a bit?

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

        Let's say the queries come in x, y, z. If we know how to solve by not changing the array for x, we can do the same and solve by not changing and solving for x^y, not changing and solve for x^y^z, because XOR is commutative.

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

        In first operation, you xor every element with x.
        In second operation, you xor every modified element with y.
        This is same as, xoring original elements with (x^y).
        In third operation, xor original elements with (x^y^z) instead of changing array after every operation.

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

      the smallest number not in the set is the one most similar to x (starting from higher digits) XOR x

      Could you elaborate this?

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

        Say x=11010. And we need to choose between a=11101 and b=10010. a^x is smaller than b^x.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    7 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    Do dfs on graph.In the dfs, Calculate the divisors of the current node.If this divisor divides atleast 'depth[cur_node] — 1' nodes on the path from root to this cur_node,then it can be a possible value for the gcd .Take maximum of all such values possible for that node — This is maximum beauty of that node.Or gcd(Parent of cur_node) is also a possible contender.Complexity — O(Nsqrt(Max_Val))..We keep an array(200005) that keeps track of how many nodevalues are divisible by a number in the path from root to cur_node.Sadly, it didn't pass pretest 7.

  • »
    »
    7 years ago, # ^ |
    Rev. 9   Vote: I like it +7 Vote: I do not like it

    Check my solution: 29886456

    You can do a dfs dfs(currentVertex, parent, canSkip, currentGcd) where you go to the adjacent nodes as follows: dfs(adjacent, currentVertex, canSkip, gcd(value(currentVertex), currentGcd)) and, if canSkip=true, dfs(adjacent, currentVertex, false, currentGcd). To compute the answer we must call dfs(root, -1, true, 0). You can keep a set of states to avoid repeating vertices. That is, once you have computed a particular state, add it to a set and, if you end up there again, just return and do nothing. You may also have a vector ans where, in each state, you compute ans(currentVertex) = max(ans(currentVertex), gcd(value(currentVertex), currentGcd)) and, if canSkip = true, ans(currentVertex) = max(ans(currentVertex), currentGcd).

    Why does this work? Well, according to https://en.wikipedia.org/wiki/Highly_composite_number the most composite number in [1, 200000] has 160 divisors. We must note that gcd(a, b) will always give a value that is both a divisor of a and b. In our approach, this means that a vertex may only generate at most 160 new gcds. Also, we must take into account that we can skip a single vertex, so we can "inherit" the gcds from above, so a vertex may emit at most 320 values. This means that we have at most 200000 × 2 × 320 = 1.2 × 108 distinct configurations. Given that we have two seconds, it seems that this may fit into the time limit. However, we must note that this is an upper bound. In practice, the numbers are much smaller. To be honest, I do not know how to bound even more these numbers. During the contest, I generated random graphs with numbers with many divisors, or random graphs with only numbers of the form 2a × 3b and I saw that I was not able to make it fail, no matter what I tried. I also generated arrays of numbers and computed the amount of distinct gcds I could get by ignoring zero or one numbers at a time, and I also saw that the numbers were very small.

»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What is pretest 7 on problem C?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack test for A ?

»
7 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Hints fo E problem:

  1. The farthest vertex from any vertex is one of diameter`s centres.
  2. After adding new vertex you can easily recalculate diameter ends. Let a and b be old ends and c is a new vertex. Then new diameter will be (a,b), (a,c) or (b,c).
  3. There are only 1 or 2 centres of diameter and after adding new vertex only one of them can change.
  4. You can build segment tree on euler tour of this tree. You can serve maximum distance to the nearest centre and number of vertexes that satisfy that condition.
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my first div1 round

»
7 years ago, # |
  Vote: I like it +49 Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

n * logn * logn is too much for D ?

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

    It's about 10^8, so it could be too much if your constant is big enough.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    map trie ??? no need array trie was enough as highest node will be <=(1<<20)

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

    Just got AC with n*logn*logn solution 29901340

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack case for A ?

»
7 years ago, # |
  Vote: I like it +36 Vote: I do not like it

How to solve statement of problem E?

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    If I understood correctly you are given a tree, find number of vertexes that can be endpoint of diameter.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +34 Vote: I do not like it

    The statement is ridiculous. They should let it be pure graph statement!

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

what was wrong on pretest 4 on C ?

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hack for C:
3
7 3 3
1 2
2 3

Answer should be: 7 7 3.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve div 2 C?

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

    In a dfs keep a set of all the gcd you can make till the index you are on and then take gcd of value of current node with all element in the set and add one extra element which is total gcd till last element. As, the number of distinct gcd you will hold will always be less than cubroot(max value of node). as, a number has <= cubrt(n) divisors. so your solution would be O(n*cubrt(n))

    I got the solution 10 minutes before the end of contest and wasn't able to code it :(

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

      I got the same logic for C and coded it but set size as 10^5 and noted it at the end of the contest and couldn't change that value.

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

      How do you know the number of distinct gcd will always be less than cubroot(max value of node) ?

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

    You can make a DFS(u, depth), depth will be the number of the vertices on the road from 1 to u. In vertex u, you will want to know for every integer i, how many vertices on the road from root to u are multiple of i, assume it's fre[i]. We will get another information, that is Max[x] = y, y will be the maximum value that be the divisor of the value of x vertices on the road from 1 to u. fre[] is easy to calculate, with every divisors v of a[u], fre[v]++, and after each increases, we update Max[fre[v]] = max(Max[fre[v]], v). So res[u] (result of vertex u) will be max(fre[depth], fre[depth — 1]). Just remember, after visiting all u's branches, you have to remake the values of fre[] and max[] to the values before you dfs to u (like how we use back-tracking to generate permutations).

    My code: 29897727

»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

RIP rating

»
7 years ago, # |
  Vote: I like it +41 Vote: I do not like it

For C, the basic observation is that the gcd value will either remain constant as we go down from the root, or it will atleast decrease by half. So there can be atmost 18 different points that we need to consider for removal.

»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Lucky Guy!

»
7 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Hack for A problem: 7 7 3 6 2

Answer: NO

This happened because 7 is not divisible by 2. So you cant solve this using formula.

UPD: My fault, you can: http://codeforces.com/contest/842/submission/29883923

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

      You can avoid division by doing this : http://codeforces.com/contest/842/submission/29905885
      But then this is wrong solution, I don't know where ?
      There are two line segments — [l, r] and [kx, ky] we just need to check
      if they intersect at any point or not.
      This follows from the fact that, answer will exist if and only if for a given value of a
      there exist a value of b which is a/k in the interval [x, y], which is same as a also belonging to [kx, ky].
      Unfortunately the test cases are not visible.

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

        The whole point of dividing was so that I could take the floor and ceiling of both numbers. By doing this, you can passtaht hack up there.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? Please explain if you can.

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

    my idea : pre store n * logn numbers first throw out the numbers until there is at most one of each . then just pre calculate the prefix of numbers in binary in an array . for example for 5 : store numbers 0000000000000001 00000000000010 00000000000000101 then the problem is simple ! think for yourself

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

      i just stored this numbers as strings in a map but you can put an extra 1 in the beginning and just store the number

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

    I solved it using trie

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it +24 Vote: I do not like it

    Let A be an array of numbers that our original array doesnt consist of.

    Then mex(a) = minimum element of A.

    1 useful fact: after operation (a xor x) mex will be minimum of array (A xor x).

    You dont need to save all changes, just xor new query with old. Like xi = xor(x0, x1, x2 .. xi).

    Original array A you can store in bit trie. Now you iterate over bits, from large to small. You mission is to decrease y (the number you get from trie) xor xi. So if j-th bit of xi is equal to 1 you should go through "1" edge in the trie if you can. Similarly for "0" bit. Answer will be y (the number you find) xor xi.

    Sorry for my bad English.

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

      He knows русский

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

      Why mex(a) = minimum element of a?

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

        mex(a) = minimum element of A, where A is an array of numbers, that a doesnt consist of.

        For example: a = [1, 2], then A = [0, 3, 4, 5, .. 300000]

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

      The same solution but you don't need trie. Normal sorted array is enough. You just make lower_bound for every bit.

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

      could you please explain "1 useful fact: after operation (a xor x) mex will be minimum of array (A xor x)." ? didnt quite get it . since A is the array that does not contain original given numbers, why are we doing XOR of x(given query) with A ?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Greedy by bits. In fact, xor only change the priority of bits. For example, the xor number is 100010, and current number you choose is 101[0]00000, in present bit [0] is greater than [1](because of the effect of xor number). So we first check the number [101100000, 101111111], if all of the values occur, we can put a [0] here, otherwise we can only put [1]. If current bit of xor number is [0], we try [0] first. The checking can be solved by prefix sum. Finally we got the number before xor, so just print after xor. The total complexity is O(nlogn).

  • »
    »
    7 years ago, # ^ |
    Rev. 11   Vote: I like it 0 Vote: I do not like it

    Used :

    1. Bijection Property of function : f(x) = x^k ( k belongs to [0, 2**(n)-1] ) (XOR) : [0, 2**(n)-1] -> [0, 2**(n)-1].

    2. Greedily finding the element which is not in A and closest to X.

    3. Instead of modifying Array itself, modifying query's input (Xj) by taking XOR with query input (Xi's) occered so far.


    int A[1000000]; int sumLR(int l, int r) { return ((r>=1000000)?A[1000000-1]:A[r]) - ((l-1)<0?0:A[l-1]); } int main() { int i,j,k,l,m,n,x,y,z,a,b,r; sd(n); sd(m); for(i=0;i<1000000;i++) A[i] = 1; for(i=0;i<n;i++) { sd(x); A[x] = 0; } for(i=1;i<1000000;i++) A[i] += A[i-1]; x = 0; while(m--) { sd(y); x ^= y; a = 0; for(i=30;i>=0;i--) { if(sumLR( a | ((1<<i) & x) , a | ((1<<i) & x) | ((1<<i) - 1) )!=0) a |= ((1<<i) & x); else { if(((1<<i) & x)==0) a |= (1<<i); } } printf("%d\n", x^a ); } return 0; }
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @jvj_iit can you explain why A[i] += A[i-1] and how sumLR() works ?

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

        Array A is basically used here to maintain a Prefix sum array of counts of elements which are in [0, 2**(n)-1] (assume sufficiently large n), but not in set of input elements, i.e. A[i] stores count of elements which are less than equal to i and not in set of input elements.

        sumLR(l, r) simply returns count of elements which are lie in [l,r] but not in set of input elements.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For this testcase for problem B: 5 3 1 5 0 1 What should be the answer?

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

    It's 0.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      But I hacked a solution whose output was 1. It showed me unsuccessful hack!!
      solution code: 29883956
      edit: sorry my bad. The code gives correct output i.e. 0.

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Why in each round you make a big hardness difference between (C & D) or (B & C) like this round !!

4102 ACC for B , 446 ACC for C !!

WTF !!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Plus people scored 12-13 hacks on A which got them points equal to C, although both the things aren't the same.

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

    Maybe they like repeating :)

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

    Less ACC for A than B too!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is O(nsqrt(maxval)) good enough in c?

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

    firstly i got tle, then optimize it and changed to printf and got ac in pretest

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any ideas for C? Problem was intersting, but a litle more difficult than standard for "C"(Div 2).

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    1. Check the frequency of divisors of the node you're on. If there's at most one missing, it can be an answer.

    2. As soon as a number has one missing, it might be an answer for one more node and then the rest must have this number as divisor otherwise there will be 2 missing and it won't be an answer.

    So just check the current node and parent node's divisors (or send the maximum from the current node that has no missing frequency to the next nodes).

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

      hello, I am trying to implement exactly what u said, but getting WA on test case number 7. Can you please, find what is wrong in my code?or provide me some critical test cases? thanks.

      29930421

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        http://codeforces.com/contest/842/submission/29931334 at line 200 you need to mark 1 as visited otherwise the path will go back to 1. Edit: other than that, long long might be causing TLE.

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

          thank u, but now TLE :P how to get rid of that?

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

            You have a few options:

            Get rid of vis and just keep the edges you need.

            Get rid of long long as in here: http://codeforces.com/contest/842/submission/29931449

            Turns out you are making O(divisors * n) modulo operations and modulo is really costly on codeforces if you use long long.

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

              thank u. you already did it for me. :D you are too fast brother :)

              but the execution time is 1996 ms. that is too tight. how to improve my solution?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                Rev. 3   Vote: I like it 0 Vote: I do not like it

                You can change the frequency of divisors running through the list of divisors as in my solution: http://codeforces.com/contest/842/submission/29885607

                You can also optimize this solution to O(nlog(maximum value)). You need to optimize the second part, running it through every prime in the prime factorization (and every possible exponent for that prime) and multiplying the answers to get the second part of the answer.

                For example: if you have 2^5 * 3^4, you can run it for 2^1, 2^2, 2^3... and take the largest power of 2 you can for every node and the same for 3.

                Edit: I'm not sure about the second part actually. Someone did something similar but what I wrote looks wrong. Edit2: it was this guy http://codeforces.com/blog/entry/54120?#comment-382225

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

                  ok, this is getting weird!

                  why am i getting TLE now? -_- 29931793

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

                  As you said, the way you coded is too close to TLE :/

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

                  brother, u told me "Get rid of vis and just keep the edges you need.".

                  i just add: if(d<=(lvl-2)) return;

                  and got acc in 951 ms.(faster than yours :D :D )

                  thank u so much for ur help. :)

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

    There are atmost root(n) divisors of n. For node 1 calculate all it's divisors and run a dfs with a divisor assumed as answer and see how far you can go with only change (a number to 0 in path) and maintaining gcd equal to that number. Do it for all the divisors. That's a n root(n) solution. One more case when you change node 1 to 0 can be handled by just changing it and running dfs with no further number change and taking gcd of all the nodes in path. Not to mention every time you reach a node ans[node]=max(ans[node],current). Put all answers to 1 by default.

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

      There are atmost root(n) divisors of n ??
      Not Really !!
      Divisors for 12 : 1, 2, 3, 4, 6, 12
      root(12) -> 3.46

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

        I meant complexity wise , if you're talking constants 2*root(n)

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

    n Log n solution: you factorize the root, (at most there are log n factors) for each prime factor you solve the problem separetely: for each vertex and prime factor you save if it is possible to get the factor down so far, and if yes then save which vertex you changed to zero doing so(if you did)(for each prime factor can be done in O(n)), when you preprocessed all of this, for each vertex you check how much of those prime factor you can get down here changing only one(or less) vertex to 0.Also you need to consider the case when the root node is replaced by zero, which is trivial to solve. My submission: 29900204

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

    An O(idk) solution: for each vertex store a set of gcds of all possible numbers on the path to root with one element excluded. And try to prove that in the long run (like when the depth of the vertex is huge enough) its set will contain a negligibly small number of gcds :) 29884556

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Simplified Version : You cannot do skips, then you will have at most logai distinct values. (easy to prove).

      It should be intutive that the number wouldn't be much larger with skips. I was convinced it's bounded by sqrtN in worst case.

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        So was I, and that is the reason why I submitted :D

        According to the execution time, the sizes shouldn't exceed log(n) per set.

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

    Thank you all)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good thing we have the comments or else there would be no other way to ask questions during the contest.

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

look at fatego's code, his for loop in problem c and in problem d is different. I think it is obvious that he cheated.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B. I took 5 points from the x,y given and checked if all of them lie in crust or not. Apparently that is not how its supposed to be done :(. http://codeforces.com/contest/842/submission/29896449

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

    Let d_i be the distance from the center of the sausage to the origin. Then, the sausage is on the crust iff r — d + r_i <= d_i <= r — r_i

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

      kind of did the same. I have center as x,y. let rr be the radius of sausage. I checked if dist(x-rr,y), dist(x+rr,y), dist(x,y-rr), dist(x,y+rr),dist(x-rr,y), dist(x,y) all lie in r-d.

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

        That won't necessarily work though. You can imagine a situation where a sausage just has a small upper-right portion sticking out of the crust.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How long do you have you wait to submit for practice? Is it once system testing is done?

»
7 years ago, # |
  Vote: I like it +67 Vote: I do not like it

my reaction when a solution strikes me during the last 5 minutes

»
7 years ago, # |
  Vote: I like it -27 Vote: I do not like it

ABC

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What happened to rating change predictor? I am unable to see it.

»
7 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Very bad, that there is no explanation to sample testcases. I couldn't understand problem E for 10 minutes.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is it only my problem, or show unofficial button changes randomly when refreshing.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really want to understand graphs better (like in problem C). Can someone please suggest some good tutorials (using C++ STL only please) other than Hackerrank.

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

    Read the analysis and all And solve the problem SPBGU in training with 2 stars when you solve all probably will already fumble in the graphs there is a problem purely on the algorithms that are in the internet but these algorithms are the most important

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve about D ?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is python so slow? Couldn't even perform 10^7 operations in 2 seconds!

Link

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

|

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

    he said the efficiency is non integer which means that a/b can be non integer , but he didn't say that k can be a non integer .

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

      Input First string contains five integer numbers l, r, x, y, k (1 ≤ l ≤ r ≤ 107, 1 ≤ x ≤ y ≤ 107, 1 ≤ k ≤ 107).

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I got MLE for mapping values in the range l to r using C++ STL map.. i know max value of r was 10^7 but as far i know STL map can handle this unlike Array.. can anyone explain what is the reason for MLE here?

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

    look 1e7 * log(1e7) * const > 2e9, so you can get tl

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

      oh. got it. but why MLE here? what's the reason behind MLE?

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

        Sorry i read TLE, for MLE the same 1e7 * long long > 70 MB and map his big constant

»
7 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Seeing how a lot of submission for A got hacked, I feel fortunate being able to come up with my super elegant 107 for-loop solution.

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

    and math with 1 line also wrong...

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

    I just checked whether there is an intersection of range..but it failed system tests.. As test-cases are not visible, I'm am not able to get that case..Can someone please help..!

    Link

»
7 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Why can't we see the testcases?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the rating be updated?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for C keeps failing for pretest 4, does anybody have any idea about what that case may be?

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

    Try this:

    7 35 5 35 7 35 5 7 1 2 2 3 3 4 4 5 5 6 6 7

    answer: 35 35 35 7 7 5 1

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

    Value of the root node can be changed to 0 in computing gcd for any of the children nodes.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me, please!

Tell me, what I'm doing wrong in problem A? Here is my program: http://codeforces.com/contest/842/submission/29897053. Please, tell me testcase 8 if you can.

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

    you reversed ranges, we have b*k =a you checked k*a=b

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Glebodin I understand that there is some problem with codeforces right now and we are unable to see the test cases. If possible, could you share the test cases in form of some repository for now. I think it would be of great help for many users.

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

    I'm sorry, I can't (same problems) and this is the reason i can't post editorial

»
7 years ago, # |
Rev. 8   Vote: I like it +81 Vote: I do not like it

To some extent, the test cases for problem E are weak.

There exists a solution that maintain the points meeting the condition by using brute force. See these two solutions 29894980 and 29894566 for more details.

Both of them can be easily hacked by building a star graph and then adding a long chain to the root. To be more specific, here is the test case:

300000
1
1
1
1
...(149995 ones omitted)
1
150001
150002
150003
...
300000

Now I am still trying to hack other solutions...

UPD: I give up and dicide to go sleeping.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you hack this one: 29901727.

    Though it seems like an amortized O(N) because each element is moved at most 3 times, I'm not totally sure. It just seems a bit unclear why dividing the nodes in 3 sets like this makes it work. For example it's clear when the diameter is odd we keep a left and right part, but when it is even, we have a center and it gets more complicated.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Well, I think your solution is correct but I am also not sure.

      Also I have found a similar solution 29892728 that divides the nodes into two parts and tried to hack it but in vain. It seems that if a node moves from one set to another, it will never come back or otherwise it will never meet the condition.

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

    I knew that my code would fail before systest so I'm wondering why my code passed.

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can you see the mistake in this picture? ._.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone tell me the corner test case that my code fails on for Problem A. It fails on Test case #38. Link to my code is: http://codeforces.com/contest/842/submission/29874288

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

    You have long i and k. So i * k overflows before getting assigned to val.

»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

nice contest with fast testing and rating update, thank you

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not fair if you're holding a contest, with a bug, Not allowing test cases to be seen. How am i able to upsolve?

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can't figure out the mistake in A. Could someone please provide a test case, thanks.

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

    3 3 1 2 2 is a possible test. The idea is to find [l,r] such that no multiples of k lie in this interval.

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

    I think someone pointed to this, try for example 5 5 1 10 3, it will give yes in your code but it has to be no

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Even this passed the pretests,very weak test cases.


int main() { long long int l,x,r,y,k; cin>>l>>r>>x>>y>>k; int flag=0; for(int i=x;i<=y;i++) { if(l<=x*k&&x*k<=r) //this line though :) {flag=1;break;} } if(flag) cout<<"YES\n"; else cout<<"NO\n"; }
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Am i wrong? I see no problem in this code

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      There's no i in the if statement.

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

        ???

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          Check for loop carefully There is no index i inside the loop.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Oh i see it. But was it accepted? If it hadn't passed been accepted then the test cases wouldn't be weak

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              No it was not accepted but it passed the pretests.

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

    I would have helped you find this bug if you were in my room =)

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    By the way, does anyone see the problem with this solution? (Doesn't pass test 26: 29901876)

    long long l, r, x, y, k;
    cin >> l >> r >> x >> y >> k;
        
    auto min_v = k * x;
    auto max_v = k * y;
        
    bool inside = l <= min_v && max_v <= r;
    bool outside = min_v <= l && r <= max_v;
    bool intersect = l <= min_v && min_v <= r ||
                     l <= max_v && max_v <= r;
                         
    bool exist = inside || outside || intersect;
        
    cout << (exist ? "YES" : "NO");
    
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same problem as most hacked solutions, try this test 5 5 1 10 3

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

        Oh, thank you. I get it now. So it looks like we can't solve this task in O(1), because we can't just intersect the segments.

        Good thing I wasn't trying to be smart during the contest and just did a simple for loop =)

»
7 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Can anyone write shorter solution to A than this?

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem D I could not figure out how to find the least xor with an element NOT in the trie. What I ended up doing was putting in every number except for those in the array and did a least element query with that. How did everyone else do it?

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

    I used subtree size in trie to find min element. If there is xor 0 at that position and if left subtree in incomplete go to left else go to right. If there is 1 then check the same for right subtree and then left.

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

when is the editorial going to release.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So there are no official solutions for each problems? I see there are "problem tags" which can be used as a hint, but no more detail one? Thanks!

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Sorry to say,I can't totally understand the statement in the beginning until the announcement.But the problems are nice.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WA 29905833

Instead of storing all the divisors of current nude in a vector because of memory constraints, I tried to iterate through all divisors of current node again and decremented the count.

Why does this fail?

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

    Your solution will fail for tests some thing like this:

     3
    8 1 9
    1 2
    2 3
    Answer should be 8 8 1. But I think your code will output 8 8 9
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

For a purely Div. 2 contest, please list the Div. 2 winners first in the editorial. They deserve their moment in the sun!

Otherwise, I don't understand the purpose of the "Div. 2 only" contest:
- The Standings show all divisions, which is dominated by Div. 1.
- Then the editorial shows the Div. 1 winners first.

So what is the point? Is it about rating? Even there, I believe that NOT including D1 players in the rating calculation hurts D2 players — because D2 is expected to rank lower than D1, so if we included the top division in the rating, the D2 players can only gain.

If I am missing something, please let me know, otherwise I would love for there to be an editorial guideline at CF to show D2 winners first, in the D2 contests. I can never dream of being in the D1 top 5, but I CAN dream of being in the D2 top 5 list one day!

Thanks for your consideration.

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

    All the people who are purple in the top 5 rating of the 2nd division have already become purple after the recalculation of the rating in this round.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. Uncheck 'Show unofficial' when on the standings page.

    2. The Div. 2 winners are right there, 6 lines below overall winners. Don't whine about it so much.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Does anyone know what is test 6 in problem D, why am I keep WA on test 6?

My submission: http://codeforces.com/contest/842/submission/29896373

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

    insert into the Trie unique values only

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      I was such an idiot in this contest. Thank you very much. I now realized my mistakes!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Memory limit exceeded on test 43 in Problem A(Kirill And The Game) My code Can someone please help?

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

    You don't need to convert those range objects to list.

    And there is about 10 ** 7 actions in your solution. Python is just not so fast for doing this (but you could try PyPy).

»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

is there no editorial??

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where is the editorial?

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

When will the editorial be added?

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

This was my First Contest (I m new in here). I solved 1000 points problem in my second attempt (on my first I missed a trivial edge case) but I got 698 points though at the end of the contest my solution was "Accepted" .

Why wasnt I awarded full marks for the solution (I know I made a penalty of 50 points due to incorrect first attempt) . Was it only because of time that I was awarded 698 instead of 950 ? What are the factors on which the awarded marks depend upon ? (any link would also help :) )

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

29910536 Can somebody tell me why I get a RTE in test case 6 in DIV2 C?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder for problem D,if I have a trie with reversed bitset of every element(for example,3 will be 11 but 4 will be 001),how can I get the mex number from this trie in less than O(n)? Or tell me my solution is not correct at all...QAQ

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

    You can do it with trie quite easily. If there was no update queries, you need to go to 0 subtree if it isn't full, and 1 subtree otherwise. You can just maintain inv array, so that you need to go to inv[i] first. Here's my code.

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

      Oh...I understood your great solution(My English is bad...) (I realized reversed bitset to inserted is not meaningful...) Thank you very much ><

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When do you have any clothes?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why cant i see the test cases of problem on which i am getting WA??

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will there be editorial for this round?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the trie solution to problem D, I got WA test 45. Then, after I changed the initial index in the trie from 0 to 1, it magically ACs. Why is that?

Submissions for comparison:
29917934 — WA 54
29918066 — AC

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be an editorial?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Which data structure do I need to study for solving problem D of DIV2?

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

    trie

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

      How to apply trie in this question? I tried to think about it but could not find any way. Please guide me. Thank you.

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

        All the numbers can be presented in binary form as words with length 20 (220 > 3·105). So we can build trie (with edges 0 and 1) on these words and we can calculate weight of each vertex (amount of words that use this vertex)

        We will add in trie only unique numbers

        To find mex on trie we have to find the least number that is not in trie. So if we want to use any edge we need to understand if next vertex is full (all the numbers are written there). For this we calculated a size for each vertex. If is is equal to 2i (where i is a number of bit which is presented with this vertex) than vertex is full and we have to use another one.

        Algorithm to find mex if array doesn't change is quite easy: while we can use edge 0 we use it, else we add 2i to answer and use edge 1

        If array changes with number p than we need to present it to binary form. For example, p = 100010101010. It means that next time in levels 1, 3, 5, 7, 11 we will have to choose edge 1 instead of edge 0 firstly (because xor has changed edges on these levels). If we cannot do it, we use edge 0 and add 2i to answer

        But if next time we will have p = 1010, than we will "swap" edges only in levels 5, 7, 11. So for each bit we calculate how many time it was changed. And if it was changed odd times than we swap edges on this level

        Sorry for my bad English

        Here is my code: 29929754