Блог пользователя Glebodin

Автор Glebodin, история, 7 лет назад, По-русски

Всем привет!

29 августа 2017 в 18:05 (по московскому времени) состоится рейтинговый Codeforces Round #430 для участников из второго дивизиона. Как всегда, участники из первого дивизиона смогут принять участие вне конкурса.

Задачи для вас готовили Глеб Glebodin Лобанов, и Илья Ilua Максимов. Большое спасибо Алексею Perforator Рипинену за помощь в подготовке раунда, Даниилу qoo2p5 Николенко, Ильдару 300iq Гайнуллину и Алексею Livace Илюхову, Ивану BledDest Андросову, Максиму HellKitsune Финютину за тестирование задач и конечно же Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и 2 часа на их решение.

Разбалловка — стандартная: 500 — 1000 — 1500 — 2000 — 2500.

Надеемся, раунд вам понравится! Всем удачи!

Поздравляем победителей!

Div. 1:

uwi

vintage_Vlad_Makeev

natsugiri

kmjp

victoragnez

Div. 2:

fatego

sufficiently_large_boss

qscqesze6

white_flag

Panole2333330

Разбор : http://mirror.codeforces.com/blog/entry/54179

  • Проголосовать: нравится
  • +312
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Glebodin (предыдущая версия, новая версия, сравнить).

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

it is the shortest announcement I have ever seen .

»
7 лет назад, # |
  Проголосовать: нравится +151 Проголосовать: не нравится

Is this the best month or what!

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +135 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +68 Проголосовать: не нравится

    sorry for my bad english

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Before anything else,

»
7 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

А Семён Романенко тоже помогал готовить задачи?(надеюсь не очень сложно пошутил)

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Вегда было сложно на контестах от синих юзеров, не знаю почему :)

»
7 лет назад, # |
  Проголосовать: нравится -93 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

ypa!!ypa a a a

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
Rev. 4   Проголосовать: нравится -15 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    1)0 2 mex = 1

    2)3 1 mex = 0

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    "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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is it necessary to solve B with integer calculations only ?

i spent lots of time to solve it without doubles

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve C and D?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Please explain.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It is possible more in detail please

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 9   Проголосовать: нравится +7 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

What is pretest 7 on problem C?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the hack test for A ?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my first div1 round

»
7 лет назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

n * logn * logn is too much for D ?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hack case for A ?

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

How to solve statement of problem E?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

what was wrong on pretest 4 on C ?

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

Answer should be: 7 7 3.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve div 2 C?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

RIP rating

»
7 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Lucky Guy!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

задача А 6 6 1 2 4 ответ NO

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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://mirror.codeforces.com/contest/842/submission/29883923

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D? Please explain if you can.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it using trie

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 11   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        http://mirror.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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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://mirror.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 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                You can change the frequency of divisors running through the list of divisors as in my solution: http://mirror.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://mirror.codeforces.com/blog/entry/54120?#comment-382225

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  ok, this is getting weird!

                  why am i getting TLE now? -_- 29931793

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится +5 Проголосовать: не нравится

                  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 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you all)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/contest/842/submission/29896449

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

ABC

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve about D ?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Link

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

|

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1) Где разбор? 2) Объясните кто-то как решать С. Я так понял там ДП.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Сделаем обход графа в глубину из корня дерева. При обработке вершины будем считать для нее ответ.

    1) Пусть мы НЕ будем занулять текущую вершину. Тогда ответом является один из делителей числа в этой вершине. Будем перебирать делители до корня. Теперь необходимо проверить, что данный делитель подходит как ответ. Он подходит, если все предки текущей вершины кроме одного делятся на этот делитель. Чтобы быстро это проверять, заведем глобальный массив, в котором будем хранить сколько на текущий момент вершин делится на это число. То есть в начале дфса при переборе делителей делаем +1, а при выходе из вершины -1. 2) Если мы хотим занулить это число, то ответ — НОД всех предков текущей вершины ( можно просто передавать как параметр в дфсе)

    Ответ для вершины — максимум из 2ух случаев

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо за решение. Можете подсказать, почему не работает следующая динамика:

      dp[v][0/1][0/1] -- ответ в вершине v, при условии что мы меняем/не меняем данную вершину и нам можно/нельзя менять предков (dp[v][1][1] не используем)

      dp[v][0][0] = gcd(a[v], dp[par[v]][0][0])

      dp[v][1][0] = dp[par[v]][0][0]

      dp[v][0][1] = max(gcd(a[v], dp[par[v]][1][0]), gcd(a[v], dp[par[v]][0][1])

      У меня чувство, что дело в максимуме, но я не могу придумать тест, на котором это ломается.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Why can't we see the testcases?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the rating be updated?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Помогите, пожалуйста!

Подскажите, что я делаю не так в задаче A? Вот моя программа: http://mirror.codeforces.com/contest/842/submission/29897053. Подскажите, пожалуйста, тест 8.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Help me, please!

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 8   Проголосовать: нравится +81 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/contest/842/submission/29874288

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

nice contest with fast testing and rating update, thank you

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why can't we see the test cases?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кажется, здесь необходимо в сотый раз напомнить, что не стоит использовать питон для тяжелых операций :)

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Can anyone write shorter solution to A than this?

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

when is the editorial going to release.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Разбор будет? Все ждут его...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

is there no editorial??

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Where is the editorial?

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When will the editorial be added?

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When do you have any clothes?

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Разбор будет?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Will there be editorial for this round?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be an editorial?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    trie

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        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