Hope I can keep my purple!Thanks!

Hope better English comments

Problemset is designed to satisfy participants of all skill levels.

you can make virtual participation later. the problemset is good for all contestants so every one would compite in this kind of rounds , do not worry about rating just enjoy and Good luck for all .. sorry for bad english !

Does anyone ever understand the reason for downvotes on codeforces?

Hope this comment won't get downvoted :)

hoping same just need +31

I think not so.

It is my last round before going to Hangzhou and Shenyang.

dude you don't have to comment the same phrase each contest xD

(score[2] != score[3])

Neither I think.

We are waiting for the onsite participants to be ready to start.

after a while it will be boring to wait until the contest starts! :/

Your rating will not change if you don't send any solution

No need to.

just don't submit anything during the contest and you will be fine.

If you don't submit a solution during the contest your rating won't get affected, so there's no need to unregister.

Never mind, this just resolved.

Hint: If you can solve the problem on tree, edges that create a cycle with that tree can be processed separately (they affect every path the same way)

B
3 3
3 2 1
2 3 1
1 3 2

I hacked B with

2 4

4 3 2 1

4 3 2 1

"long long case" was included in pretests for C?

Not increment or decrement x and y by 1 or -1, but by more at once. For example, always increment it enough to make x == n || x == 0 || y == m || y == 0, which is not that hard to do.

My solution's complexity is O(k) and it's 25 lines long. Is there a shorter slower solution that works?

I did it this way

first see if the array can be sorted without changing in rows -> (change in each line==0||change in each line==2)

then, change each rows with n^2 and check all the same way

this way O(n^3) but n is only up to 20 xd

#include <stdio.h>

int n, m;
int data[30][30];
bool ans;

void change(int a, int b)
{
    int i;
    for(i=0; i<n; i++)
    {
        int tmp;
        tmp=data[i][a];
        data[i][a]=data[i][b];
        data[i][b]=tmp;
    }
}

bool check()
{
    int i, j;
    for(i=0; i<n; i++)
    {
        int cnt=0;
        for(j=0; j<m; j++)
        {
            if(data[i][j]!=j+1) cnt++;
        }
        if(cnt!=0&&cnt!=2) return 0;
    }
    return 1;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    int i, j, k;
    for(i=0; i<n; i++) for(j=0; j<m; j++) scanf("%d", &data[i][j]);

    if(check()) {printf("YES"); return 0;}
    for(i=0; i<m-1; i++) for(j=i+1; j<m; j++)
    {
        change(i, j);
        if(check())
        {
            printf("YES");
            return 0;
        }
        change(i, j);
    }
    printf("NO");
}

OK , so we go.At first you must see that row may be already sorted , it needs one swap , two or more. 1)If some row needs more than two swap , answer is NO as with this operations we can get at max two swaps in one row . 2) if in none of these rows need more than one swap , answer is of course YES , because we don't need to use "column swap" at all .3) We have some rows than need two swap , so it have 3 numbers not in correct place , than we don't need to do about sorted rows , also we don't need to do anything about "one-swap" rows before "column swap" because. and so we have to consider only two-swap rows . It's not hard to see that all different positions for two-swap rows must be at max 4 . and it's the case , than we check all column swap , at most 6 =) hope it helps ! Feel free to ask.

I think you need to transfer in such a way that the largest amount of excess goods is minimized. Consider the case where each town can sell 100 goods. Then for case: 150 150 0 with maximum transfer between any 2 towns=50

You cannot transfer from town 0 to town 1 before transferring it to town 2.

wow!! master

i cant get out of green island xd

Congratulations!! You are still in Div 1!

hmmm , I afraid of that and always I change name of define after changing it's definition. because it's the last thing that we notice it ...

sry for necro-posting but how is this editor/IDE called. Ty in advance

The idea is correct, the implementation is wrong.

Same happened to me (OSX 10.12. Firefox and Chrome)

You have already reported it :D

Well, I don't know about CRT, but if you are looking for a solution based on Number Theory then you can check out mine 21299508

The 4 linear diophantine equations represent the four types of points you get when you expand your rectangle to account for reflections (see this problem's discussion in the blog for further explanation 241C - Mirror Box, it redirects you to this: Codejam problem), and you need the minimum solutions with both x and y positive to find the closest of the points of that type having x == y.

I failed during contest to solve those diophantine equations properly (a, b negative and getting the min x), do you know any other problem where I confirm if now I know how to manage such tricky requirements?? Notice I don't want to practice finding the equations, I just want to test my solver, although the problem being nice/hard is always a plus.

Reflect the box over the top and right sides, with the bottom left corner at (0, 0). So in the 3rd sample, all the boxes have left corners (7x, 4y). Note that the path of the ball is then equivalent to y = x. We can find the stopping point, which is the top right corner of some box, in the form (mk, nl) for some (k, l). It's also on the path, so mk = nl, and the first hit is at (lcm(m, n), lcm(m, n)).

With some experimentation, you can see that for some point (x, y), it's also equal to all the points ( ± x + 2nk,  ± y + 2ml) for some (k, l). (In each box, there's 1 point). And because it's on x = y, we can use the 4 congruences

We find the minimum such a, and check if it's  ≤ lcm(m, n).

Notice that if the greatest letter used is P, then all occurrences of letters 'a', 'b', ..., P-1 and some (possibly all) occurrences of P will be used in the answer. We can find P easily in O(N*ALPHABET_SIZE). Let's insert the positions of letters 'a', 'b', ..., P-1 into a set and then loop over all intervals ([1,M], [2,M+1], ..., [N-M+1,N]). If the current interval [L,R] has no 'a', 'b', ..., or P-1, then we should choose some of the occurrences of P in this interval [L,R] and insert it into the answer. It's easy to see and prove that it's always optimal to take the rightmost one. Everything I explained can be done with set linearly, don't look at my code, please! PLEASE!

Consider the sorted version of the input string. The most crucial observation is that the best answer must be a prefix of this string.

Let's binary search the length of the answer, the only problem is how to check it fast. An useful insight is that any prefix contains every positions of the same character, except one. So the problem reduce to this: Given the picked positions, select some more positions in order to fulfill the requirement, this can be done greedily in O(N).

First notice that if you where to take only the smallest letter, then the solution is the least number of positions with that letter on the string fulfilling the "every m..." condition.

To solve that problem a simple greedy works: go from left to right only taking a position if you passed over m positions without taking any, and take the last you have seen (remember this is only considering the smallest letter ie. 'a' if it existed), if there is no last seen position closer than m to current position then we can't solve it using the lowest letter only.

Now back to the full problem is easy to prove that if we are using >= 2 types of letters is optimum to take all the positions of all but the greatest of the types of letters. Because inserting them before the greatest character makes the solution string smaller.

Full solution is iterate over the greater character c to use and then perform the greedy described but taking all positions of the characters smaller than c.

Link to my solution: 21281704

I solve D with the 2- pointers technique. Fix the m first "window" ( interval from 0 to m-1). It must be covered by any of this characters. Then, we get the most right and most lexicographically smaller character (on position x). When we get this, we repeat the same problem in the (x+1,r+m-1) window. To do this we keep a structure pont[i] that keep the most right position of character i and update this with 2 pointers. After do that we have to add to the solution all character which is lexicographically smaller than your "bigger character". Sorry for my bad english ;/ My solution: 21297160

consider this test:

2
aba

Answer : aa

in line 65 you 'erase' too many positions, and besides you cannot guarantee last will become 0 neither (line 67).

In the example huansuz1 provided you find a problem in position 1 (the one with the b) and it can be fixed, but last would become 1 not 0, and you cannot 'erase' the position 2.

fixed solution: 21301915

My solution is m*n Find all the possible pairs to swap Max 4 elements can be in wrong place For 4 elements in wrong place, there should be only 2 pairs For 3 elements in wrong place there will be 3 pairs For 2 elements in wrong place 1 pair I made all these possible pairs and at last checked if every row gas some common pair then ans is yes else no This solution is of course an overkill. I wrongly computed brute force so wrote this solution

We can model that problem as network flow as follows : create a source node (let's call it 0) and sink node (let's call it n + 1). Then we are asked to find maximum flow in network with edges 0 -> i, cap = p_i for 1 ≤ i ≤ n, i -> n + 1, cap = s_i for 1 ≤ i ≤ n and i -> j, cap = c for 1 ≤ i < j ≤ n (you can't get more than that because of the way network is constructed, you can get exactly this value, because this graph is DAG and you can always push flow in order of topological sorting). We could use any algorithm to find maximum flow, but this graph has O(n²) edges and they will all TLE probably.

But maximum flow is equal by value to minimum cut, which we can actually find in O(n²) time and O(n) memory. Every cut in this network can be expressed as , . Now we can find value of dp[l][k] — minimum total sum of already cut edges if we have taken exactly k vertices into S from vertices 1, ..., l. Then it can be recalculated as follows: dp[0][0] = 0, dp[0][i] = inf if i > 0, dp[l][k + 1] = min(dp[l][k + 1], dp[l - 1][k] + s_l, dp[l][k] = min(dp[l][k], dp[l - 1][k] + p_l + ck (in first case only one edge is cut and this is edge from l to sink, in second case edge 0 -> l is cut and so are edges i -> l for . Of course, we need to keep only last two layers of this dp. Answer is min(dp[n][0], dp[n][1], ..., dp[n][n]).

You have a bug in function next_point. y2 does not initialize. Likely you confused y1 to y2.

ll x2, y2;
if(dir == 1) {
	if(n-x1 > m-y1) {
		x2 = x1 + (m-y1);
		y2 = m;
		dir = 4;
	}
	else {
		x2 = n;
		y2 = y2 + (n-x1); //BUG
		dir = 2;
	}
}

P.S. Sorry for the bad English skills

Its working now!

And then u cheated and you are back.

And now the ratings have been reverted back too. Whats happening?

cuz you must have cheated lol

Because

consider bound as mirror

then every action can be performed on another side.

therefore, all points' coordinates are (x,x) (x )

Make 1 3 2 in every row and swap columns.