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

Автор awoo, история, 34 часа назад, По-русски

Neapolis University Pafos

Привет, Codeforces!

Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со стипендиями JetBrains. Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с учебной программой прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно!

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

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

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

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

Данный раунд частично пересекается по задачам с Внутривузовской олимпиадой Саратовского ГУ. Если вы участвовали в этом соревновании, то воздержитесь от участия в раунде.

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

Наши друзья из Neapolis University Pafos также хотят передать вам сообщение:

Прием на бакалавриат по программе "Компьютерные науки и искусственный интеллект" в Neapolis University Pafos открыт!

JetBrains Foundation поддерживает эту программу бакалавриата и предоставляет 15 полных стипендий для самых талантливых абитуриентов. Стипендия покрывает стоимость обучения, проживание, медицинскую страховку, визовые сборы и карманные деньги (300 евро в месяц).

Узнать больше →

Первая волна набора:

  • Срок подачи заявок – до 23 апреля 2025 года
  • Вступительный тест – 27 апреля 2025 года
  • Проголосовать: нравится
  • +98
  • Проголосовать: не нравится

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

Hope we'll find a variety of topics in this round rather than only maths or bitmasking type problems.

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

Hope that we'll find a variety of topics in this round rather than only maths or bitmasking type problems.

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

I wish we could have a

^-^

Edit : Why does it always happen when I wish for something not to?

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

lets see if -100+ is possible or not

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

score distribution?

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

Sacrificed my sleep for +9 in last div 2 hoping to get it in this round

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

Hope to enjoy this round without any technical issues. Because, the calendar has a less number of rated scheduled contests this month.

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

Why adamant about not keeping educational rounds on saturday sundays

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

watch me win in this contest...

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

Why this post has less up votes??

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

I really hope enjoy this round without the server acting unstable for no reason

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

best of luck coders!

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

bruh my alarm didn't ring

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

    I literally registered for this contest seeing that one of my friend has already solved problem A in 2 minutes and started this contest like 5 minute late

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

Yesss, finally, I will be back to CYAN today, inshaAllah! Scored 'C' just 13 minutes before the ending! It took me 3 unsuccessful submissions and a long time to realize that 'B' was that much easy!

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

    what was the approach for 3rd bro i tried but failed

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

      Bro, we need to choose a pair every time ensuring their "SUM" is at least 'N'. When this "AT LEAST" thing come to your mind, this is something "BINARY SEARCH". At the same time, you need to make it optimize that how many such index exists for the current index that if you form a pair their "SUM" will be at least 'N'. Then, when this "HOW MANY THING" come to your mind you need to sort the given array and use "PREFIX/ POSTFIX" sum array to optimize the counting approach using "BINARY SEARCH".

      One important point, if the value of an index is 'N', then make it 'N-1' before processing. Because, we need to make 'N' by taking at least 2 indices.

      Now, you can see my submission to align this approach in a better way. (I named the array preSum. It's actually postSum.)

      • »
        »
        »
        »
        6 часов назад, # ^ |
          Проголосовать: нравится -14 Проголосовать: не нравится
        /**
         * author: vanshgambhir
        **/
        #include<bits/stdc++.h>
        #define ll long long
        #define vi(n) vector<int> v(n);
        #define loop(i, n) for (int i = 0; i < n; ++i)
        #define all(v) v.begin(),v.end()
        using namespace std;
        void solve(){
        		ll n,m;
        		cin>>n>>m;
        		vector<ll> v(m);
        		loop(i,m) cin>>v[i];
        		sort(v.begin(),v.end());
        		vector<ll> suff(m);
        		suff[m-1]=v[m-1];
        		ll tot=0;
        		for(int i=m-2;i>=0;i--){
        			suff[i]=v[i]+suff[i+1];
        		}
        		for(int i=0;i<m;i++){
        			ll mini=v[i];
        			ll maxiIdx=lower_bound(v.begin()+i+1,v.end(),n-mini)-v.begin();
        			if(maxiIdx>=m) continue;
        			ll maxi=suff[maxiIdx];
        			ll cnt=m-maxiIdx;
        			tot+=maxi+(mini-n+1)*cnt;
        		}
        		cout<<tot*2<<endl;
        	}
        int main() {
        	ios_base::sync_with_stdio(0); 
            cin.tie(0); 
            cout.tie(0);
        	int t;
        	cin>>t;
        	while(t--){
        		solve();
        	 }
            return 0;
        }

        actually i tried but can't figure out what's wrong in this

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

wtf was B

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

How to solve E

P.S. C << B

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

any hint to solve b?

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

    handle k is equal to 1 case explicitly otherwise it's just summation of maximum k+1 elements from the array

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

      Oh wow

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

      intuition ? excuse me?

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

        it is pretty simple like if k==1 you can take one element which can be any and you have to take at least one last end element you can take both as well otherwise for k is greater than one try to make segments you will always be able to cover all the k+1 greater elements

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

        If $$$k > 1$$$, consider the array's largest $$$k + 1$$$ elements : $$$G = g_1, g_2, ..., g_{k + 1}$$$.

        Let the $$$g_i$$$ that appears first in the array (smallest index in $$$a$$$) be $$$g'$$$ and the one that appears the last be $$$g"$$$. Now we can choose the last value as any $$$g_i$$$ between $$$g'$$$ and $$$g"$$$ and initial $$$k$$$ values as the remaining values in $$$G$$$. Then we can color the chosen ones as red initially and start moving inwards from $$$g'$$$ and $$$g"$$$ and reach all $$$k + 1$$$ elements $$$g_i$$$ and can finish at any one of them, so that the last value that is added is also one of the $$$g_i$$$. Thus sum of values of $$$\sum_{i = 1}^{i = k + 1} g_i$$$

        If $$$k == 1$$$ you have only two elements, if you choose them to be the largest two, you cannot always color such that the last element is one of them, eg. [1, 5, 6, 2]. In those cases answer is $$$max(a_{max} + a[0], a_{max} + a[n - 1])$$$

        If $$$k == 1$$$ and max element is at one of the ends, answer is $$$a[0] + a[1]$$$ if a is sorted in descending order

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

      omg, I'm gonna kill myself. I thought about that, but I didn't consider k = 1, and get wa

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

        did you try c?

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

          yeah. Actually C was easier than B

          • »
            »
            »
            »
            »
            »
            6 часов назад, # ^ |
              Проголосовать: нравится -9 Проголосовать: не нравится
            /**
             * author: vanshgambhir
            **/
            #include<bits/stdc++.h>
            #define ll long long
            #define vi(n) vector<int> v(n);
            #define loop(i, n) for (int i = 0; i < n; ++i)
            #define all(v) v.begin(),v.end()
            using namespace std;
            void solve(){
            		ll n,m;
            		cin>>n>>m;
            		vector<ll> v(m);
            		loop(i,m) cin>>v[i];
            		sort(v.begin(),v.end());
            		vector<ll> suff(m);
            		suff[m-1]=v[m-1];
            		ll tot=0;
            		for(int i=m-2;i>=0;i--){
            			suff[i]=v[i]+suff[i+1];
            		}
            		for(int i=0;i<m;i++){
            			ll mini=v[i];
            			ll maxiIdx=lower_bound(v.begin()+i+1,v.end(),n-mini)-v.begin();
            			if(maxiIdx>=m) continue;
            			ll maxi=suff[maxiIdx];
            			ll cnt=m-maxiIdx;
            			tot+=(((maxi+mini*cnt)-(n*cnt))+cnt);
            		}
            		cout<<tot*2<<endl;
            	}
            int main() {
            	ios_base::sync_with_stdio(0); 
                cin.tie(0); 
                cout.tie(0);
            	int t;
            	cin>>t;
            	while(t--){
            		solve();
            	 }
                return 0;
            }

            can you tell me what is wrong in this code? i am confused

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

      Although this might be the solution, my approach was slightly different. To make the i-th element (i > 0 && i < n — 1) the final cell to be painted blue, there must be at least one blue cell to its left and one blue cell to its right. For i = 0 and i = n — 1, the answer is just a[i] + sum of k maximum numbers in the remaining array.

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

      how ? if n=7 and k=4 array=7 1 3 1 10 12 14 ans is 44 or 46 ?

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

        It's 46 choose 4 elements as 7 10 12 14 and consider last element as 3

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

          but 3 is not neighbour of any blue element

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

            Like consider making 1 blur first which is adjacent to 7 then make the right side elements of 3 blue then make 3 blue and that way 3 is last element

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

      WHAT? i thought there some kind of 2d dp...

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

why cant I submit solution now that contest is over

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

is there any smarter way of doing 2F without some cosmic-tier binary search/sweep line jank

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

    I think divide and conquer works.

    For each $$$i$$$, we find optimal $$$j$$$. Let $$$solve(l,r,a,b)$$$ mean that we are solving $$$l...r$$$ and their optimal $$$j$$$ are in $$$[a,b]$$$. Then, find the optimal $$$x$$$ for the index $$$mid$$$ and call $$$solve(l,mid-1,a,x)$$$ and $$$solve(mid+1,r,x,b)$$$.

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

    Actually the sweep line is not that complicated, you just have to notice that the best endpoints are $$$l,r$$$ such that $$$a[l]$$$ is the unique minimum of its prefix and $$$a[r]$$$ is the unique maximum of its suffix (in this problem it really helps visualizing the array as points in 2D).

    And now the candidates for $$$l$$$ and $$$r$$$ are decreasing sequences, because of that, for each element, the endpoints that it appears in are a range of each sequence (i.e. the 2D conditions are now easier 1D conditions).

    And then you do the sweep line of the biggest range intersection of the second sequence given that only pairs of ranges that contain me in the first sequence are alive.

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

Panicforces.

WA multiple times, I'm cooked.

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

Could you please give me an explaination why problem B can be solved in $$$\mathcal O(n\log n)$$$ easily but $$$n\le 5000$$$?

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

    two pointers on 2D prefsums

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

    Misdirection

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

      is this really allowed in pB? I have just known that pA could (and should) be have smaller constraints.

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

    there are two cases

    when k=1: you will take any element, and take max of first and last if available.
    Logic: As you have can only paint in one direction, you can only take max of first or last element

    when k>1: you will just have to take sum of k+1 max elements in array!
    Logic: Fix range to minimum and maximum index of k+1 max elements

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

    I solved it in O(N * K) because it was the only solution I could think of. I think they keep this time limit because it's Div2 B.

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

Is "D" Bruteforce?

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

    same question, I thought of bf but have no time to implement.

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

    Yes, try every possible subset for $$$x$$$ and $$$y$$$ which are disjoint and reduces $$$x$$$ and $$$y$$$ to the same value.

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

why does my D solution is wrong recursive dp + bits 311139765

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

Good C and D :)

The only unpleasant part is B, the too many "Announcement" are misleading and interferin :(

And hope the samples can be stronger.

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


    #include <bits/stdc++.h> using namespace std; #define ll long long int main() { ll a = 1000000007; int test; cin >> test; while(test--){ ll n,k; // map<ll,ll>mp; cin >> n >> k; vector<ll>vec; ll maxele = 0; ll sum = 0; for(ll i=0;i<k;i++){ ll x; cin >>x; vec.push_back(x); maxele = max(maxele,x); } vector<ll>ct(200000+1,0),pfx(200000+1,0); for(ll i=0;i<k;i++){ ct[vec[i]] += 1; } // ele greater than or equal to this val ll ways = 0; pfx[ct.size() - 1] = ct[ct.size() - 1]; for(ll i=ct.size() - 2;i >= 1;i--){ pfx[i] = pfx[i+1] + ct[i]; // mp[pfx[i]] += 1; } for(ll i=1;i<=(n/2);i++){ // cout << ways << endl; ll val1 = i; ll val2 = n - i; if(i < (n - i)){ ll x = pfx[n-i]; ll y = pfx[i]; // cout << x << " " << y << endl; ways += 2 * ((x) * (x-1)); ways += 2 * (x * (y-x)); } else{ ll x = pfx[i]; ways += (x * (x-1)); } } cout << ways << endl; } }

    why is time limit exceeding in my solution ????

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

      vector ct(200000 + 1, 0), pfx(200000 + 1, 0);

      You create two vectors, ct and pfx every time. If operations iterate over these vectors t times, the total number of operations can reach around 4e9 ((2e5 + 2e5) * 1e4), which can easily exceed the time limit.

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

Is there a reason why all of these submissions are the same for problem E? Either someone has several alts, or serious cheating is happening...

22R01A05B8 kushwahaarpit360123 vinay_m18

with several more (usually unrated or newbies).

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

    Livestream on YT and link to telegram group with solutions A-E :/

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

    sadly there exist multiple telegram groups sharing solutions to rounds, most of these cheaters just copy the code from these groups

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

    ALL leaked solution :> (src -yt)

    Leaked D solution
    Leaked C solution
    Leaked E solution
    • »
      »
      »
      5 часов назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Rajkumar_24M11MC100 this cheater has same codes, nigga is so dumb didnt even think for a second before copy pasting the code lol. also look at his prev contests he has 0/1 submissions.

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

Problem B be like:

"Your first solution must be the sum of first $$$k+1$$$ maximum elements and you shall figure out the correct solution afterwards when you've already got a wrong submission"

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

Good contest, quite interesting problems.

  • A: decent number theory problem
  • B: the corner case was non obvious and I spent 1 WA and about 10 minutes to figure it out.
  • C: cute 2 pointers problem, when you need to move pointers in opposite directions (at first I was moving them in the same direction and couldn't find an error for a while lol)
  • D: have no idea why my 3d dp was not working. I thought I got this problem, but no. Better luck next time

Overall, not so bad of an Edu round. B was very educational lol.

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

    How to solve B problem? IDEA please

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

    D doesn't need any DP. I solved D with DFS, I try to guess the answer never greater than 100000. And it worked! :) :) :)

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

      DFS is dp actually

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

        No, I just used DFS to run out a answer map in home and submit. $$$O(T\times\log^2_2\max(x,y))$$$.

        Check my code to see my strange solution :)

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

      Is this based on the fact that the first 15 bits are enough since sum of first 15 nat nums is 120 = 60 * 2 ?
      Edit :- Ok, that would tle

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

    can you tell how you solved C

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

    C 2 pointer trap can be avoided with binary search. I was lucky to choose BS instead of 2 pointer (for real)

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

    there is nothing wrong with 3d dp . if you look other submissions , from msbs , why to only have equal reductions . That is underfit , u may even not be able to make things equal ofc excluding( u can make both as zeros which is not optimal alwys)

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

    BTW , you were very close .

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

      I've just fixed my dp. Now it TLs lol, so I should probably think of another approach

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

        Ohh overflow tle?

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

          Daamn, I didn't think about precalculating. In this problem, it is a must. Also, I couldn't figure the error about properly computing cost of making both numbers 0 during the contest.

          Indeed, an educational content here.

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

            if we have to make x and y equal and they are not zero when made equal , msb1 , msb2 as to go to some common msb (reductions are msb1 — msb , msb2 — msb). but when they are zero that they do not have to be some common msb like 2^(-1) or 2^(-2) . one can have msb of 2^(-1) x is 0 , other can have 2^(-2) y is 0 .

            e.g. 2 3

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

such a bullshit B

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

Top 7 all from Japan :D

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

dumbest contest ive ever participated in. gl CM :(

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

Such a bullshit B

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

    I really liked B tho

    maybe I'm picking a side here because this contest is my best one yet

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

I tried solving problem D by finding the longest common prefix in the binary representation of x and y. This helped me determine the highest power of 2^k that divides each of them, which I called d1 and d2. Then, I used a DP approach with a state dp[d1][d2][60], where I tried to form two disjoint sets contributing to the smallest cost. However, I’m getting WA on test 2. Can anyone help me figure out the issue? Thanks!

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

CornerCaseForces

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

I am so dumb I should leave CP ATP

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

ALL leaked solution :> (src -yt)

Leaked D solution
Leaked C solution
Leaked E solution
»
6 часов назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится
»
6 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem C's testcase maybe so water

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

while there is at least one red element, you have to select any red element with a blue neighbor and make it blue.

should have made "any red element" bold

i request awoo and coordinators to please highlight/bold important informations in problem statements for any upcoming contests

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

nice round i was 1 line from getting ac on B but its great to make sure that my code works with the corner cases next time

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

It's really really bad EDU, A is very bad, B > C and B's first test not a useful test. Make a good problem or don't make but give a useful test case LOL, B's test case always pass !!

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

    I understand that B could be trivial, but how is A bad?

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

      A is too much straightforward, in my opinion. We don't see this much straightforward As anymore. That's why I guess

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

      A is not like div2As, but I solved it easily :) but fr it's only implementation I think, no need to think :(

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

any hint for $$$D$$$?

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

the closest to returning to blue, if I could realize x and y can shift same number in D and didn't write continue to avoid it

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

Please someone tell me how to solve c in a simple way. Please....

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

    Look at my solution. You know that you only need to pick two colors and paint the planks such that starting few planks have same color of first type, while the rest have the same color of second type. Now, fix the number of planks having the type of first color and then check for the possible number of ways to select colors for the second type to paint rest of the planks. Now, suppose that you can color i planks with color-1 and j planks with color-2. Now, it's only possible when a[color-1] >= i and a[color-2] >= j, which is the number of colors which can color at least i and at least j planks, respectively. Hence, total number of ways will be (number of colors having a[x] >= i) * (number of colors having a[x] >= j). But doing so, you're taking such indices for which color-1 and color-2 are same, so you need to subtract such cases. Just visualize it, the number of such cases will be the minimum of (number of colors having a[x] >= i, number of colors having a[x] >= j).

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

      bro, you have the best and the simplest solution I have seen so far. even the o3mini has complex solution which was written by all of my friends !

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

    Essentially, you want $$$\sum_{l = 1}^{N - 1} c(l)$$$ where $$$c(l)$$$ is the number of paint combinations where the length of first paint's continuous colored planks is $$$l$$$

    Let the number of paints with capacity $$$ \geq k$$$ be $$$g(k)$$$. We can pre-compute $$$g_i$$$ for $$$i = 1$$$ to $$$n$$$ in $$$O(m)$$$ time by storing frequencies of each paint

    Now it is easy to calculate $$$c(l)$$$ if you know number of paints with capacity $$$ \geq l$$$ and number of paints with capacity $$$\geq n - l$$$. Let the smaller quantity out of $$$l$$$ and $$$n - l$$$ be $$$l$$$. Then,

    $$$c(l) = g(n - l) * (g(l) - 1)$$$, i.e. choose any paint with capacity $$$\geq n - l$$$ and choose any other paint with capacity $$$\geq l$$$ except the paint chosen for $$$n - l$$$ length

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

I don't seem to properly understand C. As a trivial/slow solution, I would apply the colors to the fence s.t. all of color i is on the left, and all of color j in on the right, and do this for all i and j. This only works if a[i] + a[j] >= n, and if so there should be a[i] + a[j] — n + 1 ways to do this, as seen in the sample testcases. We can express this as the following line of python:

res = sum(a + b - n + 1 for i, a in enumerate(l) for j, b in enumerate(l) if i != j and a + b >= n)

But even this slow solution fails on many testcases in test 2 by printing a too high answer, for example this one:

l = [5, 6, 3, 4, 3, 7, 7, 4]

gives the answer 210, but the actual answer from the judge is 182. Can someone help me understand where my error is?

Edit: n = 7 in the example

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

For B***

Sum of first K + 1 elements is correct but,

(what if k == 1, suppose the maximum is at any index != 0 and != n — 1 then we will always take the boundary elements of array, aka the last blue box)

:)

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

Are you guys able to see the standings

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

DPforces

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

i think b is pretty hard for b of div2

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

Can someone please explain D, without magically defining DP.

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

Never felt so stupid solving B... Implemented maps, vector of pairs, custom sorts...just to be solved by k=1 explicit case.

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

My Submission

Can anyone tell my why my submission gave WA? I sorted the input then for each index i, I tried to find index ind such that for every j greater than ind, arr_i + arr_j >= n. Then I used prefix sum to find the sum between [a_ind, a_(m-1)] and used remaining indexes, r = m-ind and used the ans line. Basically used a_i + a_j - n + 1 for every pair from ind to the end. Ignore the cout lines, I used them to try to debug but couldn't find any. Thank you in advance.

Update: I found the problem. I didn't consider the case where a_i = n and also there was a signed overflow in the ans line.

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

Here is a different approach for C no problem https://codeforces.me/contest/2075/submission/311149194