Finally getting specialist!...Thanks for the round! :)

There is some issue with the editorials. Supermagzzz pls check.

Editorial is not perfect. please look into it and upload all c++ solutions with proper explanations.

What happened to the editorial?

Why are people upvoting this blog?? The tutorial is not visible and for c++ code, you can check the submission of any lgm

The tutorials aren't visible.

You can read this article to read editorials now.

Write a new blog on CF (you don't have to post it), add a line [tutorial: <problem id>] (e.g. [tutorial: 1336A]), and preview it.

My solution to problem G:
The main observation is that we don't ever need to use more than 2 teleportations (because going from point $$$a -> b$$$ and then from $$$b -> c$$$ is strictly worse than going directly from $$$a -> c$$$). Therefore, we can calculate for each portal the cost required to use it as the first one, which is $$$dist(start, portal) * w + a[i][j]$$$ and in similar way the cost to go from a portal to the end as $$$dist(portal, end) * w + a[i][j]$$$ (by using bfs). The solution is either $$$dist[start][end] * w$$$ or the smallest cost to access a portal from the start plus the smallest cost to go from a portal to the end.
Code : https://codeforces.com/contest/1520/submission/115344755.

Can we solve E with ternary search?

$$$F2$$$ and $$$G$$$ has the same codes.

Problem E has issues in solution code.

problem D was directly available here

My DP solution for E: we can find all pref[i] values where pref[i] shows how many moves we need to move all sheep to the left from i to i. If a sheep doesn't stay at i position, then pref[i] = pref[i — 1] + was ( was is an amount of sheep to the left from i), else pref[i] = pref[i — 1]. Same operations we can do for suff (we go from n to 1). Then we can simply check for every i: ans = min(ans, pref[i] + suff[i + 1]).

Can someone hack the F2 solutions which are very nearer to time limit 4000 ms. Even my upsolved solution is very close to 4 sec.

Why does my solution to 1520E - Arranging The Sheep gives WA? I did it like this:

Thanks if someone had the goodwill to read :)

In C, I just printed odd numbers first and then the even numbers row-wise, I thought this would be the intended solution.

Submission 115253830

Could someone give a proof (or hint) about the correctness of this simple problem E solution? I solved it during contest based on intuition, but struggle to give a formal reasoning. The solution differs from the one given by the editoral. Any help is appreciated.

Idea:

1. discard all leading and trailing empty spaces

2. initialise $$$ans=0$$$

3. for each remaining empty space at position $$$i$$$, increment $$$ans$$$ by $$$min(sheeps_l, sheeps_r)$$$ where $$$sheeps_l$$$ is the number of sheeps appears before position $$$i$$$, $$$sheeps_r$$$ is the number of sheeps appears after position $$$i$$$

interactive problem in cf == Binary Search

Finally i'll get 1600+ rating :)

Weird solution for "1520A — Do Not Be Distracted!" in Editorial.

Isn't this solution much faster and simpler?

const set = new Set();
let flag = true;
for (let i=0; i<tasks.length; i++) {
	if (set.has(tasks[i]) && tasks[i-1] !== tasks[i]) {
		flag = false;
		break;
	}
 
	set.add(tasks[i]);
}

return flag ? 'YES' : 'NO';

Let's understand what the maximum number of vertices can be in the tree. We will consider each level separately. If the level number x is less than logt≤14, then we can spend no more than x of vertices (since there are simply no more vertices). If the level number is from 15 to 18, then we can spend no more than t vertices, so each request uses only one vertex per level. By limiting the number of vertices in this way, we get that there are no more than 214−1+4⋅104=56383, which fits into the constraints.

Can anyone explain these lines from the last paragraph of Tutorial of F2 more clearly?

In editorial of F2 it should be $$$2^{14}$$$ instead of $$$2^14$$$.

To correct it the editorialist should put 14 between {}, thats how the syntax works

Solutions for A-C

Solution of Problem D

Best solution + Explanation for Problem F1

G can be solved with dp?

weak test cases in d

Can I use Dijkstra to solve G?

There is a LaTeX problem in the tutorial for F2, $$$2^{14}$$$ is mistyped as $$$2^1 4$$$ and confused me a bit at first.

1520G - To Go Or Not To Go? solution using Dijkstra's is giving WA on test 2; PLEASE HELP

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define deb(x) cout << #x << " = "<< x << endl
#define pb push_back
//=====================
using pii = pair<int,pair<int,int>>;
using pi = pair<int,int>;
const int MAXX = 1e18;
void solve() // simple dijktra's Algorithm
{
    int n,m, w;
    cin >> n >> m >> w;
    vector<vector<int>> a(n, vector<int>(n)); // stores original matrix
    for (int i = 0; i < n; ++i)
    {
    	for (int j = 0; j < m; ++j)
    	{
    		cin >>  a[i][j];
    	}
    }
   	vector<vector<vector<pii>>> adj(n, vector<vector<pii>>(n,std::vector<pii>(n)));  // adjacency matrix
    vector<vector<int>> d(n,vector<int>(n,MAXX)); // distance vector
    vector<pair<int,pair<int,int>>> v; //stores all portals
    vector<vector<int>> neighbours = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    d[0][0] = 0;
    for (int i = 0; i < n; ++i)
    {
    	for (int j = 0; j < m; ++j)
    	{
    		if(a[i][j] == 0)
    		{
    			for(auto nbr : neighbours)
    			{
    				int x = i + nbr[0];
    				int y = j + nbr[1];
    				if (x >= n || y >= m || x < 0 || y < 0 || a[x][y] == -1)
    				{
    					continue;
    				}
    				adj[i][j].pb({w,{x,y}});
    			}
    		}
    		else if(a[i][j] != -1)
    		{
    			for(auto nbr : neighbours)
    			{
    				int x = i + nbr[0];
    				int y = j + nbr[1];
    				if (x >= n || y >= m || x < 0 || y < 0 || a[x][y] == -1)
    				{
    					continue;
    				}
    				adj[i][j].pb({w,{x,y}});
    			}
    			v.pb({a[i][j], {i,j}});
    		}
    	}
    }
    for (int i = 0; i < v.size(); ++i)
    {
    	for (int j = 0; j < v.size(); ++j)
    	{
    		if(j != i )
    		{
    			pair<int,int> temp1 = v[i].second;
    			int weight1 = v[i].first;
    			pair<int,int> temp2 = v[j].second;
    			int weight2 = v[j].first;
    			adj[temp1.first][temp1.second].pb({weight2 + weight1, {temp2.first, temp2.second}});
    		}
    	}
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0,{0,0}});
    while(!q.empty())
    {
    	int v_x = q.top().second.first;
    	int v_y = q.top().second.second;
    	int d_v = q.top().first;
    	q.pop();
    	if(d_v != d[v_x][v_y])
    		continue;
    	for(auto ad : adj[v_x][v_y])
    	{
    		int to_x =  ad.second.first;
    		int to_y = ad.second.second;
    		int len = ad.first;

    		if(d[v_x][v_y] + len < d[to_x][to_y])
    		{
    			  d[to_x][to_y] = d[v_x][v_y] + len;
    			  q.push({d[to_x][to_y], ad.second});
    		}
    	}
    }
    if(d[m-1][n-1] == MAXX)
    {
    	cout << -1 << endl;
    	return;
    }
    cout << d[m-1][n-1] << endl;
}

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

    solve();
    
    return 0;
}

Is the solution only given in C++ ? If no, when will Java solutions be uploaded ?

Does the round became unrated or what?

Nice

Can anyone tell why this code is giving TLE on test 125?

For C, my approach was to print consecutive numbers in alternate boxes. I am not sure why this fails, I tried testing my approach by verifying that no 2 adjacent squares have adjacent numbers too.

Here's the code: 115288339

Can someone please explain Guess the K'th zero solution hard version using binary search.

I understood if i internally initially check the positions of last zero then second last zero and so on upto 1st zero then i can know the all initial positions of all zeros and map the positions e.g. first zero at 2 index and 5th at 9th index

But after giving the answer for first query how to modify the answer of other queries without using segment tree or BIT.

In problem E:

Note that in the optimal solution the sheep with the number $$$m = \lceil\frac{n}{2}\rceil$$$ will not make moves.

Shouldn't $$$m = \lceil\frac{k}{2}\rceil$$$?

for problem C , i have different approach, (accepted)

https://codeforces.com/contest/1520/submission/115286972

i am filling cells diagonal wise. first main diagonal then alternate diagnol

Problem D Video Tutorial link : https://youtu.be/7IRsFvqgWlw

The option to submit file is not showing. I want to solve those probems which i couldn't do yesterday. When will that option be back? anyone knows it?

Wanna share my miserable experience during the contest...

During the last 30 min, the queue is too long, I submitted G, but knew the result after the contest ended, so I don't have chance to debug and resubmit!

What a pity:<

In F2 many people have used ordered_set, order_of_key.

Can someone tell the functionality of this, or some source maybe. Thanks.

My solution for C was, if n != 2, print in appropriate way all odd numbers from 1 to n^2 and afterwards all even numbers.

More easy to implement & understand, I think.

where is my points???

Please can anyone can explain problem e?Thanks in advance.

A relatively easier approach for problem C (Not Adjacent Matrix):

At first, we try to fill the array with odd elements starting from 1 till n², then we fill the remaining cells with even elements starting from 2 till n². The only exception is when n is 2.

For reference, here is the link to my submission.

I think problem C can be easily solved by just simply printing the odd numbers till n*n and then the even numbers. For example, if n=4

1 3 5 7
9 11 13 15
2 4 6 8
10 12 14 16

Would anyone mind explaining E tutorial again to me? I've been trying for a while but I still didn't get the formula for the final position of the sheep

Does anyone else thinks editorial for problem F2 has not been explained properly ? Comments have better explanation than that. Could someone explain the editorial of F2 ?

Nice round ! Thanks for the problems !

Alternate solution for F-hard if anyone is interested:

Divide the array into blocks of size $$$20$$$. As a preprocess, store the number of zeros in all these blocks. It takes $$$200000/20==10000$$$ queries.

Now, we can answer each query: find the block where the zero is, and use $$$\lceil \log 20 \rceil == 5 $$$ per query to binary search this block.

In total, we use exactly $$$60000$$$ questions in worst case.

115436756 code with some comments

I can propose a simpler solution for the C (Not Adjacent Matrix) Question

we can just print all the odds or all the even first until they are greater than n^2 . Then after all those are printed we can just print the rest odd or even numbers.

Implementation is as follows:

include<bits/stdc++.h>

using namespace std; void solve() { int n ; cin>>n;

if(n == 1)
{
    cout<<1<<endl;
    return;
}
if(n == 2)
{
    cout<< -1 <<endl;
    return;
}
int odd = 1;
int even = 2 , evenc = 0;

for(int i = 0 ; i < n ;i++)
{
    for(int j = 0 ;j<n ;j++)
    {
        if(evenc<(n*n)/2)
        {
            cout<<even<<" ";
            even+=2;
            evenc+=1;
        }
        else
        {
            cout<<odd<<" ";
            odd+=2;
        }
    }
    cout<<endl;
}

}

int main(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif

ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto start1=high_resolution_clock::now();
//solve();
test(solve);

auto stop1=high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
    //cerr<<"Time: "<<duration.count() / 1000.0<<endl;
    cout<<endl<<endl<<endl<<"Time: "<<duration.count()/1000.0<<endl;
#endif

}

So if you like the solution then please star this comment.

Can someone explain why in problem E, not moving the middle sheep and moving other sheep towards it is the optimal solution?

Hi, guys! Trying to solve F2 with multiset. I have WA on 9 test. My someone help to find the mistake please? https://codeforces.com/contest/1520/submission/115447429 (Very simple code)

weak pretests in G if you intended to make the dijkstra solution get TLE.

In problem C, it's enough to randomize the position of each number until a valid matrix is found. There's a small probability of generating an invalid matrix.

Editorial is awesome and very clear thank you

There is an block solution for F2.

Let $$$w$$$ be the block size, it will interact $$$\frac n w + t\cdot\lceil \log_2 w\rceil$$$, with $$$w=8$$$, it will interact not more than 55000 times

Uses BIT for prefix sum between blocks, the time comlecity is $$$O(n \log n + t \log^2 n)$$$

115414141

solution using Dijkstra's is Runtime error on test 146 ; PLEASE HELP

my submission : https://codeforces.com/contest/1520/submission/115467140

Can someone explain me this part of code. Prob : F2

void dec(int pos, int L, int R) {
    cache[{L, R}]--;

    if (L != R) {
        int M = (L + R) / 2;
        if (pos <= M)
            dec(pos, L, M);
        else
            dec(pos, M + 1, R);
    }
}

115471003

Problem F-2

I can't figure out why it is wrong. It gets wrong at test case 7, can you especially explain that? Because when I try, it seems fine!

In F2, what does "In this task, the interactor is not adaptive. This means that within the same test, the hidden array and the queries do not change." mean? Are we supposed to keep track of the changes in the array ourselves, because the interactor will continue to answer according to old values?

My submission for Problem E 115482300

Basic approach is:

` Count Total Stars`
` Iterate through string {`
`    if(starsTillNow <= (totalStars / 2)) {`
`            if(c == '*') starsTillNow++;`
`            elsesteps += starsTillNow;`
`        }`
`        else {`
`            if(c == '.') dotsTillNow++;`
`            else steps += dotsTillNow;`
`        }`
` }`

In problem G:

Here is link to my AC solution.

Here is link to my WA on test case 122 solution, it's exactly similar to previous solution, only difference is value of LINF as LONG_MAX.

Can anyone explain, why this error is caused????

Can someone please clarify, that in (QUESTION E) are we assuming that the count of sheeps will always be odd, then only we can have one middle sheep, or else there will be two. The test cases passed with this assumption but i cannot see anywhere specified that number of '*' is odd. should i have known this just by reading the question or am i missing something.

Please see my solution for E: Arranging The Sheep 115496010 ``

• Why is it WA can anybody tell me ?
• I found the center of mass of all the sheep, on that position will be the center sheep in the final arrangement and accordingly place half sheep to left and half sheep to right. then count number of spaces each sheep is from the center of mass and add them together Is my approach wrong?

Why the code following cannot accept...

Problem B

115509456

I did not get the logic of 4th problem. Can anyone explain?

Problem F2, Does anyone have any way to show that there are no more than 6*10^4 vertices?

why this code is giving the wrong answer.

include<bits/stdc++.h>

using namespace std; bool a[26],res; int main() { int t; cin>>t; while(t--) { int n; string s; cin>>n>>s;

for(int i=0;i<n;i++)
   {
      a[i]=false;
   }
   bool res=true;
   for( int i=0;i<n;i++)
   {
      int t=s[i]-'A';
      if(!a[t])
       { 
          a[t]=true;

        }
      else if(s[i]^s[i-1])
        {
          res=false;

          break;
        }


   }
   if(res)
   {
      cout<<"YES"<<endl;
   }
   else
   {
      cout<<"NO"<<endl;
   }

}

}