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

How can we do D with disjoint set union?( As it was tagged in the problem page)

One of the best editorials I've seen in the contest I registered In!

Why brute force on E1. Rotate Columns (easy version) doesn't work? My implementation

When n <= m i get the max of each column, then i sort in increasing order, and sum up the last n values. When m < n i just brute force every possible shift of each column.

Nice problems : )

I don't get D. Could anyone explain more about it,please? Thanks in advance

In $$$B$$$, I think the smallest time unit to which we must process is $$$120-1+max(b_i-a_i)$$$ (which is at most $$$123$$$).

Should the complexity of problem F be $$$O(m \log m \cdot 10)$$$?

Can someone explain a solution for G1? (Maybe a different method as compared to editorial)

What the minimum number of columns we need to check in E? I think i have proof of 1/4 * n.

In problem C) Paint the digits, it says in the condition that *) Each digit is painted either with color 1 or color 2. And in the last second line, it also says that "It is allowed that either of the two colors is not used at all". Can someone explain the significance of this line?

My alternate solution for E1. Observe that if n is less than equal to 3, you can just pick the 3 maximum elements. Otherwise if it is four, observe that all the selected elements must lie in the top four in their initial row. So lets take all the 16C4 elements and check for validity on each. The maximum that we get now is the answer.

I used DSU to solve G1, though this technique won't work on G2 because of update queries,

For every number in the input, maintain a map for the first occurrence and last occurrence, map<ll, ll> start and end.

start[a[i]] => starting index of a[i]
end[a[i]] => last index of a[i]

now take two temp variables, temp_start and temp_end initialized it with,

temp_start = start[a[0]]
temp_end = end[a[0]]

now, iterate throughout the input list and keep expanding the temp_end if a new element is found within the previous range (temp_start, temp_end), else if the next element is outside the range, reinitialize the temp variables,
like,

temp_start = start[a[i]]
temp_end = end[a[i]]

finally, for each disjoint set, sort the number of occurrence of each number and counted n — 1 number. (convert n — 1 numbers to the most occurring nth number)

https://codeforces.me/contest/1209/submission/60579121

In C you can sort the numbers and try to add numbers greedily.

can someone explain more explicitly solution outlined for E1?? Thanks in advance.

Задачу С можно решить по-другому. Идём по массиву справа налево и ищем, поддерживая минимум на суффиксе, последний элемент, который больше какого-то элемента справа. Если его нет — массив отсортирован и вывести все единицы. Если есть — это начало последовательности 2-ек, все элементы слева можно сделать — 1-цы. А дальше идём от него по массиву, поддерживая последний элемент 2-ек (x), и данное число 2-ка, если >= x и 1-ца иначе. А потом проверяем ответ на корректность.

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, list(input())))
    q1, min1 = n, float('inf')
    for q in range(n-1, -1, -1):
        if a[q] > min1:
            q1 = q
        else:
            min1 = a[q]
    if q1 == n:
        print('1'*n)
    else:
        s, last = [1]*q1, a[q1]
        s.append(2)
        d1, d2 = a[:q1], [a[q1]]
        for q in range(q1+1, n):
            if a[q] >= last:
                s.append(2)
                d2.append(a[q])
                last = a[q]
            else:
                s.append(1)
                d1.append(a[q])
        d1 += d2
        for q in range(1, n):
            if d1[q] < d1[q-1]:
                print('-')
                break
        else:
            print(''.join(list(map(str, s))))

In problem C,"a[i]<=9" is very important.Sadly,I didn't pay attention to it.So I kept thinking of a way of O(n)(Here) ,but I didn't finish it during the contest.I only solved 2 problems...

We can solve E2 in $$$O(2^n*n^2)$$$.

Code

What is the concept behind using string suffix structures in Problem D?

Can someone explain E1 and E2 in a better way didn't get the editorial

i tried D (div2)/ cow and snacks with this approach https://codeforces.me/contest/1209/submission/60608611

what i did is made the vector pair of the favourite snacks of each person( where min(xi,yi) always the first element of each pair) then did sorting on the vector pair after that traversed once from front to count sad people with help of visited array( marked the snacks which are already eaten ) and did same thing from back and took the minimum of the both

please help me out in this

not able to understand the tutorial for the problem c...completely stuck!..please help anyone:(

I don't get G. What's the meaning of 'blocking is "+= 1 on segment"'?

I didn't get the editorial of problem B completely. Could anyone explain why there is also a "pre-period" of 5?

tbh, I cant get G2. Could anyone explain it in detail?

Can anyone explain me C solution?

I got AC with a simpler solution for E1 here: 60699383.

The idea comes from the maximum sum would be if you take the 4 maximum elements in the matrix, but you wouldn't always be able to take the maximum 4 elements such as a case like this:

2 2
100 1
100 100
1 1
1 100

Through trial and error I thought that the number of collisions like these that might force me into taking a smaller element would be low, I stored the indices of the columns in which the 8 maximum elements appear and I bruteforce all possible shifts through these columns. I even tried storing the indices of columns for the 5 maximum elements and it got AC here: 60700309.

If someone could provide a proof for this solution or a counter example, it would be appreciated. :)

I can't get H :( Could anyone explain it please?

Why in problem F, in the second test case, the answer for city 3 is 12 instead of 1.

12 implies 1 -> 2 -> 3 then it costs 123

1 implies 1 -> 3 then it costs 13

I think I don't understand this problem. If someone can explain to me what I am not understanding, I would appreciate it.

any o(N) solution for problem c?

I tried to implement problem D using bfs but I keep getting TLE on case 23. Can somebody help me with this? Here's my code: https://codeforces.me/contest/1209/submission/60944190.

In my opinion, E1 is hardest part of E2 problem lol..I managed to solve the E2 part on my on (bound on columns that matter), but I still dont understand E1 dp.

Trying to understand the G2 tutorial right now, but I don't get what the statement "blocking is segment +=1" means, would appreciate some help!

I was solving the problem E1 using simple DP, for each i from 1 to col, find the the max answer(col containing the maximum values for each row) which we will get after all possible rotation of ith column, i got WA. The part which is missing in my solution is, i am always doing this in a order of 1 to m, whereas in the editorial they are using mask for the order. I am unable to think of a counter example for my solution. WHY DO WE NEED MASK? WHY CAN'T WE JUST SOLVE IT GOING FROM COLUMN 1 TO m? please help.

Problem D using DSU:

Maintain a deque of pair of snacks, for printing optimal answer. Consider each disjoint set as those snacks which are already being eaten. Now consider ith favourites (0<i<=k) snacks say, 'u' and 'v'. Now 2 cases arise:

Case 1: If both u and v belong to the same set, then this implies that both of the snacks have already been eaten earlier, and if we were to make this cow happy, then we would be making atleast 1 previous cow sad. So its optimal to make this cow sad instead, increment sad_count. And put this u & v, in back of the deque.

Case 2: If u and v belong to different sets, then this implies that both of the snacks had been eaten but never were pairwise favorites of any previous cow. So its optimal to let current cow eat both snacks, and merge the sets. Merging two sets implies that previous cows which had eaten two snacks in prevous sets, are now eating atleast 1 cows (In fact those eating u and v, are eating exactly 1 snack, still happy). This way we make no cow sad, so push u & v in front of deque.

Now iterating from front to last in deque, is the optimal way to eat the snacks.

Submission

Why the complexity on E1 is O(((3^n)+(2^n)*(n^2))*m)? :(

Is that editorial of E1E2 even an explanation lol, see so many people feeling confused, me too

Editorial should contain implementation of problems.

G2 can also be solved in $$$O((n + q)\sqrt{(n + q)})$$$ but the implementation will likely be cancerous.

249975135

Hey, can someone help me with test case 4?

Consider $$$n=4$$$. What I did is just take $$$x_{1}, x_{2}$$$ contigous numbers from 2 columns, and shift them to get the desired result. So, $$$x_{1}=1,2$$$, and correspondingly, $$$x_{2}=3,2$$$. This is just one case. We can take numbers from 3 columns, and get $$${x_{1},x_{2},x_{3}}$$$={$$$1,1,2$$$}, $$${x_{1},x_{2},x_{3}}$$$={$$$1,2,1$$$}, and $$${x_{1},x_{2},x_{3}}$$$={$$$2,1,1$$$}. Seeing the number of cases to be small, I just bruteforced over the number of integers $$$p$$$, such that I choose $$$p$$$ columns, and take $$$x_{i}$$$ many contigous values from column $$$i$$$.

#include <bits/stdc++.h>
using namespace std;
#define int int64_t

int32_t main(){
        ios::sync_with_stdio(0), cin.tie(0);

        #ifndef ONLINE_JUDGE
        freopen("inp.txt","r",stdin);
        freopen("out.txt","w",stdout);
        #endif

        int _test;
        cin>>_test;
        while(_test--){
                int n, m, ans=0;
                cin>>n>>m;
                vector<vector<int>> a(n,vector<int>(m)), d(n+1,vector<int>(m));
                for(int i=0; i<n; ++i){
                        for(int j=0; j<m; ++j){
                                cin>>a[i][j];
                        }
                }
                for(int t=1; t<=n; ++t){  //  length
                        for(int j=0; j<m; ++j){  //  column
                                for(int i=0; i<n; ++i){  //  starting point
                                        int sum=0;
                                        for(int z=0; z<t; ++z){  
                                                sum+=a[(i+z)%n][j];
                                        }
                                        d[t][j]=max(d[t][j],sum);
                                }
                        }
                }
                // bruteforce over combinations of sum n
                // taking 1 column
                for(int j=0; j<m; ++j){
                        ans=max(ans,d[n][j]);
                }
                // taking 2 columns
                for(int i=0; i<m; ++i){
                        for(int j=i+1; j<m; ++j){
                                if(n==2){
                                        ans=max(ans,d[1][i]+d[1][j]);
                                }else if(n==3){
                                        ans=max(ans,d[1][i]+d[2][j]);
                                        ans=max(ans,d[2][i]+d[1][j]);
                                }else if(n==4){
                                        ans=max(ans,d[1][i]+d[3][j]);
                                        ans=max(ans,d[3][i]+d[1][j]);
                                        ans=max(ans,d[2][i]+d[2][j]);
                                }
                        }
                }
                // taking 3 columns
                for(int i=0; i<m; ++i){
                        for(int j=i+1; j<m; ++j){
                                for(int k=j+1; k<m; ++k){
                                        if(n==3){
                                                ans=max(ans,d[1][i]+d[1][j]+d[1][k]);
                                        }else if(n==4){
                                                ans=max(ans,d[1][i]+d[1][j]+d[2][k]);
                                                ans=max(ans,d[1][i]+d[2][j]+d[1][k]);
                                                ans=max(ans,d[2][i]+d[1][j]+d[1][k]);
                                        }
                                }
                        }
                }
                if(m>=n){
                        vector<int> lst;
                        for(int i=0; i<m; ++i){
                                lst.push_back(d[1][i]);
                        }
                        sort(lst.rbegin(),lst.rend());
                        int np=0;
                        for(int i=0; i<n; ++i){
                                np+=lst[i];
                        }
                        ans=max(ans,np);
                }
                cout<<ans<<'\n';

        }
        return 0;
}