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

Автор Livace, 10 дней назад, перевод, По-русски,

Привет, Codeforces!

Codeforces Round #483 пройдёт во 15.05.2018 17:45 (Московское время). Раунд будет рейтинговым для обоих дивизионов.

Задачи подготовили neckbosov, KAN и я.

Большое спасибо тестерам qoo2p5, manoprenko, AlexFetisov, winger, cyand1317 и ashmelev.

Отдельная благорность MikeMirzayanov за Codeforces и Polygon и ifsmirnov за jngen.

И несколько слов от MikeMirzayanov:

Спасибо фонду Botan Investments и лично Виктору Шабурову за поддержку и поздравления c 8-летием! Горжусь нашим знакомством и возможностью помочь фонду запускать интересные программы! Напомню, что Botan Investments ведет регулярную работу по поддержку спортивного программирования в РФ: грантовая программа для преподавателей и 50000 рублей гроссмейстерам из регионов РФ работают уже несколько лет. Здесь вы можете ознакомиться с отчётами фонда и найти ссылки на интересные посты MikhailRubinchik.ru (и в ВК-группе https://vk.com/botaninvestments).

Upd. Разбалловка 500-1000-1500-2000-2500 для div2 и 500-1000-1500- 2250 -2500 для div1

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

div1:

  1. fateice
  2. skuecrk
  3. Egor
  4. dotorya
  5. LHiC

div2:

  1. wevetriedly
  2. mraron
  3. adeliaut
  4. fengsuiyan
  5. K.F.Cat

Разбор

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

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

how many problems ?

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

Judging from the name, it seems like a round in honor of people who donated some satisfying amount. Why are such special rounds not held on weekends so that as many people as possible could participate? Also maybe include some more information about the sponsors in the announcements.

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

My rating is waving on the border of specialist and pupil these days.

And bless everybody and me to get more rating in this contest.

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

It is raining contests...!!!

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

It will be very helpful if you please provide the scoring distribution for each problem.

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

Don't worry that your division can change after ratings update after Codeforces Round #482 (Div. 2). I'll fix all the registrations to match your actual division.

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

Both divisions ? Now we have three in Codeforces ! Thanks Codeforces

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

I believe if it is a thanks round, then the blog post should include some information and thanking for the supporters in this round. Otherwise it'll be no different from a normal round.

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

Accidentally downvoted :(

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

Contests everyday, thank you

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

what does jngen mean???

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

Contest of Div1 and ((div2 — div3) union div3) ) :P

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

These guys will beat tourist :

  1. gautam1212
  2. __B
  3. sarthak0797
»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully, (Div. 2) Problems will be interesting like today's one.

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

Wow, there are real jngen users :) I haven't promoted it for several months, so I'm very happy to see that sort of self-promotion exists.

I would be glad if you could share the problems with me after the round. If I see how the community uses the library I can maybe improve the docs, give you some advice or see new development directions. My polygon login is the same as here.

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

Wow, nice short description. Hope the description of the problems will be as short as the blog. :)

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

My semester final exam start from today and I am waiting for Codeforces Round #483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!] :).

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

My rating is below 2100 but I cannot register at the home page.

Please fix the bug. MikeMirzayanov

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

    If there is a div1 round, you only can participate in it. You are still a div1 contestant.

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

    Candidate Masters are in Div 1 when both Div 1 and Div 2 round are scheduled at same time.

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

Hopefully.

Candidate master still participate in div 1 round.

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

She: "What would you do alone at home?"

Mobile chimes, " Codeforces Div ..."

He: "I am not alone, anymore."

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

"Гожусь нашим знакомством", "лично Виктор Шабурову"

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

you said the round rated for both divisions

is it rated for div3?

or div3 is n't a division

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

is it rated for DIV-3?

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

Q. Why did Scarlet witch fell in love with Vision?

A. He was Red. :P

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

Good luck & hack for Both divisions

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

Заиграет ли velheor в Na'Vi?

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

    Good question it could be if it was in english. Accroding to google translator velhore I guess will overplay in Natus Vincere. Good luck in contest! Do not lose as Na'Vi always do.

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

10 min delay. why?

»
9 дней назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
9 дней назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

Problems difficulty is Unbalanced at all A and B**** are extremely easy compared to C and D

  • »
    »
    9 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится
    Комментарий удален по причине нарушения правил Codeforces
    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      just searching the problem C and going to the top result leads to the answer

      why you copy the question from somewhere else and then remove the comments??

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

No Hacks !!

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

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
9 дней назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

I solved problem C without the condition of 4 guys in the elevator, and was thinking why I had got WA 4 during all contest.

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

What's the point in making such a tough TL in div1A? Nice problems btw.

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

    After finding g = gcd(q,b), If you divide q by g only once, it may reduces TL.(In TC 13)

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

      Furthermore, the next value of g will always be a divisor of the previous one. So you can initialise g = b and then do g = gcd(q, g).

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

Is Div1 E just finding greedily till lca from both nodes and summing it??

Also is Div1 B using SOS dp or something easy??

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

    I did simple interval dp with precalculating function on all intervals.

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

      Dint precalc use SOS dp. ??

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

        F[i][len] = F[i][len — 1] ^ F[i + 1][len — 1]

        dp[i][len] = max(f[i][len], dp[i][len — 1], dp[i + 1][len — 1])

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

          Thanks!! I dont know how to react to this to miss such a simple observation but find a very nice pattern...

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

    Easy.
    dp[l][r] = max(dp[l][r-1], dp1[l, r]) where
    dp1[l][r] = max(dp1[l+1][r], dp2[l, r]) where
    dp2[l, r] = (dp2[l][r-1] ^ dp2[l+1][r])
    calc dp2 for all [l, r], then dp1, then dp.

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

    Is Div1 E just finding greedily till lca from both nodes and summing it??

    Almost. The way I see it, you should go greedily (precomputing jumps by 2^k buses up) and stop before reaching lca, then check if the two vertices you stopped at can be connected by 1 bus. That check seems harder to me, I solved it using offline+sweepline+segtree in or , but I'm sure there's a simpler solution.

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

      That check is equal to query "Is there any number from interval [tinx, toutx] in the subtree of vertex y?" so it can be done with simple merging of sets.

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

        Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex?

        My solution represents each "do we need 1 bus?" query by a rectangle formed by the intervals corresponding to the subtrees of its end vertices and each bus by a 2d point formed by the coordinates of its end vertices (both sorted to avoid casework). I avoid using a 2d interval tree by sorting and sweeplining by one coordinate, using an interval tree with operations "add/remove labeled interval" and "check off all intervals containing some point". In the end, I made it have amortised complexity per query, it's just more work and a clever structure.

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

          Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex?

          Yes

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

    I think you need to know whether you can "save one bus" because the stops from both subtrees are connected by the same bus.

    Since I'm not too sure how to phrase that properly, maybe I'll just highlight the problem by asking a simpler problem: Given 2 nodes, how do you know if they are connected by a bus (i.e. answer = 1 for that query)?

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

How to solve C?

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

    is finite iff q contains only prime factors of b. So just divide q with the prime factors of b, and check if at the end whether q is 1 or not.

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

    A rational number p / q has finite decimal representation in a base b iff there exists a positive integer n such that q|bn. From this we conclude that the set of divisors of q must be a subset of the divisors of b. I tried implementing this idea in PyPy but got TLE on pretest 9 (though asymptotically it should pass, guess the constant factor for PyPy is too large or my implementation was bad. :( )

    Edit: Reading mraron's reply above, I think that my implementation was bad, kind of overkill.

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

Hack-Free contest !

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

why second pretest in B doesn't equal second example in task? wtf

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

I realized that the TITLE of the Problem Div2D,Div1B was such a huge hint, but it was too late. no time to debug.

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

Problem Div.2 C

What is the answer for :

1 1000000000000000000 999999999999999999 10

the calculator shows : 1000000000000000000/999999999999999999 = 1.000000000000000001 which is finite

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

Thanks Botan Investments for my decreased rating...

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

For div2d, I thought of some kinda O(N^N) preprocessing but I had no clue how to calculate f() efficiently.. What is the idea behind this problem ?

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

    Look at the title of that problem. There's a huge hint.

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

    If len = ar - al then
    f(al, ..., ar - 1) = f(al, ..., al + len - 2k - 1) xor f(ar, ..., ar + len - 2k - 1),
    where 2k is the maximum power of two that less than len

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

    First, Calculate the 2d dp:

    A[j][i+j] = A[j][i+j-1]^A[j+1][i+j]

    then calc max as:

    M[l][r] = max(A[l][r], max(M[j][i+j-1], M[j+1][i+j]))

    then the query will be O(1)

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

Может быть, авторы перестанут ставить ограничение по времени 1 секунду в задачах, где много ввода????

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

    Там они по какой-то странной и неадекватной причине решили отсечь .

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

      Хм, у меня возведение в 64ю степень с бинарным умножением зашло на претестах за 982 мс

      и упало

      а потом я поменял cout на printf и зашло

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

how can we solve problem D , i know we need to find max xor pair in given range , but how to optimise it from o(n^2) ?

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

To be honest, I must appreciate how setters choose cases for pretests in this one — really careful and cover nearly everything one can slip into. Cheers. ;)

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

too tight time limit on Div.2 C....

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

Anybody else wants to complain against time limit of div1 A?

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

    me, i even made a comment in russian

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

    It depends on what is an intended complexity. Firstly I did something like log times gcd per testcase (which is O(log^2)) and it turned out to exceed TL. Then I did some optimization which looks silly, but I think it may actually improve complexity and passed in TL/3. However this task is actually doable in O(log(log(b + q)) per testcase, because it suffices to check if q|b64 which can be done with 6 multiplications if we have big integers or __int128_t that Codeforces doesn't have (taking mod q after each step of course).

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

      I tried bigint solution with python, and got TLE..

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

      I have log times gcd and it got AC. On the other hand, the numbers I'm computing gcd from decrease very quickly — it's "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible".

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

        That's what I did in the end as well. I mean you and I both finally have "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", but in the beginning I had "while Q > 1 compute gcd(B, Q), divide Q by it" without "as many times as possible". I am not sure what is the worst case complexity of this solution, but after some thought I got an impression it is really useful and it is not as silly as it looks.

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

          For having "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", it may takes even longer time in worst case. An example is q = 260, b = 231 then gcd(q, b) = 231 but we can divide it only once. However to check whether dividing it one more time is possible, we have to compute a division to check its remainder. (That cause extra time)

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

            Yes, in some cases it may be worse but thats not a worst case. In your example in next iteration we will have gcd=2^29 and divide everything, so there is only 2 computations of gcd(which also has divisions btw). If you divide by gcd once you have up to 60 iterations of gcd (which gives per test comlexity. If you divide while you can, it's no more then sqrt(60) iterations of gcd, which gives you (and comment shows that complexity may be shown to be

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

        I'm pretty sure this is asymptotically faster. It's no more that O(sqrt(log()) iterations of gcd because you divide by numbers with different number of primes each time

        (and may be it's even faster)

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

        If you do that + making B = gcd(B, Q) after not being able to divide makes the complexity O(log) amortized. This works because for each 2 iterations of Euclid's algorithm, one number is at least half of before and you use that number for the next iterations so the maximum number of iterations is O(log). Other than that, the number will obviously be divided at most O(log) times. Did I miss something?

        Edit: also, for your optimization my friend's reasoning applies. There will be 1 prime that will get below the exponent of B in one while iteration and it will disappear in the next one. So you get rid of at least one prime for each 2 iterations.

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

      Thanks AlexDmitriev for this comment, he is right, this solution works O(nlog1.5M). Optimization is same as "divide as we can", but works faster because numbers are smaller. But I think that it doesn't make less complexity. Editoral will be updated.

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

        It actually does make the complexity O(logM) per case. Maybe I wasn't clear on the comment above. If you call gcd(q, b) for each 2 iterations b will be at least half so the sum of iterations until b is 1 is O(logb) (amortized).

        By iteration I mean iterations inside gcd

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

          Sorry, it's not clear to me why the complexity is O(log M) per case.

          If you have log(N) + log(N/2) + log(N/4) + log(N/8)..., that's still log(N)^2 time, no? Since it's log(N) + (log(N)-1) + (log(N)-2)... complexity.

          Seems to me like the real complexity is still . Since the worst case involves all the primes having different exponents, we can divide by more than half each time, we can divide by 2i for each iteration. So, our computation is log(N) + log(N/2) + log(N/2^3) + log(N/2^7)..., or log(N) + (log(N) -1) + (log(N) - 3) + (log(N) - 6) ....

          So, the number of log(N) operations we have to do is based off of how fast 1,3,6... reaches log(N). As that's just simply the triangle numbers, there's terms.

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

            If you had one gcd take x iterations then B will be <= B / 2^(x/2). So the complexity isn't log(N) + log(N/2) + log(N/4) + log(N/8)... and the sum of steps will be <= 2 * log(B).

            So if a gcd computation takes indeed log(B) or a big number of steps, the number will be much lower than B and the maximum number of iterations for the rest will be lowered. This is amortized analysis, not every gcd will be worst case. Also as you get closer to worst case for gcd, worst case implies that gcd is 1 and you don't need to continue so more iterations == B is much lower.

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

          If I'm not mistaken the following simpler code works in :

          b = gcd(q, b);
          while (b > 1) {
            q /= b;
            b = gcd(q, b);
          }
          return q;
          

          Suppose that the loop has several iterations, and the value of variable b in the i-th iteration is bi. Time complexity of the i-th invocation of Euclid's algorithm is . So the total complexity of the loop is , since for some Q.

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

solution for Div2. C (Div1. A):

https://math.stackexchange.com/questions/310402/proving-finite-vs-infinite-representation-of-p-q-in-base-b

(i think now there is no violation with codeforces stupid rules)

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

    they didnt even change the p,q,b!!!

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

      well if you know the solution. why you couldn't get accepted verdict? they have tighten the time limit so you must try different approach.

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

        i tried 19 different approaches!

        and now when i see others approaches some of them are same whit me and the only difference is that they print the answers immediately but i print all answers after calculating all of them

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

      A very high chance that it's just a coincedence. Integer fraction is very often (almost always) presents as p/q and base is ussualy presents as 'b'.

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

An interesting game

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

problem C looks trivial. Does this dp works? dp[i][pos][x1][x2][x3][x4]=minimum cost if the first i people already entered in the elevator, currently we are at floor pos, and the elevator contains people that wants to go to floors x1,x2,x3,x4.

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

    Yes, i think. but you should consider memory limit in that problem.

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

    You can reduce the complexity and memory space only considering the ordered multisets of (x1, x2, x3, x4). There is only 715 such multisets. Also looked trivial for me, just a careful implementation was needed.

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

This is the first round when I solved div1 E. I solved div2 E for the first time when Livace was the problem setter too (Codeforces Round #442).

Link: http://codeforces.com/contest/877/standings

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

    Perhaps you should plan to meet him in person?

    I don't think it's just notorious coincidence ;)

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

in problem (B. Minesweeper) 1 1 * how test like this can be valid ????

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

    It satisfied all constraints.

    There is only one cell with a mine. No cells left un-mined, so no numbers could be found.

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

    The one cell satisfies both criteria given in the problem statement:

    • there is not a digit in the cell, so you don't check for the count of bombs in neighboring cells;
    • the cell is not empty, so you don't check for neighboring cells having bombs.

    :)

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

      there is a bomb with no number point to it !! this is a violation for the game rule ??

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

        Indeed, in the real game it would not make much sense. But if you just abide by the problem statement it does. In my case, I didn't think about this apparent inconsistency because I never played that game :)

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

During the contest I wanted to hack leon_ldy's solution(38273146).I had 2 unsuccessful submissions in this problem and after my second submission I noticed in pretests 8 , n=1.but why his submission passed pretest? this is his code:

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int a[MAXN];

int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	int j = n - 1, k = 0;
	while (true)
	{
		j--;
		if (j == k)
			break;
		k++;
		if (j == k)
			break;
	}
	cout << a[j] << endl;

	return 0;
}

but when n=1 so j=0. and in the "while (true)" we had TLE. because at first "j--" and after that j=-1. so always j!=k.

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

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

C+E = (Code*Code*Code+Code^2)^Code

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

    What's wrong with C? Seems fine to me.

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

      That it is obvious to come up with a solution and nontrivial how to properly code it. It is a programming task, not an algorithmic one. Some people would say that it is ok, but I think that it is also ok to say it is not an interesting problem.

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

        OK, I see what you mean (but I still think that it's pretty easy to code)

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

          It seems that whenever contest goes well for me I think tasks were fine and when it doesn't I always declare tasks as programming and noninteresting ones :P.

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

For C I check whether the divisors of q are a subset of the divisors of b with gcd but still get TLE on 13.

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

Any ideas for D?

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

    Probably, it's wrong

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

      Do you know any good tutorials for kd-tree?

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

        Unfortunately, I haven't seen.

        For D I followed this easy-to-implement solution(actually, it's not classical KD-tree, it's more likely as joined KD-tree and Segment tree, just intersecting rectangles instead of segments) Probably, the author forgot about inclusion/exclusion case with boundary points in some quadrant.

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

    Author's solution is scanline + segment tree with sets in vertices.

»
9 дней назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
a=input()
while(a>0):
    a-=1
    p,q,b=map(int,raw_input().split())
    r=gcd(p,q)
    q=q/r
    r=gcd(q,b)
    while(q!=1 and r!=1):
        while(q%r==0):
            q=q/r
        r=gcd(q,b)
    if(q==1):
        print"Finite"
    else:
        print"Infinite"

even after writing exactly the same code as it is being discussed in the comment section, my solution failed. Time limit for python is too strict. i got tle in 11. Please verify if there is a mistake on my side or this happened because of the language selected. Thanks :)

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

    my English is poor,emmmm,

    while(q!=1 and r!=1):
            q=q/r
            while(q%r==0):
                q=q/r
            r=gcd(q,b)
    

    ~~~~~ while(q!=1 and r!=1): q=q/r while(q%r==0): q=q/r r=gcd(q,r)

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

      it means while q not equal to 1 || r not equal to 1

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

        i know , it is the first time for me to reply you can look the code i changed.

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

          I even tried this in my submission but even that failed pretest 11

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

            oh i know ,and you should know if p == 0 output Finite change like that ~~~~~ while(q!=1 and r!=1): q=q/r r=gcd(q,r) ~~~~~

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

              ohh shoot I think I got my mistake i thought all were having constraints >=1 Thanks a lot mate

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

                it dosent matter whether p==0 or not as when p==0 gcd(p,q)=q and q/q=1 and so ans would be finite it is definitely fault of strict time limit

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

    The language selected is the mistake on your side.

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

Is the time limit for python and c++ same every time for every question???

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

    Pretty sure it is. Python needs more love!

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

    no I guess its 5x for python but at times even that is slow it makes the competition more fair if the setter/tester try it in python as even python is being used a lot as compared to c++ and java

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

      no I guess its 5x for python

      Where did you hear of this? All I see is there is only a single time limit for each problem, e.g. it's 1 sec for Div2 C

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

        python has a time of 5x likewise java has 2x. this time is allocated according to the processing time of the language. as python is a slower language than c++ it gets 5x time. But this dosent mean python has more advantage.

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

          You aren't answering my question though, are you sure you are not just making this up?

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

            no I am sure as on various platforms like codechef and hackerearth this rule follows

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

For Div2D , if (r-l+1) is power of 2 then we can take all elements from l to r.

If I am right then please someone say the answer of this input and how ?

24

1 2 128 256 512 1024 2048 4 8 16 32 64 1 2 128 256 512 1024 2048 4 8 16 32 64

1

5 20

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

During the contest I had the following problem. In my template I have a few pragmas that should optimize operations and make Codeforces submissions faster (they’re pretty common to include nowadays).

However, for today’s problem E, something weird happened. The solution with these pragmas got RE verdict on pretest 1, while the solution without them got accepted.

http://codeforces.com/contest/983/submission/38296856 http://codeforces.com/contest/983/submission/38297301

I assure you the only difference between the two sources is in the pragma macros.

Have you ever experienced something like this? What pragma do you think is broken, in this sense?

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

    Leaving my comment, cuz I am curious as well and I wanna be notified :D

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

    I tested on custom invocation and put the bits/stdc++ line before the pragmas and oddly it worked. I have no idea why

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

    Third pragma. The problem may appear in situation, when CF uses different machines with a different architecture to compile and run code. It's common problem on Yandex Contest system. I use following pragma for it:

    #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
    
    • »
      »
      »
      9 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      So, is it only the tune=native setting I shpuld remove or all the rest of them?

      Also, I can’t test myself right now, have you tried running it without tune=native and seen it work?

      Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.

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

        Ok, I tested. In your case it's "abm" setting.

        Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.

        Actually, It depends not on platform, but on problem and on your code. That is, if the bottleneck of your solution can be vectorized, then the pragma will help. Otherwise, the optimizer can apply vectorization where it is not needed, and your solution will slow down.

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

          I agree with that. However, I’ve seen consistently better results overall on Codeforces, while I’ve never seen improvements on Yandex (Opencup for example). I think it depends on the architecture and the compiler as well. I’m not pretending to know anything here, but my guess is that the running on Windows the pragmas will have a bigger positive impact than on Linux.

          Have you ever had noticeable changes using these pragmas on Yandex? (compared to not using them, obviously)

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

            There were some problems from SNWS contests, PTZ and MIPT camps, that I solved with not optimal complexity, and I'm pretty sure that pragmas helped in that solutions.

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

        abm changed the implementation of std::__lg, which is later called by std::sort. Here's a simple example of it being unstable, even on other platforms:

        #pragma GCC optimize("Ofast")
        #pragma GCC target("abm")
        #include <bits/stdc++.h>
             
        using namespace std;
             
        int main() {
            cout << __lg(1) << endl;
            volatile int i = 1;
            do {
                cout << __lg(i) << endl;
                ++i;
            } while (i <= 1);
        }
        

        Output:

        0
        31
        

        with abm

        without abm

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

        Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.

        Lol, I added the Ofast pragma to my code for E and it slowed down by ~50%.

        On the other hand, one secondary school student in our IOI selection used

        # pragma GCC optimize ("O3")
        # pragma GCC optimize ("Ofast")
        # pragma GCC optimize ("unroll-loops")
        

        to almost solve a problem with bruteforce.

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

The time limitation on Div2C is too tight.... just reassigning gcd value made it passed.. -_-

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

Systests for div1B are weak, i see some O(q*n) solutions accepted

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

Can anyone explain why first gives TLE and the other one AC 38300452 and 38300601

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

When are we going to get the tutorial?

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

So, did noone notice this: 1 2?

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

can someone explain why the first query of the second test case of Div.2-D is 60 instead of 63? shouldn't it be 1 ^ 2 ^ 4 ^ 8 ^ 16 ^ 32?

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

Pretests for B were pretty weak. In my solution I put a "n" instead of "m" in the second loop when I wanted to traverse my matrix. Apparently that was enough to pass the pretests. I noticed that error only after the system tests.

Then I changed "n" for "m" and got AC. Sad day for me :( .

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

Q. When does one grow up? A. When one reads more comments on CF than FB.

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

In div2 problem C For values of p,q,b=(10,5,3) in TC#3 how the answer is finite

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

    10 / 5 = 2 in base 10 which is 2 in base 3. This does not have a non terminating decimal part(rather does not have any digit after decimal point)

    I guess you are confusing with the case (p,q,b) = (5, 10, 3). In which case it would be non terminating and hence infinite in problem's context.

    So you only need to take into consideration the prime factors of denominator and base since for improper fraction a/b you can always write it as [a/b] (greatest integer function) + {a / b} (fractional part) where the former will always be translatable to different bases without recurring decimals . Refer editorial for more insights.

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

      Well if we convert both numerator and denominator firsthand to base 3 i.e. 10 in base 3 would be 101 and 5 in base 3 would be 12, so 101/12 will be infinite. I am confused here.

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

        Yes it is correct to say that but notice that since you convert numbers to base 3, conventional division(in base 10) does not work.

        You can still observe that base3(12) * base3(2) = base3(101). Hence we don't have a recurring decimal. An easier way to do the this is the same as mentioned in samples in the question .

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

          I got it. I misunderstood the notes of the problem given in the contest. Thanks alot. :D

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

I was trying to solve Div1E with O(n * sqrt(n)) complexity, sqrt(n) jumps instead of binary lifting. When I debugging I changed my sqrt variable to 1. And it got accepted.

38320734

It simply tries to jump lca and stop when there's a route from this node to lca. And same thing for second node, also check for ans - 1, no different solution.

You can check my code and see that for every query I'm calculating the answer with increasing res one by one.

while(!inside(c, go[x])) {
	if(go[x] == x) {
		res = -1;
		break;
	}
	res++;
	x = go[x];
}

And sad part is I have no clue how good my O(n * sqrt(n)) solution is. It actually got slower time :(

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

My solution was missjudged in contest. Please kindly look into it.

Detailed post: http://codeforces.com/blog/entry/59503

Submission on contest: 38291441

Same solution accepted: 38328663

Thank you.