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

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

Большое спасибо!

Вам за участие

Привет, Codeforces!

Рады пригласить вас на Codeforces Round 816 (Div. 2), который пройдет в 20.08.2022 17:35 (Московское время). Раунд будет рейтинговым только для второго дивизиона. У вас будет 2 часа на решение 6 задач. Советуем прочитать все задачи.

Раунд полностью подготовлен и составлен учениками ЛКШ Зима (зимняя смена Летней Компьютерной Школы). В течение смены мы придумали для вас интересные и креативные задачи. Вы можете ознакомиться с предыдущими раундами, подготовленными учениками ЛКШ: Codeforces Round 815 (Div. 2), Codeforces Round #694, Codeforces Round #612, Codeforces Round #530

Огромное спасибо

Разбалловка будет опубликована перед началом.

Ждем вас на нашем раунде, а также в ЛКШ!

Удачи, высокого рейтинга и удовольствия от решения задач!

UPD — Разбалловка:

$$$500 - 1000 - 1750 - 2250 - 2750 - 3000$$$

В контесте могут быть интерактивные задачи! Обязательно прочитайте этот пост.

UPD 2 — Доступен разбор!

UPD 3 — Громкие овации победителям!

Официальные участники:

  1. william556
  2. fursuit
  3. huge_waxberry
  4. lbwhangbeateveryone
  5. Longiseta

Все участники:

  1. jiangly
  2. kotatsugame
  3. hitonanode
  4. ksun48
  5. Rubikun
  • Проголосовать: нравится
  • +703
  • Проголосовать: не нравится

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

UPD: Large text has reached its limit! Good luck on the round!

178 upvotes on this comment and the larger large text becomes even larger!

57 upvotes on this comment and the large text becomes even larger!

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

Big comment text for upvotes

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

    Italic comment text for upvotes

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

      ᵗᶦⁿʸ ᶜᵒᵐᵐᵉⁿᵗ ᵗᵉˣᵗ ᶠᵒʳ ᵘᵖᵛᵒᵗᵉˢ

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

        Русскоязычный текст комментария для лайков

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

          sǝʇoʌdn ɹoⅎ ʇxǝʇ ʇuǝɯɯoɔ pǝddᴉʅᖵ

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

            Monospace comment text for upvotes.

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

        hidden comment text for upvotes

        UPD 1 : there was simple instead of hidden before. UPD 2 : there was not before written on the upper line.

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

As a (supposed) tester, I don't even remember testing this round but it should be good.

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

3 раунда от московских школьников подряд, кайф)

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

    Если ШЦПМ это московская школа, то может даже 4.

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

      Как известно, АНО ОШ «ЦПМ» является самой московской школой среди всех московских школ.

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

    Я бы сказал, 5 раундов подряд будет)

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

Same setters for this as well as the previous round, nice!

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

winter Summer Informatics School

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

С Новым годом!

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

As a tester, I don't remember tasks.

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

Hope to become an expert!

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

Well, it got my attention. The round better live up to your hype now, that's all I've got to say.

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

Float like a butterfly, Sting like codeforces.

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

Very excited!

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

All these Contests back to back, as coders we are just loving it :)

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

Good Luck

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

Hope to become pupil(lll¬ω¬)

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

I finally found SomethingNew that I have glebustim, now I KAN participate in this contest :)

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

As a student, I will try my best to solve the problems.

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

(* ^ ω ^) comment ʕ ᵔᴥᵔ ʔ with (▽◕ ᴥ ◕▽) cute ❤❤❤ emoticons ❤ (ɔˆз(ˆ⌣ˆc) for (ノ◕ヮ◕)ノ*:・゚✧ upvotes (◕‿◕)

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

The same but not the same time :(

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

Just a random question but if anyone knows about it please reply. Here is the question:

I may not be able to participate in today's contest but i saw in the calendar that the next contest is going to be held on the 2nd of September. Do you know if any contests are taking place before that date? If not i might have to cancel everything and participate.

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

Hoping not to see grid in problem A.

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

I hope the problem statements are short, crisp and clear.

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
The contest may contain interactive problems!

Hope it doesn't >_<.

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

Ah, that score distribution is looking dangerous.

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

I want to be expert

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

.

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

Div 1.5

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

C seems tedious

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

    not much, but i struggled for an hour on what i think was some overflow (WA on pretest 2). At the end i just put ll everywhere and it passed the pretests

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

It's hard for me to imagine what the author's mindset was when he wanted to put that hard tasks to 2C, only to make this LARGE GAP?

I know! The large text stands for the large gap, right?

Conclusion: gapforces, speedforces.

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

I couldn't see the problems for the past 15 minutes. It keeps saying "Bad Gateway 505". Anyone else?

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

[deleted]

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

Nice round!No mutitestcases! C is a little difficult,but interesting!

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

Large Gap

to make you get negative rating change.

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

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

I TLEd on 2 different problems using Java and passed in C++. Not sure if it has something to do with my implementation, but I never encountered this on CF before.
I liked the problems though.

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

So sad, that i solved C too late. Could've solved 20 minutes faster, if i would've not been wasting time on E. At least now it's my bad. Thanks for contests, SIS! Was glad to participate in all of them! Hope to see more contests of yours!

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

Сегодня я попросил родителей, чтобы они пораньше затопили баню, потому что у меня вечером раунд. В итоге мне пришлось сразу после бани бежать на раунд, даже не поев. Но я не разочаровался, задачи действительно неплохие!

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

Can somebody explain C? For me it is much harder than D

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

    Let's say, you know the result for the initial array. Try to find how changing one value will affect the result.

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

      ok, its easy to observe that, but how do you store data? do we need to have length of every block stored?

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

        No, you don't have to store the length of every block.

        If you are updating index i, then ans will only change depending on its adjacent indexes (i-1 and i+1).

        My Submisson: 169128778

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

        You don't need to store anything. Once you find the awesomeness of the initial array, it is straightforward to calculate the change in the awesomeness if one value is changed. You only have to keep track of the current awesomeness and the array itself.

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

      Is this about writing $$$998244353$$$ if statements or is there a clean way to do it?

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

      I tried, but couldn't come up with something fast

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

    Though it took me a lot of time to solve this, general idea for any such problem is, we want to know, if there is something with a[i-1],a[i] and a[i],a[i+1], when we do an update on index i.

    You can check that our summation for a given array of size n = (n*(n+1))/2 + sum of (n-1-x)*(x+1), where 0<=x<n-1 and a[x]!=a[x+1].

    Now, it is easy to refer to 169149222

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

    Individual contribution of each index to the whole. So, if all numbers are distinct, then each index contributes (i + 1) * (n — i) to the total sum.

    When you modify a number, check if it is equal to the left or right index. If it is, then subtract its individual contribution from the sum. If it was equal but now different, then add its individual contribution to the sum.

    The exact individual contribution formula is weird and just takes a lot of time to find. (Ex. it's different if it's the same as the left neighbour vs the right neighbour, different for the first element, middle elements, and the last elements etc.)

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

    I tried writing an explanation but I found I was unable to explain it clearly. Nonetheless I have left the explanation in case it helps.

    First, how to calculate answer overall? Calculating prefix of blocks is simple, and all subarray s contianing the first element must sum all these. Then just iterate from left to right and if you find a new block, subtract (length remaining — 1), otherwise subtract -1. Answer is sum of all this.

    To be clear: suppose you have 1 2 2 3 2 4 block_prefix = 1 2 2 3 4 5 answer for v[0] = 5 + 4 + 3 + 2 + 2 + 1 = 17 answer for v[1] = 17 — 5 (remaining numbers) — 1 = 11 answer for v[2] = 10 (since it's the same block, we only remove 1 from the answer) // and so on

    final answer is sum of all these.

    So now we know how to find the initial answer in O(n). How would it help us find the answer?

    After a query: we have 4 cases

    either this element begins a block on the left or begins a block on the right or breaks a block on the left or breaks a block on the right

    If it begins a block on the left, we subtract 1 from all the elements to our left. If it begins a block on the right, we subtract a 1 from all the elements to our left including us. We just reverse this if it breaks a block.

    for(int d=0;d<m;d++) {
                int i,x;
                cin>>i>>x;
                --i;
                int l = n &mdash; i;
                if(v[i] != x) {
                    // Case 1: We are breaking a block on the left hand side
                    if(i != 0 && v[i] == v[i-1]) {
                        s += (l*i);
                    }
                    // Case 2: We are breaking a block also on the right hand side
                    if(i != n-1 && v[i+1] == v[i]) {
                        s += (l-1)*(i+1);
                    }
                    // Case 3: We are creating a block on the left hand side
                    if(i != 0 && x == v[i-1]) {
                        s -= (l*i);
                    }
                    // Case 4: We are creating a block also on the right hand side
                    if(i != n-1 && v[i+1] == x) {
                        s -= (l-1)*(i+1);
                    }
                }
                v[i] = x;
                cout<<s<<'\n';
            }
        }
    
  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    You just need to understand how often subarray of length 2 appear in array.

    For exmp:

    1 2 3 4 5

    Currently ans = 35. Lets say we want to change 3rd (pos = 3) element (1-indexed) to 2, so it became this:

    1 2 2 4 5

    Now we consider 2 things:

    was a[pos] equal a[pos + 1] before and if it is equal now. If it was equal and now it isn't, we just need to decrease ans by how many times does this subarray appears. In this exmp it appears 6 times: {2, 2}, {2, 2, 4}, {2, 2, 4, 5}, {1, 2, 2}, {1, 2, 2, 4}, {1, 2, 2, 4, 5}. So, now ans = ans — 6, so it is equal to 29. Else we increase ans by this number.

    was a[pos — 1] equal to a[pos] before and if it is equal now. (Do the same as this 1st case).

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

      Thank you very much! I realized my main mistake was thinking and writing some long and difficult formula. But now I see the solution was quite clear

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

    Try to think of a way to calculate the contribution of each index in O(1) time. Any number affects only the numbers just after and before it. Then the problem is simple. Whenever any number is changed, subtract the contributions of the 3 numbers(before, after and itself). Then add the new contributions after a number is changed.

    As far as calculating contribution, think of it this way — All numbers in a block except one are useless.

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

    First calculate maximum answer (i.e when all elements are distinct)

    Let B[i] = arr[i] == arr[i+1] with length n-1. Then subtract from maximum answer the sum of all subarrays of B (which can be done in O(n)). Answering queries can be done by extending the idea of sum of all subarrays: update can only change 2 values of B and it's easy to recalculate new sum of B.

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

    Assuming we have an array $$$pref$$$ where $$$pref[i]$$$ is the number of elements with indices $$$k\leq i$$$ where $$$arr[k]\neq arr[k-1]$$$. For a given $$$[L, R]$$$ segment, its awesomeness $$$=pref[r]-pref[l]+1$$$. Hence, the answer is $$$\dfrac{N*(N+1)}{2}$$$ + $$$\sum_{i=1}^{n}{\sum_{j=i}^{n}{pref[j]-pref[i]}}$$$ $$$=$$$ $$$\dfrac{N*(N+1)}{2}$$$ $$$+$$$ $$$1*pref[1]+2*pref[2]+...+n*pref[n]$$$ $$$-n*pref[1]-(n-1)*pref[2]-...-1*pref[n]$$$.

    So, whenever $$$arr[i]$$$ changes, it can can add $$$\pm 1$$$ to $$$pref[i]$$$, $$$pref[i+1]$$$, ..., $$$pref[n]$$$ (if the equality between $$$arr[i]$$$ and $$$arr[i-1]$$$ changes) and can add $$$\pm 1$$$ to $$$pref[i+1]$$$, $$$pref[i+2]$$$, ..., $$$pref[n]$$$ (if the equality between $$$arr[i+1]$$$ and $$$arr[i]$$$ changes.

    The effect of adding or subtracting $$$1$$$ to all prefix values in some suffix corresponds to adding or subtracting arithmetic sums to the answer, e.g, if we add $$$1$$$ to all the prefix values in the suffix starting at $$$k$$$, this corresponds to setting $$$ans$$$ to $$$ans+\sum_{i=k}^{n}{i}-\sum_{i=1}^{n-k+1}{i}$$$.

    Hence, we can process each query and modify our answer accordingly as needed then print the modified answer.

    Submission

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

    The initial answer is easy with DP. Then for every update at position i, you consider all segments including i, you check how their contribution change. To make life easier, you can classify segments into 3 types: 1. ends at i 2. starts from i 3. i is neither end nor start. That's the basic idea.

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

Thanks for the extra 15 minutes!

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

    I can see you solved C, can you please explain your approach !

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

      I guess there are already good explanations in other comments, but to come up with the idea, you should notice that even without any query, since n<=10^5, you already need around O(n)/O(nlogn) approach to find the initial beauty. Once you figure out the formula to calculate beauty in O(n) it's easier for you to handle queries in O(1).

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

Did anyone solve D with Python? I got TLE on pretest 4 :(

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

Yet another "speedforces" contest

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

can someone point out what's wrong with my submission for div 2 C?

spent basically the entire contest failing to figure out my mistake

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

Any hint for D?

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

    You can $$$and$$$ all the $$$x$$$ values of the triplets $$$l, r, x$$$ with $$$l = i$$$ or $$$r = i$$$ to find out which bits can/can't be placed at $$$a[i]$$$.

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

    First consider the case of $$$i = j$$$ in a statement.

    Then find all bit positions that MUST be 0. Then find all bit positions that MUST be 1. After this, you can greedily construct the lexicographically least array by deciding on the bits that are still unknown.

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

    Denote $$$unset[i]$$$ as the mask representing bits that must be unset in $$$arr[i]$$$, this can be known from the unset bits in $$$x$$$ values which are the result of an $$$OR$$$ operation with $$$arr[i]$$$.

    So we can calculate first the array $$$unset$$$ and then iterate on the queries. For the $$$qi^{th}$$$ query, for every bit set in $$$x$$$ and must be unset in one of $$$arr[i]$$$ and $$$arr[j]$$$, then we are sure we must set it in the other element. This has to be done before any further processing to ensure no extra unneeded bits are set somewhere.

    What is remaining is those $$$x$$$ values where some set bits in them can be set in either $$$arr[i]$$$ or $$$arr[j]$$$. Assuming $$$j\geq i$$$, let's sort first the queries in ascending order of $$$j$$$, then process the queries in that order, and whenever we find a set bit in $$$x$$$ that is still unset in $$$i$$$ and $$$j$$$, set it in $$$j$$$.

    The reason for that latest sorting done on queries is to handle the case when we have queries $$${i, j, x_1}$$$ and $$${j, k, x_2}$$$, where $$$i<j<k$$$ and the $$$k^{th}$$$ bit is set in $$$x_1$$$ and $$$x_2$$$. So, it is sufficient here to set the $$$k^{th}$$$ bit only in $$$j$$$.

    Submission

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

    If i-th bit of x is 0, then i-th bit of a[l] and a[r] must be 0. After that consider all queries where l = 1 (1-indexing). If i-th bit of x is 1 and i-th bit of a[r] must be 0, then we have to set 1 at i-th bit of a[1]. After considering all queries where l = 1 we can do it one more time, but now if i-th bit of x is 1 and i-th bit of a[1] is also 1, then we don't have to set 1 at i-th bit of a[r]. Now we do the same for all 2 <= l <= n

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

Any Hints for Problem F? Can we solve the 1-d version (farm's top-right corner being (100,1)) in 3 steps?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    If my solution passes system tests, then...
    In fact
    A way to begin
    Continued...
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you update values of blocks optimally for each query? This got me stuck hard on C

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

    You don't need to — the length of the blocks is immaterial, the only thing you care about is if a block is created or not.

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

    i don't know if there is an easier solution but either u use segment tree with lazy propagation or using BIT ( binary indexed tree)

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

      I thought about both, not familiar with lazy version of segTree, but couldn't get a grip on any of the two.

      But I agree with the above comment, I knew there was some kind of calculation possible to pretty much calculate everything after each query. Couldn't find it either, lol

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

jjj

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

Speedforces and this is me on B; -100 delta incoming

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

Why would you put 1.5sec for D, just why... You made such a good problem and then you screw it with a shit TL...

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

HOW I GOT TL ON THIS 169153949

Can someone help me ?

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

Me who used multiset of structures to solve C and understanding the intended solution now..

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

    i used segment tree and i got a "beautiful" wrong answer which is really annoying

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

This round is neither bitforces nor mathforces, i like it !, Codeforces should have more rounds like this

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

.

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

Can someone please explain what's wrong with my code for B?
https://mirror.codeforces.com/contest/1715/submission/169117875

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

Could Anyone Explain How to Solve Problem B I am Struggling in it :(

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

    The minimum $$$s$$$ is if $$$bk$$$ if each $$$a_i$$$ is divisible by $$$k$$$. There is no way to decrease $$$s$$$ because reducing any value of $$$a_i$$$ will reduce the overall beauty.

    On the other hand, if $$$a_i$$$ is divisible by $$$k$$$, then you can increase $$$a_i$$$ by up to $$$k - 1$$$ without changing the result of the floor division, i.e., beauty contribution remains the same. Therefore, the maximum $$$s$$$ is $$$bk + k (n - 1)$$$.

    So we can start by putting $$$bk$$$ in the first (or last) element to secure the beauty of $$$b$$$. If we still haven't reached our target of $$$s$$$, we can add up to $$$k - 1$$$ in each element (including the first/last!) to reach our target of $$$s$$$ without altering the beauty.

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

    One idea is to build an array with correct beauty, in example by setting a[0] to b*k.

    Most likely then the sum of a[] is smaller than s. But we can see that we can up to k-1 to each element in a[] without changing the beauty. So we update elements in a until the sum of the elements conforms to s.

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

I'm so glad I NOPE'd at C so fast and moved straight to D, which I felt was much easier than C.

Even after I returned to C (after solving D), I couldn't even figure out how to compute the initial awesomeness value for C in sub-quadratic time...

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

    Was D some graph theory problem or what? For me it was harder, than C

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

      Not so much graph involved, just some basic knowledge of connected components imo

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

      Nah, you just need to think about how bitwise OR constrains the values and then greedily construct the array.

      If $$$i = j$$$ for a statement, then $$$a_i$$$ is exactly equal to the result.

      Each statement is essentially 30 statements, each involving the OR of two bits.

      For bits $$$p$$$ and $$$q$$$, the statement $$$p \mid q = 0$$$ means $$$p = q = 0$$$. So now we only need to worry about statements where the result is 1.

      For bit $$$p$$$, the statement $$$p \mid 0 = 1$$$ means $$$p = 1$$$. After this, all that's left are $$$p \mid q = 1$$$ statements where neither $$$p$$$ nor $$$q$$$ are fixed.

      Now we can greedily construct the lexicographically least result: start with $$$a_1$$$, clear all of its uncertain bits to $$$0$$$, and check all $$$p \mid q = 1$$$ statements that involve an $$$a_1$$$ bit, setting the other bit to $$$1$$$. Repeat for $$$a_2$$$, and so on.

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

How to solve E?

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

    Relevant Problem

    Suppose $$$distance[i][v]$$$ gives the minimum distance of node $$$v$$$ from node $$$1$$$ on using atmost $$$i$$$ flights.

    Do standard dijkstra to find $$$distance[0][v]$$$

    Now repeat this process for $$$i(1 \leq i \leq k)$$$

    Suppose you use some flight. So find $$$distance[i][v]$$$ on using values of $$$distance[i-1]$$$ (use Convex Hull trick)

    Transition state is $$$distance[i][v] = minimum(distance[i-1][u]+u^2 - 2 \cdot u \cdot v) + v^2(1 \leq u \leq n)$$$

    Do standard dijkstra to update $$$distance[i][v]$$$

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

      How to calculate minimum(distance[i−1][u]+u^2−2⋅u⋅v) quickly?

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

        You can use CHT to do that. Kind of similar to this.

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

        you can also use divide and conquer :D, which i think is more approachable than cht(i dont know how to do cht).

        Lets say you already have the minimum distances to all nodes if you use $$$f$$$ flights. I'm gonna denote the distance to node $$$a$$$ from source vertex $$$1$$$ if you use $$$f$$$ flights as $$$dist_{a,f}$$$. If you find the answer for some node $$$v$$$, which can obviously done in linear time by brute forcing all possible flights to $$$v$$$, you can find the optimal $$$u$$$ to minimize $$$dist_{u,f}+(v-u)^2$$$. Notice that, for any $$$x$$$ where $$$x<v$$$, you don't have to consider any flights where the node you travel from has a greater index than $$$u$$$.

        Let's say there exists a node $$$t$$$ where $$$dist_{t,f}+(x-t)^2$$$ < $$$dist_{u,f}+(x-u)^2$$$ and $$$t>u$$$. Note that disproving this statement suffices for a proof, since we will check all $$$t$$$ where $$$t \leq u$$$ anyways. If the inequality from before is true, then it will contradict the statement $$$dist_{u,f}+(v-u)^2 < dist_{t,f}+(v-t)^2$$$, since $$$(x-t)^2-(v-t)^2 > (x-u)^2-(v-u)^2$$$, since $$$t>u$$$ and $$$x<v$$$. Because we know that $$$dist_{u,f}+(v-u)^2 < dist_{t,f}+(v-t)^2$$$ is true from bruteforcing $$$u$$$, $$$dist_{t,f}+(x-t)^2$$$ < $$$dist_{u,f}+(x-u)^2$$$ simply can't be true.

        The same thing can probably be applied to the case where $$$x>v$$$, too. In that case, we don't need to check any $$$t$$$ where $$$t<u$$$.

        Now how is this information helpful? This leads to the divide and conquer solution; in the first stage we can pick the middle element from $$$1 \dots n$$$ and figure out the answer for that middle element. Then, we can split the range into $$$1 \dots mid-1$$$ where we only have to check $$$1 \dots v$$$, as well as $$$mid+1 \dots r$$$ where we only need to check nodes $$$v \dots n$$$ to travel from. Because the depth of recursion doesnt exceed $$$\log n$$$, and because each $$$v$$$ will only be checked in one branch of the recursion, this results in $$$O(n \log n)$$$ time complexity.

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

when will the editorial for this round be available?

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

Can anyone pass problem C in python? My solution is in O(n) time complexity, yet TLE on problem C.

https://mirror.codeforces.com/contest/1715/submission/169148981

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    import sys
    input = lambda: sys.stdin.readline().strip()
    

    try to add these two lines before your codes and submit again

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

can we solve C using Segment tree ?

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

Solved Div2 D for XOR instead of OR :'(

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Code for anyone who did the same
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Code for OR. Turns out it is way easier than the XOR counterpart. Its always XOR. Why Codeforces OR now? :‑|

      Code for Div2 D
»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

the pretests at the last two contests were really terrible

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

in problem F, I submited this code and got Wrong Answer during the contest. So I submit another code after that. But the first code should be AC because of the wrong checker.

It makes me lose scores by resubmission. I hope my score could be be back :-( don't skip my code and give me the correct score, thx.

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

I hate pretests
On your contests
They're very bad
It's really sad

XD

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

Can someone tell on which test case my solution for Problem B is failing. https://mirror.codeforces.com/contest/1715/submission/169148352

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

    For example:

    2 2 2 6

    the answer should be 3 3

    but not 1 1 4

    (if it is wrong, just ignore it~

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

I apologize that there were technical issues during the round today. Ratings updated preliminarily. We will remove cheaters and update the ratings again soon.

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

    Thanks for your work. btw, some people submit problem F again during contest because of technical issues of checker. I suggest recalculate their scores if it is possible, thanks again.

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

hey guys, can someone please tell me what was wrong with my C submition? https://mirror.codeforces.com/contest/1715/submission/169155228

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

Hope I get an increase after rechecking

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

I do not pass F on protests, although I solved it on testing)))))))))))

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

Hello MikeMirzayanov,

When CF was down in the midway, I submitted the exactly same solution twice (submission1 and submission2). One from codeforces.com and second from m1.codeforces.com as I was not able to see status. I still got first submission skipped and penalty for resubmission. Can you please look into it?

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

thanks for the amazing problems in this and previous round, definetly would like to see more contests like this

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

Can someone explain me why these 2 solutions have 2 different verdicts :thinking:? https://mirror.codeforces.com/contest/1715/submission/169136307 and https://mirror.codeforces.com/contest/1715/submission/169166978

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

Problem E is very nice

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

Really don't like this round, for :

Task A
Task C
Task D
Task E
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Very agree.E is the worst problem, it does not have any thinking content but only needs boring algorithms.

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

      I don't agree with "boring algorithms", cht/lichao tree are quite interesting as a concept

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

    I think that task was fit for div. 2, but maybe not for div. 1, since it's quite standard and a lot of div. 1 users would solve it without much thinking.

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

      Well but this trick is too high level for div2 contestants. And also everything besides this trick is quite standard

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

The system tests for problem D are too weak. Please retest it.

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

C time constraints are too tight for python :/ my linear solution TLE'd during the contest but a C++ translation worked

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

Trash contest

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

If you people don't have enough brain to choose what kinda problems to set, please, don't set it,else please give clear problem statements

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

I feel sorry for whomever had to write the interactor for problem F