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

Автор KAN, 4 года назад, По-русски

Всем привет!

В это воскресенье, 21-го марта 2021 года в 13:00 по московскому времени начнется Финал Технокубка 2021!

Для тех, кто хочет посоревноваться на тех же задачах, будет проведено два обычных раунда Codeforces: один для первого, другой для второго дивизиона. Раунды начнутся 21.03.2021 16:20 (Московское время), не пропустите!

Конечно, если вы участвуете в финальном раунде Технокубка, то вы не можете участвовать в раунде вечером. Мы просим участников официального финала воздержаться от обсуждения задач в открытых сообществах до конца раунда вечером.

Задачи для вас готовили: Александр Golovanov399 Голованов, Евгений amethyst0 Белых, Андрей AndreySergunin Сергунин, Алексей Aleks5d Упирвицкий, Diego Diegogrc Garcia и я.

Также спасибо Bench0310, kokokostya, Um_nik, dorijanlendvaj, brunomont, Stepavly, antontrygubO_o, JinhaiChen, budalnik, wucstdio, golikovnik, kuviman, dantrag, BledDest, Supermagzzz, JettyOller, geranazavr555, divanik, psevdoinsaf, Roms за тестирование задач и ценные замечания, а также antontrygubO_o за помощь в проведении зеркальных раундов.

Удачи!

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

Div. 1:

  1. ecnerwala
  2. Radewoosh
  3. Benq
  4. mango_lassi
  5. AliShahali1382

Div. 2:

  1. qwqc
  2. gezlik
  3. yanyutao
  4. fengqiyuka
  5. ykl

Всем спасибо за участие! Разбор в обычном формате, презентация с разбором.

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

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

You missed " Notice the unusual timing "

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

Друзья, а что такое "технокубок"? Как я понимаю, это олимпиада. Ещё есть возможность регистрации?

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

    Нет, финальному раунду предшествовали отборочные. Подробнее тут.

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

Hoping for strong sample tests this time ;)

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

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

    dude ur timeline is chaotic , can u tell desired rank to get to 1400+

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

      1400

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

      Depends on how many participants participating in the round generally you need to be in the top 20% maybe and it differs when it's div 1+2 just being in top 30% would get you to specialist easily

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

Is the official Technocup round (not the Div 1/2) rated? (not a bait question, genuinely curious)

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

3 contests a day. Gonna be rough. - Kickstart - CF - Cookff

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

AtCoder Regular Contest 115 — 5 PM (UTC + 6)
CF DIV 1/2 — 7.10 PM (UTC + 6)
MARCH COOK-OFF 2021 — 10 PM(UTC + 6)

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

Last year, the contest was ethical and beautiful. Hope it will be the same this year!

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

Today full of contests will coming...

JOISC 2021 Day2 1p.m. — 6p.m.
AtCoder Regular Contest 115 7.p.m. — 9p.m.
CF Round #709 Div. 2 9.10p.m. — 11.10p.m. (Isn't it used to be 9.05 p.m.? Wondering for it)

I've never participated in so many rounds in one day. It's busy without doubt, and I hope it'll also be a fulfilling and unforgettable day for me...

P.S. UTC+8

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

This round is rated or not...as it's not mentioned anywhere in the announcement ??

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

The Final Round of Technocup 2019 starts this Sunday, on the March 21, 2021 at 13:00 MSK (10:00 UTC)!

Shouldn't it be Technocup 2021?

P.S. If I misunderstand this, can someone please explain it to me?

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

Узнают ли финалисты разбалловку до начала раунда?

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

жаль что некоторые финалисты будут сдавать с фейков:(

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

Atcder round will end exactly 10 minutes before the start of this round. Such a productive day

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

Why unusual time though, so as to host it with the actual finals?

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

What is the score distribution for the tasks?

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

How many problems will there be?

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

How Many Problems will be there and problem ratings ???

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

delayed 10 minutes

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

Delayed by 10 minutes

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

Forget to release score distribution and make a 10 mins delay?

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

Come on everyone and good luck!
It's my first time to have a contest!

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

there is a delay!

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

SO now what should i do for next 10 mins of my life?

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

Delay it some more times and the unusual timing will become usual again.

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

what's the scoring distribution of the problems?

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

I guess score distribution is left for surprise.

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

So, the revealing of score distribution is gonna be the latest in codeforces history, lol!!

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

Please don't delay this round more than this, we have to give cc march cookoff as well :( T_T

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

    You know they don't delay it for fun, right?

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

      Yeah mate, I know . My apology for being a bit rude :(

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

        by mistake i locked my wrong solution instead of write due to technical glitch during start of contest will i get points of problem A as there is correct one but locked one is wrong please respond whosoever knows????

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

          Once you locked your solution for A , the next solution of A will not be judged by the judge for competition,instead the judge will just take the response which u submitted just before locking. :-|

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

Why score distribution for this round is not given

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

Literally guys , again 10 minutes what to do for 10 minutes i controlled washroom for the contest Now fucked up !!

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

Every minute seems like an hour now :)

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

Score distribution?

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

no notice for unusual timing no score distribution whats going on?

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

iS iT rAtEd?

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

How can someone solve A,B,C within 2 minutes unless they know the problems and the solutions beforehand! Ridiculous!!!

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

wtf?  In two minutes this guy read 3 problems as well as solved them and then coded them.

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

Total solve for each problem not visible on the dashboard(Div2)

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

504 Gateway Time-out

Unrated again?

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

    Now I face the problem The statement is not available now...

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

    Down only at the beginning. Later it was fine until the end of contest (at least for me).

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

    No, m1/m2/m3 were working fine for the whole round.

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

      But it lacks some useful functionality. E.g. statistics of solved tasks (one can determine which task better to solve next) and hacking (but it was too rare in this round).

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

      Idea to make m[X] for all users mandatory during the beginning of the round, e.g. first 30 minutes or so, when most participants upload their A and platform overloads.

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

I am submitting using m3 and not able to see if my solution is submitted or not.

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

It is being unethical and ugly. Again.

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

Hey guys I can't see the statements of the problems now. What's wrong?

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

Toughest Prob B ever!!

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

    B was pretty hard if not familiar with modular arithmetic. C was easier than B for me.

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

MikeMirzayanov There were a few people who read , coded and submitted about 2-3 problmes within a first few minuites, I feel thy already knew the problems. Please do us a favour and disqualify them.

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

    They have been removed.

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

      I submitted A within 7-8 min but the page wasn't loading so I resubmitted it on m1.codeforces. The same code without any change was submitted. Both the submissions passed but the later solution timing was considered and I was given some penalty for two submissions with exact same code. Check it and if possible resolve the rating changes.

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

Pathetic Contest for me IMO.. No offense to anyone

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

This is the actual power of your speed
Rank 1591 with A solved

Also Rank 9160 with A solved
:D

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

in problem b when i 1st time submited it gives me RE..i tried to find error but couldnt find it..so i tried to submit the same code added some comment line(because you cant submit same code)..and i got WA for same code..What happening :")?

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

by mistake i locked my wrong solution instead of write due to technical glitch during start of contest will i get points of problem A as there is correct one but locked one is wrong please respond whosoever knows????

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

hardforces!! ( atleast for me don't know about others )

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

Really interesting problems, have no idea how to solve them though lol

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

Really nice problems, no idea how to solve them though lol

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

I want to clarify 1 one thing,i made submission of problem A at 7 min from m1.codeforces ,and after submitting B from codeforces.com,i saw A has not been marked green ,while its pretests are passed,again i submitted from codeforces.com,then WTF,my score was reduced from 486 to 218,seriously dude,is this fair??

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

    And there is one more strange thing-

    I submitted A and B both in m1.codeforces.com and I found that A didn't mark green(Passed pretests) but B did. Now I'm worried that if I won't get any scores in A :(

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

    Mine is also not marked green. It must be a technical glitch, but you should not submit it again. This problem may be happening with many others.

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

      So you can't resubmit it during the game, right?

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

        You can submit as many times as you want. But you should not, as it leads to increased penalty also.

        And ya, the same code can not be submitted multiple times.

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

    Most recent submission time is taken into account.If pretests are passed and you submitted again then it counts as "Some edge cases striked you ,which now u think your submitted code wouldnt pass system test and thats why u resubmitted" and thats why most recent time is taken into account,it seems.

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

    same :(

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

    Due to technical difficulties, some problems may be shown as unsolved. However, on the tab "My submissions" you still was able to see your submissions.

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

I submitted A at 14 minutes 50 second and italso passed pretests, but it doesn't show green colour and option to lock in Dashboard. Though, it is there for other 3 problems.

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

Problem D: fix a source vertex $$$u$$$ and let $$$M = \max_v l$$$ over all triples $$$(u, v, l)$$$. Add an $$$(n+1)$$$-th dummy vertex to the graph, and for each triple $$$(u, v, l)$$$ add an edge from $$$v$$$ to the dummy vertex with weight $$$M - l$$$. Now an edge is useful if it is in a path of length at most $$$M$$$ from $$$u$$$ to the dummy vertex. Now the problem reduces to doing two Dijkstra's (one from $$$u$$$, one from the dummy vertex) and checking each edge. Since the graph is complete in the worst case, it was best to implement the $$$O(n^2)$$$ version of Dijkstra (heap-based version gave TLE for me). Final runtime $$$O(n^3)$$$.

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

KAN What the hell is pretest 16 in D?

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

How to do div2D?

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

    can you explain div2 B,C?

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

    Each elements is only removed at most once. Therefore, we keep two std::sets, one to keep track of the remaining elements, and one that keeps candidates for deletion. When deleting a vertex, we can do so by an upper_bound operation on the second set, update the next vertex that is not deleted.

    Complexity: $$$O(n \log n + n \log max(a))$$$.

    Code: 110638935

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

Is it rated ?

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

I literally wrote some random shit in C and it passed pretests. Waiting for fst :(

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

How to solve div2 B and C?

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

    Problem B

    If there is a solution, then, for all i > 1:

    If ai-1 <= ai then ai - ai - 1 = c

    If ai-1 > ai then ai - ai - 1 = c - m.

    Let c1 = ai - ai - 1

    If the values of c or c1 are inconsistent for different values of i then there is no solution.

    If either is unknown (i.e. the array is monotonically increasing or decreasing) then any value of m works.

    Otherwise the only possible value of m is c - c1. If this is greater than the biggest value in the array it is the solution; if it isn't then there is no solution.

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

      How did you arrive at : If $$$a_{i-1}$$$ $$$>$$$ $$$a_i$$$ then $$$a_i - a_{i-1}$$$ = $$$c - m$$$ $$$?$$$

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

        ai = (ai-1 + c) mod m

        ai = ai-1 + c - k*m for some integer k >= 0, by definition of mod

        Also 0 <= ai < m

        We know 0 <= ai-1 < m and 0 <= c < m, so

        0 <= ai-1 + c < 2*m

        So 0 <= k*m < 2*m

        So k = 0 or k = 1

        If k = 0 then ai = ai-1 + c

        If k = 1 then ai = ai-1 + c - m

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

          Thanks, I was writing $$$a_i = k*m + a_{i-1} + c$$$.

          Takeaway: $$$ a_i = (a_{i-1} + c)$$$ $$$mod$$$ $$$m$$$ is not the same as $$$a_i \equiv (a_{i-1} + c)$$$ $$$mod$$$ $$$m$$$

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

Any hints for Div2 D ?

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

Duh, I got down to 107 queries in E >_> (worst result after simulating tens of thousands of random tests locally). Is 105 provably optimal (in which case I will admit I was not close) or did I lacked just a few small tweaks :|?

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

    I sincerely hope it wasn't, because otherwise I spent 1.5 hours for nothing :(((((( My approach was to find largest $$$t$$$ s.t. worst case asking $$$(l+r) \cdot t$$$ and always getting lower answer fits in current number of remaining questions. What was yours?

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

      That's what I did as well. I passed pretests (who knows about systests...) by using this approach, running it on an interactor I wrote, and tweaking it in order to maximize the minimum number of queries left on $$$2^{46} - 1$$$, $$$2^{45},$$$ or $$$2^{46}.$$$

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

      On the beginning I tried doubling my budget till I hit first bust ("Fraudster" response). At that point my search space is of form $$$[L, R]$$$, where $$$2L \ge R$$$ (which means that after failed query I can regain a big part of my budget by asking L). Then I try to do skewed binary search. If I ask about midpoint of my interval then no matter what the answer is, I am left with interval of the same length, however in one of these cases I lost a lot of money, so this is probably not the optimal dividing point. I ask about $$$\frac{L \cdot \phi + R}{1 + \phi}$$$ (where $$$\phi = 1.618...$$$). I either end up with a longer interval after gaining money or shorter interval after losing money. Don't ask me why $$$\phi$$$, I just somehow felt it would be good and my experiments confirmed it was a sensible choice.

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

        I was thinking that something like that might pass, but I was assuming that my apporach is a generalization of your's, therefore I would just write mine. I guess it turns out that my approach suffers greatly because of precision, therefore it didn't work

        upd: turns out $$$(l+r) \cdot t$$$ isn't equivalent to $$$\frac{(l \cdot t + r)}{1 + t}$$$.................

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

        It seems that after raising number of testcases to a few millions my code got up to even 110 queries. However I added an opt suggested to me by kabuszki that if I have a lot of money I can ask closer to half, if I have not a lot, I ask closer to L (I threw in some random constants to quantify this) and after that it doesn't exceed 104 queries on a few millions of cases.

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

How to solve Div 2 E?

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

    We can do this with DP. Let $$$dp_i$$$ denote the maximum beauty you can get by taking photos of only the first $$$i$$$ buildings and $$$bef_i$$$ indicate the greatest index $$$j < i$$$ such that $$$h_j$$$ < $$$h_i$$$ or $$$-1$$$ if no such $$$j$$$ exists. Now the transitions are quite simple.

    $$$dp_i$$$ = $$$max(\displaystyle\max_{bef_i \leq j < i}dp_j + b_i, dp_{bef_i})$$$

    The first part is when building $$$i$$$ is in a different photo than building $$${bef_i}$$$, and since all buildings in the photo which the building $$$i$$$ is present are taller than it, we will only consider the beauty of this building. The second part corresponds to the case when building $$$i$$$ is in the same photo as $$$bef_i$$$. In this scenario, as all the building after $$$bef_i$$$ are taller than it, none of the buildings there will contribute to the beauty of the photo. You can implement this using segment tree. Also, make sure to handle the case where $$$bef_i = -1$$$

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

      Can you explain what you will be using the segment tree for here?

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

        For the range max queries in the first part of the $$$dp_i$$$. If implemented naively it might end up with a $$$O(n^2)$$$ complexity. You can use a segment tree or you can use a stack as mentioned in the below comment.

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

      I think it should be max( max ... )

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

      Thanks for your solution.

      I implemented it without segment tree: maintain a monotonic stack. After each operation, the last item in stack stores $$$(i, \displaystyle\max_{bef[i] \leq j < i}dp_j)$$$, the second to last item stores $$$(bef[i], \displaystyle\max_{bef[bef[i]] \leq j < bef[i]}dp_j )$$$, and so on. It can reduce complexity to $$$O(n)$$$.

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

Today at starting site was again too slow and when i submitted A it does't reflect in submission so I opened lightweight version of CF and submitted there but later i came to know previous was also submitted ans 50 points got reducted for resubmission :/

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

Can anybody give me some hints for B.

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

    This one passed pretests. Nothing much to explain.

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

    Hint: If an array is valid, then every subsequent difference d=a[i]-a[i-1] will be c if d is positive, and m-c if d is negative.

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

      What about if the array has only negative delta, ie all steps are decreasing?

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

        then m can be largest possible

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

          Example, a[]={ 5, 4, 2 }

          Which c, m would make this work?

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

            won't work. 4 — 5 != 2 — 4

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

            Suppose array is decreasing, then a[i — 1] — a[i] = di. And di is same for is i(otherwise answer will be -1), di > 0. Now d = di(any). also, d = m — c. Here m can be any value, c can have any value because d > 0. (so c can have value of [0, m — 1]). So we can any pair of m, c. So finally answer will be 0.

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

        It's still true. The next observation is that if either all are negative, all are positive, or all are 0, then there are no restrictions on m.

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

          I couldn't solve the problem when array has only negative delta For example if the array is 10,8,6,2 like this.

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

            In that case, if adjacent differences are equal the answer is 0, otherwise -1.

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

      if d is negative, then why can't 2m-c, 3m-c or in general, Zm-c also one of the possibilities?

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

        In our case, the difference between every consecutive number will have magnitude at most m (since each number is between 0 and m-1). c<m so every possibility you listed has magnitude more than m.

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

The lightweight websites m1, m2, m3 were a bit too lightweight this time...

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

Such hard problems.

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

This contest was brutal(Donno about others but for me it was).. T_T :(

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

    I always like these type of contests which is based on some contests. They usually contain nice problems.

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

      Obviously problems were nice, but this type of nice problemset is inversely proportional to +delta. (atleast for me) T_T.

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

in div 2 e :

for 4th sample why answer is 96?

if we make photo in this way:

1)1,2,3,4,5

2)6

3)7

4)8,9

5)10

beauty is 100

am i wrong?

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

Why Div. 2 A was so easy?

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

Does submitting two solutions incur a penalty? I don't know how maybe due to server issues my solution got submitted twice to problem A within 9 seconds and got a 50 point penalty. Any idea why?

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

    Yes there is a penalty of 50 points for resubmission. You can message the contest setter telling him/her that it was by mistake you submitted the same code. He/She can help you.

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

    Same thing happened with me

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

My solution for D:

Let $$$w_{uv}$$$ be the weight of the edge between vertex $$$u$$$ and $$$v$$$ (or $$$\infty$$$ if it does not exist), $$$d_{uv}$$$ be the shortest distance of $$$u$$$ and $$$v$$$ (or $$$\infty$$$ similarly), and $$$l_{uv}$$$ be the third element of one of given triplets that forms $$$(u, v, *)$$$ or $$$(v, u, *)$$$ (or $$$0$$$ if such triple does not exist).

For each $$$(u, v)$$$ such that $$$u < v$$$ and $$$w_{uv} < \infty$$$, we want to check if there exists a pair of vertices $$$(a, b)$$$ such that $$$d_{au} + w_{uv} + d_{vb} \leq l_{ab}$$$. This is equivalent to $$${}^\exists a,\; d_{au} + w_{uv} \leq \max_b ( l_{ab} - d_{vb} )$$$. We can precalculate $$$f_{av} := \displaystyle \max_b ( l_{ab} - d_{vb} )$$$ in $$$O(n^3)$$$ time, then check $$${}^\exists a,\; d_{au} + w_{uv} \leq f_{av}$$$ in $$$O(n)$$$ time for each $$$(u, v)$$$. Therefore the problem has been solved in a total of $$$O(n^3)$$$ time.

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

how sad it is when codeforces does not work:(

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

Rounds for children are so bizarre, each time I participate in them it's such a disaster.

The mice cried, pricked, but continued gnawing the cactus...

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

    From Russian saying.

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

      Yes, it's from the anecdote where the mice wanted to become hedgehogs, or alternatively from the story in which a real cactus was hurt by hungry mice which weren't able to find some less painful comestibles.

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

Is this round rated?

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

The problem E is a very great problem, especially limited the number of inquiries <= 10^{14} and let my multiplication get TLE(because of invalid queries) Thank you very much!

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

B > C. Just another day at CF.

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

Can't wait for editorial to see the intended solution for Div2 D. I couldn't do it in less than O(n^2)

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

    I have ~ O(n) solution using vector of deques

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

      would you mind sharing the idea behind it?

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

        Let's consider sequence p[1], p[2], ..., p[k], where GCD(p[i — 1], p[i]) != 1 for each neighbor pairs. We can store this sequence as a deque. Let's simulate the process and parse the given array into these deques.

        Then we have obvious property: if you delete p[1], you start from p[2] and go until p[k], and for each neighbor pairs GCD is also > 1. We don't need to check it twice, let's just remove the first element from the deque.

        After that let's consider two neighbor deques q and p. If GCD(q.back(), p.front()) != 1, we can merge them(you can use small-to-large to do it more efficiently).

        You can do it while it is possible to remove at least one element. After few operations we'll get one deque, let's consider it as given array and do the same.

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

geranazavr555 when will codeforces be fully open ?

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

Why is viewing user profiles blocked?

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

Can anyone give any hints for Div2 C?

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

In Div2 C why it was not given that "nobody is chosen strictly more than " Ceil of m/2...I got wrong thrice on it due to assuming it to be rounded down :(

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

My soln of D -
Let d[u][v] be the shortest distance between u and v.

O(n^4) soln - Let x,y,w be an edge. u,v,l is a triplet.
x,y is good if d[x][u]+w+d[v][y]<=l <=> 0+w+d[v][y]<=l-d[x][u].
Its equivalent to adding (x,v,l-d[x][u]) as new triplet.

You can always remove duplicate triples by keeping the one with has l maximum.
So you can use initial given triplets to generate O(n^2) new triplets.
At last, for each edges just check triplets which have an endpoint common with the edge.

Overall it takes O(n^3).

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

Did someone else use flows on Div2C??

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

    I did that too. I'm surprised so many people had greedy instead of this solution.

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

    Yeah! Dinic just worked fine.

    Was reluctant initially to implement as was quite sure it will TLE. Implemented it when the round was about to be over. Funny.

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

      Dinic on bipartite graphs works with complexity $$$O(|E|\cdot\sqrt{|V|})$$$.

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

    Yeah, I'm suprised that the Greedy apprroach work in this problem, my friends say that they use Greedy algo to solve without proof = )

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

A was so easy, everyone signed up for the contest, but the surprise was B. oh shit, contest is not beautiful

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

This really makes me hate myself.

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

div2 C problem: if he has only one friend, how can make other friends offended?

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

Any hints for div2C?

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

    one more

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

    Greedy works.

    1. Initially, for each day, select any friend available that day.
    2. Let's call the most common friend X. If friend X is chosen more than half the days, iterate over all days where friend X is selected and select any other friend. It can be shown this will not increase the count of any other friend above half. Stop if friend X's count is no longer more than half the days.
    3. If friend X still appears too many times (because there were too many days with no other friend available), it's impossible.
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    HINT 1:-

    if all friends appear in less than ceil(m/2) ... ans is pretty simple

    HINT 2:-

    if any friend(let's call him x) appear more than ceil(m/2) times then invite this friend for ceil(m/2) times on days and for rest days invite anyone(except the one you invited ceil(m/2) times already). This will automatically obey the condition.

    Now on which days should invite x.

    Invite x on those days in which only he is allowed(let call this num y) and rest on any day in which x is allowed.

    if(y>ceil(m/2) then ans = "NO" ..... It is obvious.

    I hope this helps

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

    I will try to explain what I did... Firstly I choose those friends whose count in all games (i.e-in all m days) is less than max allowed, Max allowed is ceil(m/2).We can use these friends on all days wherever they are possible because they can all be used at once and it will always be optimal and it will not violate the maximum usage condition. Now you can now take all the friends whose count is greater than max allowed.

    Now the question arises which friend to use and on which days to use. So, for each friend you can choose the days where there are less possibilities and that particular friend is possible on that day.I hope you understand.

    Sorry for my poor grammar.

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

110670278 Can anybody tell me what is wrong in this code. Thank You

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

I pass pretests in C, but why it doesn't turn green nor turn red?

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

    Does it mean FST?

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

      I had same issue with div2A. I got this reply : Some features may be disabled due to hosting Technocup, sorry for that. You got AC for A

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

    Check the standings. For some reason, the problems page is bugged.

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

    Same happened with me for A, when CF was down my same solution was submitted twice, due to which got 50 points penalty ;(

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

bring back the good old codeforces!!!

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

Why haven't system tests started yet?

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

But why does Div2 D/ Div 1 B have to be literal dog shit? It's almost like the people who proposed to let this kind of garbage appear in a Codeforces round don't want anyone to have fun participating it.

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

any hints for ques div2-B ?

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

I have some serious doubts about performance of alan4ik. I don't believe that any purple user is capable of solving B and C significantly faster than all reds (he solved B at 0:03, A at 0:07 and C at 0:16) and this competition being a mirror of Technocup explains pretty well how it was possible

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

I Encountered some problem while trying to submit problem A, which led to a delay in submit time and a down my ranking in the standing list, and the resulting from it confusion prevented me from focusing on the rest of the issues. Which of you happened to him like this?

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

Please add (n = 1) case to pretest in next contest. TY.

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

Me after FSTing on B : Hey cyan, here I come !

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

Weak pretests are so common now in codeforces.

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

in second test case of div2-B i am getting this result- ''wrong answer Jury has answer to test 34, but participant has not (test case 34)'' what does this mean ?

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

So painful to solve D just three minutes after the end
Yet so lovely that so many people got FST in B

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

    I solved D on 2:14:58

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

      Is your solution a Bruteforce ? What is its time complexity ?

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

        Whenever I delete some index at most I recalculate for 2 value because things change just for this index's next and before indexes currently in the array so I recalculate them.

        We can delete at most N indexes.

        So total complexity is O(N) but I am also using set hence my solution is O(NlogN) but can improve to O(N)

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

I see that the blog is being downvoted. What was wrong with the problems? I've heard that in the statement of D it was unclear whether the pairs are ordered or unordered, but I don't know what else was the fault of authors.

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

    this is at least disrespectful to the author

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

    D2B FSTs is the main reason I guess

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

    My suspicion is that this is largely motivated by the first two Div 2 tasks--A is significantly simpler than past Div 2 A's, and there were a number of ways to attempt B that led to lots of nasty edge cases. That said, I thought the Div 1 set was pretty nicely balanced. It's perhaps a little unfortunate that the range of problems that matters most for the majority of contestants (B/C/D) leaned towards the DS side of things, with the ad hocs placed at A and E, but that doesn't seem like the end of the world to me, and neither B nor C required absurdly nasty implementation.

    Another plausible explanation is that there were a large number of FSTs. I see this as perhaps a more legitimate reason to downvote; FSTing is extremely frustrating and unfair, given that it represents a significant disadvantage over failing pretests in spite of the fact that the root cause of failing pretests and of FSTing is essentially the same (i.e., submitting a buggy solution), and consequentially, I think authors have an obligation to minimize the number of FSTs that occur.

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

    As far as I check all the problems either in div1/div2 had some people FSTed so I think that's the reason.

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

      Huh? That's actually great. For a long time cf pretests are going in the wrong way. People stopped even caring about their solutions after seeing that the pretests are passed, while they should carefully check their time, memory and time relative to other participants. Pretests are here to help you catch bugs, but you should always be aware of on WA/TLE/RE on systests and be ready to resubmit if your running time on pretests isn't good enough.

      Last times I've seen that after systests my running time sometimes decreases which means that most times all the strongest tests are included in the pretests, which is bad.

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

        Isn't the point to construct as strong pretests as possible? I think pretests are here just to reduce the load on the judging servers, not to force participants to reread / test their solution after passing pretests.

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

          Actually I've never thought about pretests from this points of view, but probably this is the actual reason.

          Anyway, for me it always was another interesting feature of cf contests in comparison to other platforms, so I would've liked more tasks with weak pretests to make competition more interesting.

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

Is the contest still rated? please, let me know.

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

how n=1 is not in the pretest?

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

is CF-predictor working ??

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

    Nope. You can't visit other's ids. Maybe it is the case for the api as well. Cf tool must have stopped too i guess.

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

      any reason for that

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

        I am not exactly sure how cf-predictor works but it should have to fetch some data for your account. Since visiting ids was blocked by cf till some moments ago, cf-predictor was not working. It should be working now though.

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

мое решение получило ТЛ 20 на систестах, а переотправленное уже прошло. Посылка которая получила ТЛ 110676013, и посылка которая прошла 110673324 KAN MikeMirzayanov

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

    Bro, you're orange and you don't understand that there are natural fluctuantions in tests time and the consequences of that, seriously?

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

      he was red hello and you r blue, think u r smarter, seriously?

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

      You don’t understand that if solution gets TLE, then it is runned several times and if any of those runs gets OK, then your solution is considered correct. Seriously?

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

        I understand that it is perfectly natural because of fluctuations
        It would be one thing if the same solution passed with half the time of time limit
        But 4960 out of 5000 — this is ridiculous
        If your solution is on the borderline then depending on your luck it may pass and may not.
        AFAIK even now in case of TLE the code is restarted two times to mitigate the issue. But there is no way to solve the issue completely.

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

What should be output for this TC in Div2B 3 4 2 0

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

For div1A/div2C:

I used Dinic to solve it, modeling a graph with Source that gives (M+1)/2 to "left-side" nodes(that represents "friends"), adding an edge (of weight 1) to "right-side" nodes (that represents days) when that friend could be used on that day. Then i joined the "days" with SNK (weight 1) and run maxflow.

Anyone knows if it can work with Edmond-Karp or some Matching algorithm?

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

    You dont need to struggle that much. Although I dont know matching algos, it can be solved greedily. First go through all the days for which there is only one friend available, take him and increment his count.Then go through all the remaining days, take any person whose count is less than ceil(m/2). If at the end, there is any person with count > ceil(m/2), then print no, otherwise print the result.

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

    Hopcroft Karp algorithm should also fit.

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

Why https://codeforces.me/contest/1483/submission/110663953 gets TL, while https://codeforces.me/contest/1483/submission/110672560 gets Accepted in 4570 ms? The two files are identical

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

    How the hell were you able to submit the same code twice? Didn't it give any error?

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

      The second submission is in practice, it seems that the system does not compare contest submissions with practice submissions.

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

        Well, I have no clue why there is run time difference in 2 of your submissions but I want to say that hard-luck buddy! luck wasn't on your side in the contest.

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

I have a doubt. What is the correct size for declaring segment tree ? For problem C (skyline), I declared N as 3e5+5 and seg tree size as 3N. But it gave memory error on test 6. Then When I changed to 4N, it worked. Since the seg tree divides every node by 2, so the max size should not go beyond 2N right ? (N + N/2 +N/4 +... = 2N) ?

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

Для участников технокубка раунд рейтинговый?

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

I passed div2 A at 0:08 but why did my submission is skipped? I submitted div2 A again after i passed the B,but my A‘s score is not calculateed with the submission i submitted at 0:08。my score is lost!

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

    It wasn't lost. The dashboard was faulty. It didn't show green for A. But it was in the submission page. Then you submitted again. Therefore your previous submission is skipped.

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

How to see the probable rating change before the end of the round?

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

To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Finally.... reached expert today :)

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

in Proplem B Div 2

When can I say that the condition takes a value of 0?

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

    In three cases:

    1) whole array is increasing (with the same difference between adjacent values)(like: 1,3,5,7)

    2) whole array consists only one integer (like: 1,1,1,1)

    3) whole array is decreasing (with the same difference between adjacent values)(like: 7,5,3,1)

    if the difference is not same in case 1 and 3 then answer will be -1

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

when will ratings be updated ?

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

anyone getting notifications that someone wrote something ?

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

div 1.5 i guess

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

How to solve Div2D / Div1B?

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

    My solution is following. Notice that we will remove at most N numbers. So, if we can "fast" search next and remove it, then time complexity is O(n * (single_search+single_remove)). How can we remove element? You can do it with double-linked list or using set. How to find next pair? Let's maintain set of all indices of consecutive gcd = 1. Then, we need to find among all indices next from current position. In c++ you can do it with set and lower_bound. Or you could write segment tree. Probably there some other ways. When you delete number make sure you also remove all corresponding gcd = 1, and add new ones.

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

In DIV2 A and B, what arguments or justification you used while reaching to the solution ? Like what was your lane of thought .

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

    In Div2A we can think of a cell as a vertex in a graph and a broken wall as an edge. Let's also assume that there's a vertex that represents "outside of the prison". Then, the task is to find the minimum number of edges that a connected graph can have. In other words, the graph we're looking for is a tree which has n-1 edges. Including our "imaginary" vertex (because there must exist a connection with the "outside"), n = a * b + 1 so the number of edges is a * b.

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

    A: You can think of (a*b) cells + 1 outside as components of a disjoint set. Opening any wall means joining two componenets. As we need to merge a*b + 1 components to 1 we need at least a*b wall breaks. Then you can easily create a solution which satisfies this for eg. breaking the bottom wall of each cell.

    B: If the array satisifies a generator there can be only two cases for each pair of adjacent elements: a[i] >= a[i-1] and a[i] = a[i-1] + c, and a[i] < a[i-1] and a[i] = (a[i-1] + c — m).
    After checking that each case has only one difference in it, you need both these cases occuring to fix one (m,c) pair else m can be arbitrarily large.

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

Getting error 'You are not allowed to view the contest' when trying to open Div2 contest (ID 1484). Please fix, I'd like to look at the problem statements again.

MikeMirzayanov KAN

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

I found out that the link to the div 2 round is not working. It said that I am not allowed to view such contest! Please fix it. @MikeMirzayanov

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

When can we view others' code?

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

It seems the prompt for Div2 Problem B was misleading. It said that c is nonnegative and that a[i] = a[i-1] + c. That led me to conclude that arrays that are monotonically decreasing have no solution, but that doesn't seem to be the case based on some of the comments (Codeforces is not currently allowing access to the div2 problems so I can't check the testcases I missed).

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

Codeforces Round #709 (Div.1 only)

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

Is there a reason why problems A,B in Div.2 cannot be viewed?

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

Can anyone please explain how to solve DIV2 C (DIV1 A) using flow?

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

    The problem can be reduced to finding the maximum bipartite matching of the friends with the days, restricting the capacity from the source to each friend to (m+1)/2.

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

    Dude, why do you implement flows to solve this simple problem? Anyways using flows will most probably give TLE.

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

      I'm not sure if greedy will work if constraints were changed to m/4 or m/3. Also I cannot prove if greedy is always correct, it's just seems intuitively correct because of large constraints.

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

        Greedy works because after any assignment there can only be one invalid friend. Then while greedily reassigning friend during the days where this invalid friend was chosen, there is no possibility that a newly assigned friend will become invalid, because if we consider the frequencies of the previously assigned and newly assigned friends:

        For even m closest case would be: $$$(m/2 + 1,m/2 - 1)$$$ to $$$(m/2,m/2)$$$

        For odd m closest case would be: $$$((m+1)/2 + 1, (m+1)/2 - 2)$$$ to $$$((m+1)/2, (m+1)/2 - 1)$$$.

        In both cases, the invalid friend becomes valid and the valid one stays valid. Of course it woudn't work if the limit was changed, that was the point of the problem.

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

      can we use dp, where we maintain the frequencies of the friends in a map and for each day if the frequency is less than ceil(m/2) then we push it and call the next day recursively? and we end it when the call has an empty list of list of friends ?

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

        Hey, I just did it using the same way, but getting WA, could you please help me in telling the case I am missing. IMO I don't think you need more than two friends to come on a single day to get to the answer. Submission: https://codeforces.me/contest/1484/submission/110655268

        But when it got a WA to me, so I expanded it a bit for checking for all friends. Submission: https://codeforces.me/contest/1484/submission/110660421

        But I not able to find out the Error.

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

          im getting WA on tc2 for the same reason too, even I wanted to know why dynamic programming is not working in this case.

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

            Ig this is not always optimal. Suppose x and y are available on second last day and only x is available on last day and count of x is (ceil(m/2)-1) and count of y is 0 till third last day.

            So now we should take y on second last day and x on last day for optimal answer. But as per your approach you can end up selecting x on second last day and having no choice on last day.

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

              When I chose x and have no choice on last day , the call comes back negative for the call in which I chose x and the function proceeds to chose y and check again , this tome it will get a true

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

                I can't access your newest submission. Try the test case commented below. Your earlier submission(which I can access) fails in that case

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

              You should see my submission once again. I am handling the cases with only one person on one day initially. And then checking for others. There won't be any case because we will first check for the day with only one person.

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

MikeMirzayanov почему мы не можем смотреть коды других участников из DIV1?

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

These rating changes don't seem appropriate, is there some extra +ve rating given in the first few contests? , I would like to know more about this...

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

Would you please describe the details of the complexity analysis about Div2. D in editorial?

This problem is still puzzling me.

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

I just realized I got only 438 points for problem A, but I did solve it in under 5 minutes. There are many who took more time and still got more points, is it because I submitted my problem twice? because the first time the server went down while it was in queue.

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

where is div2? I cant open it.

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

when to publish the tutorial?

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

can anyone please explain the approach to problem D? i have no clue how to do it..

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

MikeMirzayanov Please update problem rates.

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

Sorry if it's too late, but i think C div.1 can solve using divide and conquer and greedy with a bit more data structures.

See my code : 110746829

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

    Let $$$solve(l, r)$$$ be the answer for segment $$$[l, r]$$$ then you choose the building $$$m$$$ with minimum $$$h_m$$$. You easy calculate it in O(1) if you have the answer for segment $$$[l, m - 1]$$$ and $$$[m + 1, r]$$$. Let's call these answer are $$$left$$$ and $$$right$$$.

    There're two case here:

    1. $$$b_m$$$ contain in the answer then $$$ans = right + left + b_m$$$
    2. $$$b_m$$$ does not contain in the answer, that mean it must be in same picture with $$$l - 1$$$ or $$$r + 1$$$ or both.
    • If $$$l > 1$$$ and it is in same with $$$l - 1$$$ then $$$ans = right$$$.
    • If $$$r < n$$$ and it is in same with $$$r + 1$$$ then $$$ans = left$$$
    • If $$$l > 1, r < n$$$ and it is in same picture with both then $$$ans = 0$$$.

    Take max all of these, and you got the final answer.

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

Any plans to add english editorial authors ?

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

KAN any updates on the english editorial?

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

Thanks to everyone who downvoted my survey is accomplished. Also, thanks to Dragnoid99 to make it possible faster. ORZ community

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

At this point I think I will just try google translating the Russian slides instead of waiting for the editorial.

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

god! Am I the only rookie praying for tutorial?

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

Instead waiting for English tutorials to be posted, i am going to learn russian to speed up the process.

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

Here is the English Editorial version (using Google Translate) of "Slides in Russian" which is attached to the Announcement — Google Translate Version Of Technocup 2021 Final(CF — 709) Editorial .

Hope it helps before the official editorial gets published.
Thank You !

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

    Sorry, I mistook.

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

      I am not the editorialist.
      I have just translated the Russian one which is attached to the Announcement using Google Translate and put them in a Document for the curious ones.

      UPD : Glad you understand my point.

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

In case anyone is curious about the solutions to the problems, I wrote up an unofficial editorial for all the problems except Div. 1 F at https://codeforces.me/blog/entry/88944.

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

please post editorial asap !!

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

I'm not sure why editorial is not out yet, but I was the writer of Div2E/Div1C, so ill post the editorial I had written for the solution I had in mind, hope it helps out.

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

Thomas had never seen such long delay for editorials

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

Please, upload the editorial. It's been 3 days.

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

It's frustrating to wait so long for the editorial

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

Can the editorial link be posted on the announcement also? KAN

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

How to solve div2F/div1D?