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

Автор awoo, история, 9 месяцев назад, По-русски

Привет, Codeforces!

В 23.02.2024 17:35 (Московское время) состоится Educational Codeforces Round 162 (Rated for Div. 2).

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

UPD: Разбор опубликован

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

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

Good luck to everyone!

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

    HERESY! Weak CPers are not allowed to use a picture of the Lord as their pfp.

    I advise you to quickly change your pfp and repent for your sins before the Holy Church Of Bateman is forced to take punitive action.

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

Such a short and clear announcement I hope problems statements be like this too!

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

Hope able to solve ABC this round

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

Hope able to AK this round

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

Good luck to everyone! (please upvote i need contribution)

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

Very excited for the upcoming contest

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

Good luck to all , i hope to solve ABC

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

Excited!

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

_Good luck _

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

Excited to get to Expert

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

whyyy?

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

Hope to solve ABCDEFGHIJKLMNOPQRSTUVWXYZ in this round (i'm a divinity i can do things you dont think are possible)

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

Hope to reach 2024

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

I think the title should say [Rated upto div2] instead of [Rated for div2]

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

I think the title should say [Rated upto div2] instead of [Rated for div2]

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

    Div. 2 includes all ratings below 2100 (if there's no Div. 1 contest)

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

      Oh then why we have div3 and div4 contests.. if no such division exists?

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

        Div. 3 and Div. 4 are not exclusive to Div. 2. Usually Div. 3 includes Div. 4 and Div. 2 includes Div. 3 and Div. 4. The only exception so far, to my knowledge, was https://codeforces.me/blog/entry/121579 this Div. 1 & 2 & 3 contest.

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

        Historically, there were no Div. 3 and Div. 4 long time ago. They were added later as a part of Div. 2 for new type of contests that are newbie-friendly.

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

My last contest in this winter vacation

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

Good luck to everyone =D

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

good luck from good duck !!!

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

Score distribution?

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

Who tested?

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

good luck :>

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

Educational rounds are mathforces af, thats a skip

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

Just to let you guys know vimdhayak ji is here

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

Enjoy the contest!

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

stay up to late again:)

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

Small and clear announcement. Hopefully we will enjoy this contest. </>

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

Good luck everybody. Hope to get positive delta :)

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

Ah Shit, Here We Go Again.

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

Missed opportunity to name problem C. as "Find C"

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

Do we write outputs for each test case as it comes or all the way at the end?

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

    Either way works, however it's much simpler and more efficient to output as it comes.

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

Finally, Goodbye 2023 has a worthy competitor.

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

It's like Div 1.5

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

B>>>C

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

Speedforcing abcde

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

B < A

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

cheaters ruined the contest again , that's very sad

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

problem D :(

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

    it was just about binary search.

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

      What's your approach?

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

        for each index,i checked on both sides and if any side's sum exceed the number at current index than can compress the range.Also note that if any side's range have all number same then will not consider that side.

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

          how did you find if all numbers are same in a range?

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

            For example, arr=[1,1,2,3,3,3] i stored the ranges (0,1) , (2,2) , (3,5) in a vector 'vec' in sorted manner. It can be done in O(n).

            now suppose i want to check if (4,5) has all number same,what will i do? i will find the largest index in vec such that vec[i][0]<=4, now i will check if vec[i][1]>=5 than (4,5) lies under the range (vec[i][0],vec[i][1]) otherwise some numbers are diff.

            Just binary search things...

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

              you can check it easy if all elements in the segments are the same or not you can use prefix sum and check if the summation in the segment is equal to r-l

              vector<ll>id(n+1);
              for(int x=1;x<=n;x++){
                  if(v[x]==v[x-1]) id[x] =id[x-1]+1;
                  else id[x] = id[x-1];
              }
              if(id[r]-id[l]==r-l) all elemnts are the same 
              
            • »
              »
              »
              »
              »
              »
              »
              9 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Understood it! Thanks

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

            I did it with sparse table.

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

I couldn't get the implementation for B right for over an hour... fml

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

E too easy to be an E, swap D and E

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

cheaters ruined the contest again :(

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

    just train more, yours perfomance is bad not because of cheaters

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

Nice problem F! Thanks!

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

    How to solve it? My intuition is that we will perform 2nd operation at most once. Since number of 1s stays constant , we will try to merge 1s as close as possible.

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

      That's it! (I didn't realize we needn't do the 2nd operation twice in the contest QWQ)

      When we perform the 2nd operation only once, we can consider on the reversed string. We can try all positions for the highest bit, and binary search on the final length of the string ignoring leading zeroes.

      If the positions of the highest bit and the lowest bit are determined, the greedy solution is to put all 1 outside to the last few 0s in the interval, so the prefix of some length doesn't change. So we can use hash or suffix array to compare the prefixes, and then the best starting position can be determined.

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

    But I think it's hard to write it.

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

I finally joined the dark side, selling my soul to Atcoder!

If you want to build intuition and upsolve problem D without looking at the editorial, try out 1901D : Yet Another Monster Fight. I've added hints as well.

A major hint for this problem:

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

after getting 15 WA on problem C, I wished contest end earlier.

screwed up, going gray again

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

    can you share the approach for C? thanks in advance

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

      it's called brute force approach, guess the solution and submit until AC

      so basically what I did was it must has something to do with prefix sum, so I computed that and may involve prefix cnt(0) so I used that, but couldn't figure out there is length involved so failed to AC.

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

in B is it not optimal to kill the nearest monster?

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

hint for D pls

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

Enjoyable contest. At least I will not come back to pupil ^-^

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

Why so tough time limit in E?

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

    The intended solution is most likely small-to-large merging. It is not uncommon for the centroid decomposition to have a large constant factor.

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

how to approach B?

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

    Loop from the closest monster to the farthest (you need to take only the absolute value of all monster positions and then sort them), but you need to know each monster's health after the sorting, so you need to use something like a vector<pair<int,int>> where the first value is for position and the second value is for the index of that monster corresponding for its health . Now just loop from the closest to the farthest and sum their health and check how many rounds you need to get rid of the current sum, Rounds_required = ceil(current_sum/k).

    If at any time the rounds required are bigger than the current monster position, then we can't kill that monster so break and print no

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

      "it's better to use ( current_sum + k — 1 ) / k for ceiling ". said by LGM

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

        is there a blog post for that? i wanna read more about why that's the case

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

    think binary search on prefix sum

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

.

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

for Problem C why i'm getting an WA : submission

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

    To determine if the answer for a query is yes, you need to the number of non-ones from L to R.

    Instead of sum-cnt*2 > 0, try sum-cnt*2-num_nons (where num_nons is the number of values in the range that is not 1).

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

      After number of non-ones,then what ?

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

        That's it. Just create another prefix array that allows constant time counting of the number of "non-ones" from [L,R].

        It is optimal to set b[i] to 1 when c[i] is not 1, and then set b[i] to 2 when c[i] is 1. If b's sum is too small, then it suffices to increase one b[i] to match c's sum. If b's sum is too large, the answer is "NO".

        What amoad forgot to do was consider all indices where c[i] is not 1, as b[i] would be 1 and therefore part of b's count.

        I hope this explanation makes sense

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

    try this test 1 1 1 1 3 2

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

    for the array 1 1 1 2 2 with query from 1 to 5 ,your code will say yes , while the actual answer is no. got -3 before figured this out finally and had to take a whole different approach

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

Clutched problem C

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

Need More Practice for Educational Rounds. Btw Can anyone tell me the approach for C.(B>C)

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

    we construct "good" array just using 1 (but if there is already 1 in original array we can write 2 instead) then just compare sums between l and r (can be done with prefix sum) and if sum[l:r] of original array is less than "good" array its ans is "NO" else "YES"

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

Very nice problems

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

How to hack others?

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

any hint for problem c????

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

    Basically, if you have $$$1$$$'s in array $$$a$$$, they will be at least $$$2$$$ in array $$$b$$$ and all other elements will be at least $$$1$$$. So, for some $$$l$$$, $$$r$$$ you just need to check if sum on subarray from $$$l$$$ to $$$r$$$ is at least it's length $$$+$$$ amount of $$$1$$$'s in it. $$$l=r$$$ is an edge-case.

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

Typo in problem D's tags: https://imgur.com/TvwOJcP

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

Did anyone recognize C was 1856B

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

    Yes, I solved the question today, but I'm still unable to solve Question C. I attempted to use a segment tree but failed.

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

A: Let L=the minimum position of i such that a[i]==1, R=the maximum position of i such that a[i]==1, the until occurences of 1 become a single block, R-L will decrease 1 if you do operation on position R, otherwise it will not decrease. So the answer is (R-L)-(cnt-1) where cnt is the count of occurences of 1.

B: For each 1<=i<=n we need sum(j:abs(x[j])<=i)(a[i])<=k*i to kill monsters with distance <=i in i turns.

C: If L==R answer is no. Otherwise, for each a[i]==1 we need some j such that a[j]>1 and let a[i]+=1, a[j]-=1. Then we need sum(i:a[i]==1)(1)<=sum(j:a[j]>1)(a[j]-1). We can check this condition in O(1) by prefix sum.

D: Assume slime i is eaten by some slime to the left (the other case is similar), and all slimes used to eat i will form an interval [j, i-1]. So we need to find the maximum j such that sum(j, i-1)>a[i]. If j==i-1, slime i-1 can eat slime i directly. If value of a[j...i-1] is not all the same, then there will be a largest slime which can eat all other slimes in range [j, i-1] then eat slime i. Otherwise, all slimes in [j, i-1] have the same size and cannot eat each other, and slime i-1 is not larger than slime i. So we need to extend this interval to the left to find some k such that a[k]!=a[i-1] (if such k exist).

E: Small-to-large merge. Let dp[u][c]= (the number of nodes v in subtree of u, such that v is color c, and nodes on the path from u to v (except v) are not colot c). Then the number of valid paths with lca=u is sum(v1)(dp[v1][color[u]]) + sum(v1,v2,c)(dp[v1][c]*dp[v2][c]), where v1,v2 iterates over childs of u, c iterates over all colors on subtree of u, and v1<v2, c!=color[u]. The first term means valid paths start from u, and second term means valid paths start and end in subtree of u. To calculate the value we have dp[u][c]=sum(v: child of u)(color[v]==c) (if c!=color[u]), dp[u][color[u]]=1, we can maintain imformation in std::map and merge them small-to-large.

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

    Can you explain what merging small to large means? I had the same dp relation but got TLE on testcase 10.

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      using tmii = map<int, int>;
      
      tmii& dfs(int node,int prev){
      	tmii& mp=*new tmii();
      	for(int next:adj[node]){
      		if(next==prev) continue;
      		tmii& mp2=dfs(next,node);
      		if(mp.size()<mp2.size()) swap(mp,mp2);
      		for(auto [color,cnt]:mp2){
      			if(color!=c[node]) ans+=(ll)mp[color]*cnt;
      			mp[color]+=cnt;
      		}
      		mp2.clear();
      	}
      	ans+=mp[c[node]];
      	mp[c[node]]=1;
      	return mp;
      }
      
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

    Problem E can also be solved with DP on auxiliary trees.

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

    In problem C Why a[i]=1 ?

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

Can anyone please tell me why does this code won't work for problem C :(

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

B >>> D > E > A > C

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

Anyone who got WA on test 2 at problem D, then managed to solve it? What was missing? I did a binary search on prefix sums while checking for the existence of different elements using two segment trees (minimum != maximum). I got WA on test 2, and I couldn't find one where it was not working.

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

    Same here . I had the same approach but WA on test case 2.

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

    You don't just have to check the existence of different elements. If your segment found by binary search contains all equal elements, you will need to extend it until a different element is found.

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

    I found the test I got incorrect on:

    3 
    2 2 1
    

    My program gives 2 -1 -1, it should have been 2, -1, 1. I guess I didn't pay enough attention when implementing.

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

    Let's say we have 3 9 9 9 9 9. We're checking how far right we need to go to eat 3. Simple binary search will result in -1 (no answer for it), because it will first check 3 9s but they're the same so then it will try more than 3 9s, etc. You need to process 1-length case separately.

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

In problem D sample input and ouput it is given in the third testcase that 2 2 3 1 1 will give an output of 2 1 -1 1 2 but cant slime 3 be eaten when 2 eats 2 and then eats 3. Making the expected output 2 1 2 1 2 or am I going wrong somewhere

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

    "A slime can eat its neighbor only if it is strictly bigger than this neighbor. " So 2 can't eat 2.

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

    slime1 can not eat slime2.

    A slime can eat its neighbor only if it is strictly bigger than this neighbor

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

F is beautiful! Too bad I only managed to solve it a few minutes late lol

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

B — Can anyone find out the my mistake Thanks

int main(){

int t; cin>>t;
while(t--){
   ll n,k; cin>>n>>k;
   ll hel[n];
   for(int i=0;i<n;i++){
     cin>>hel[i];
   }

   map<ll,ll> m;
   int mon[n];

   for(int i=0;i<n;i++){
     ll x; cin>>x;
     if(x<0) x=x*-1;
     mon[i]=x;
     m[x]=m[x]+hel[i];
   }

   ll cnt=0;      
   ll p=0;
   int flag=0;
   for(auto &ele:m){
      ll extra=cnt+((ele.first-p)*k);
      if(extra<ele.second){
        flag=1;
        break;
      }
      ll remain=extra-ele.second;
      cnt+=remain;
      p=ele.first;
   }

   if(flag==1) cout<<"NO"<<endl;
   else cout<<"YES"<<endl;
}

}

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

    cnt+=remain; here is your mistake! you shouldn't increase the value of cnt everytime. Rather you have to update the value, as cnt is used here to calculate the remaining time. so it should be: cnt=remain;

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

Can someone hack it? 247947284

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

Edit --> My question was dumb asf. I misunderstood the entire question so resolving now

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

247976858 Can you give me test case wrong ? My program WA on test 2 (Problem D)

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    test:
    	1
    	7
    	1 5 10 4 4 1 1 
    	
    correct output:
    	1 1 -1 1 2 1 2 
    	
    your output:
    	1 1 -1 1 2 3 2 
    
    • »
      »
      »
      9 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! when i revised my code but it's TLE (my code use O(nlog(n)^2)) 247988327

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

        You can use a sparse table instead of segment tree to reduce the time complexity to $$$O(n*logn)$$$.

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

      Your test case really helps, thanks! I realized that with the special case that the neighbor is greater than the current item, it doesn't satisfy the condition for a single binary search anymore.

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

Can anyone find out the my mistake Thanks[submission:247947411]

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

    void solve() {

    ll n, q;
    cin >> n >> q;
    vector<ll>a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<ll>b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        b[i] = a[i] + b[i - 1];
    }
    while (q--) {
        ll l, r;
        cin >> l >> r;
        if (l == r) {
            cout << no << endl;
            continue;
        }
        ll tem = b[r] - b[l - 1];
        ll h = r - l + 1;
        if (tem >= h / 2 + (h - h / 2) * 2) {
            cout << yes << endl;
        }
        else {
            cout << no << endl;
        }
    }

    }

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Test case
»
9 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

COULD YOU MAKE SAMPLES IN TASK C BETTER?

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

I think problem D can be solved using binary search

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

Do anyone know how can my O(n * log(n)^2) solution for problem D got TLE, since n * log(n)^2 is only around 10^8

247977945

Thank you so much

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

can anyone tell me why my code not working problem B?

https://codeforces.me/contest/1923/submission/247969707

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

Hello ,

why i am getting wrong answer on problem B?

https://codeforces.me/contest/1923/submission/247969707

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

    maybe because you sorted cordinate before filling it, not sure about the other things

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

Why does this submission 247963822 fail problem B test 2? Thanks!

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

Why does C have so many hacks?

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

    even tourist got hacked? tf

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

      does anyone know that missing edge case?

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

        I don't think there's an edge case possible for that task? (except L==R which his submission covers). My code is exactly the same as tourists so I'll probably get hacked as well smh

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

          Maybe my view of problem will help you:

          Let's notice, that we can fill "one" to indexes with other elements, and then fit our sum with big numbers to indexes with one.

          a[1 1 1 100 100] -> b[67 67 67 1 1]

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

What is an "easy" solution of problem E? I solved it exactly as this problem.

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

    I also solved it using this idea, some people have solved it using small-to-large merging.

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

    I just saw your comment. I already posted my solution elsewhere but here it is again.

    It consists in one dfs. The idea is to keep track of which colors were accessible before on the dfs tree, with multiplicity. When branching, we set the current color to multiplicity = $$$1$$$ because it then loses its multiplicity (the path needs to be beautiful). But then it needs to regain its old multiplicity $$$+1$$$ when we end the dfs.

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

tourist C hacked

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

D: For each index ,I gonna binary search on the answer. So consider position i, we have to check if after x seconds, we can eat this slime or not.

Im computing the left side first, that mean we considering only from 1 to i-1.

In the position i and after x second, there are two case:

  • All x-1 slimes to the left of it are the same , so the process can make the biggest slime is one of them.
  • Otherwise , the process after x seconds always make one slime that equal to the sum of all x-1 slime to the left of i-th one (this pretty obvious because at any time, you always exist a biggest slimes that near to another), then we just need to check that sum is bigger than size of i-th slimes or not

After finishing the left side, we do the same on the right side and compare the answer 247990076

E : I saw a lot of simpler solution for problem E (merge set/map on tree, etc...). Anyway, I have another technique for E that is "Auxiliary Tree", which was very useful and generic in some specific type of problems. You can find it here : https://codeforces.me/blog/entry/76955. This problem is similar to E, which you can try to solve it first : 613D - Kingdom and its Cities. You can read my solution for E here : 247980215.

Bonus

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

What is the hack on C? Asking for a friend..

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

    There seems to have been some issue with the system (probably related to Polygon), they're rejudged and most of the WA hacks are gone now.

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

Unfortunately, hacks for C were judged incorrectly due to a very peculiar case of UB :(

We are sorry for that, all hacks have been rejudged. The solutions during the contest were judged correctly, so this affected only the hack phase.

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

    Yeah, I was so confused. I literally went through my code a dozen times to see what was wrong. Thanks for the prompt fix.

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

This comment has been deleted.

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

Im not able to understand why im getting wrong answer 2 for problem D,247990642

Could anyone please help!!

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

I wasted 30 minutes in Q2 just because I didn't used int64_t

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

247954847 How this solution is getting TLE?

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

it may not appropriate to write such comment but

There is a case where my code for C is failing, i tried a lot to debug even stress testing but still couldn't found anything! it's failing on token 59831 on testcase 3

i don't know what's minor mistake i'm making 247924659

can anyone help me ?

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

Can someone explain why I got TLE 247937101

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

Approach for solving Problem E using auxillary tree and DP.

Suppose for each color $$$\textbf{c}$$$ we perform a $$$\texttt{dfs}$$$ on the tree and calculate number of nodes in subtree of node-$$$i$$$ of color $$$c$$$ such that none of it's ancestor has color $$$\textbf{c}$$$. Now we divide our answer in two cases:

Case-1: Node-R has color c
Case-2: Node R has color c

But this will take $$$O(n \cdot n)$$$ time. To optimise this, we compress the tree in a way such that we only take nodes of color $$$\textbf{c}$$$ (and some extra nodes less than equal to number of nodes of color $$$c$$$ in number) without losing any information that we could obtain for any node of color $$$\textbf{c}$$$. Now we can use the same logic without any problem.

For each color our complexity would then reduce to $$$O(\text{number of nodes of color c})$$$ (ignoring the extra $$$\log$$$ factor that comes because of $$$\text{lca}$$$ and $$$\textbf{sorting}$$$. Here is my submission for the problem.

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

Спасибо за раунд он мне очень понравился

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

is problem D prefix/suffix sum problem? then using binary search on pref(left), suff(right) then take lower..? but how to handle case where having same size adjacent?

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

    I took care of this case by first going through the whole array and extracting the adjacent subarrays of same values (in the form of a vector of pairs (left index, right index)). Then, when binary searching, I would call the condition not met whenever the currently considered subarray lied in one of the precomputed "adjacent subarrays of same value".

    To handle this with a good complexity, I used another binary search to find the good (left index, right index) candidate with which I should check if I am inside or not. It's like geometry, so maybe there are easier ways to do so.

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

      To make the implementation easier, you could use DP. Define $$$dp[i]$$$ to be the index of the leftmost consecutive identical element that ends at $$$i$$$.

      • If $$$a[i] == a[i - 1]$$$, then $$$dp[i] = dp[i - 1]$$$.
      • If $$$a[i] \neq a[i - 1]$$$, then $$$dp[i] = i$$$.

      Using this DP array, how to check if the range $$$[l, r]$$$ has identical elements? Just check if $$$dp[r] \leq l$$$. If yes, then the range has identical elements.

      Now, you can do a binary search on $$$[0, i - 1]$$$ to figure out the answer.

      Submission

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

Any small counter testcase for my C 1923C - Find B; submission 247973573 as well? I have used all the TCs posted by AVdovin and 29logN

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

I guess we can solve problem F using greedy algorithm with string suffix structures :D

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

https://codeforces.me/contest/1923/problem/C

can anyone tell why my code is wrong...

update: Solved

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

I got a time limit on C even though it passes now :( (barely though) Python always does me dirty like that

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

Hello Everyone, Hope Everybody is doing great. I am stuck at problem C, can someone help me, what's wrong with my code

248047400 this code is after i have take the input array

for(int i=0;i<n;i++) { prefix[i+1]=prefix[i]+a[i]; } while(q--) { ll l,r; cin>>l>>r; ll k=r-l+1; if(k==1) cout<<"NO"<<endl; else { ll sum=k/2+2*((k+1)/2); if(sum<=prefix[r]-prefix[l-1]) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }

According to me it should be correct,but failed at some 58k token.

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

    Can you explain what's the meaning of sum in your code?

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

      Basically sum is the minsum of the array for which good array is possible Suppose pattern {1 1 1 2 2 2} -->3 one and 3 two if we decrease any of the two then it wouldn't be good array and this pattern would be min sum possible for length 6 good array possible

      {1 1 1 2 2} max sum for which good array of length 5 is not possible. {1 1 2 2 2} min sum for which good array of length 5 is possible.

      let say length of array is k then we need min sum of k/2 one's and (k-k/2) two's for array of length k to be good array

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

        An example : 1 1 1 3. It should be "NO" but accroding to your solution your sum = 2 + 2 * 2 is exactly 1 + 1 + 1 + 3. Then you output "YES".

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

    Find possible b's for 1 1 1 1 4 and 1 1 1 2 3 on paper and with your solution

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

247904944 Look at this , my implemetation for 1st problem

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

Why are red coders visible as rated contestants in the final standings?

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

When will rating update

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

is it rating ? my rating stayed the same

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

    It is system testing now. The rating is not calculated yet.

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

      yeah i see

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

      could you tell how much time does it generally take after the completion of the contest? (new comer/ first contest)

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

        For edu rounds, it may last for 2-3 hours(without the 12 hour hacking phase and the preparation). For the normal ones(div.1/div.2), it will be done within about 1 hour.

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

          so once the contest is completed first there will be this hacking phase for about 12 hours and upon completion of that it will require 2-3 hours more right?

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

            Yes. And then you will wait for another 1-2 hours to get your rating changed.

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

I have been a Pupil for ages now. Ya it hurts

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

Video Editorial for problem C : YOUTUBE EDITORIAL LINK Audio : English

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

unrated contest pleaseeeeee!!!!

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

Can anyone give the solution of problem E with simpler explanation ??

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

Where is editorial? The round is already over and even contestants' ratings changes have been published. Round was great but it's cool to see the solutions when you haven't forgotten the tasks yet. Thanks :)

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

Hey folks, can someone please help me figure out why my solution for C fails in the second test case.

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

    use long long int as sum of elements of the array will be greater than the maximum capacity of regular int

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

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

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

Who else failed the system test for problem C because they used 2e5 instead of 3e5 for the array size? (And somehow passed the pretests?)

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

Some printing mistakes in 1923 C ci > 1 is printed as ci > i and last line should be I this sum is less than

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

lovely contest became specialist after a lot of struggle

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

+

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

Hello CodeForces,

I have been marked because my solutions are similar to other people. This is not true and i am expecting that you are gonna change this because that is not true.

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

In problem C, could you please check, why this segment tree approach is failing? code