All problems were invented by MikeMirzayanov and developed by me, Stepavly, and Supermagzzz.
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int solve(int a, int b) {
int side = min(max(a * 2, b), max(a, b * 2));
return side * side;
}
int main(int argc, char* argv[]) {
int t;
cin >> t;
forn(tt, t) {
int a, b;
cin >> a >> b;
cout << solve(a, b) << endl;
}
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int test;
cin >> test;
for (int tt = 0; tt < test; tt++) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
sort(a.begin(), a.end());
int result = a[n - 1] - a[0];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
result = min(result, a[j] - a[i]);
}
}
cout << result << endl;
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<int> v(n);
int a = 0, b = 0;
for (int &e : v) {
cin >> e;
if (e % 2 == 0) {
a++;
} else {
b++;
}
}
if (a % 2 != b % 2) {
cout << "NO\n";
} else {
if (a % 2 == 0) {
cout << "YES\n";
} else {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (v[i] % 2 != v[j] % 2 && abs(v[i] - v[j]) == 1) {
cout << "YES\n";
return;
}
}
}
cout << "NO\n";
}
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int test;
cin >> test;
for (int tt = 0; tt < test; tt++) {
int n, k;
cin >> n >> k;
int ans = n;
for (int j = 1; j * j <= n; j++) {
if (n % j == 0) {
if (j <= k) {
ans = min(ans, n / j);
}
if (n / j <= k) {
ans = min(ans, j);
}
}
}
cout << ans << endl;
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
bool a[50][50];
int main() {
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char c;
cin >> c;
a[i][j] = c - '0';
}
}
bool ans = true;
for (int i = n - 2; i >= 0; --i) {
for (int j = n - 2; j >= 0; --j) {
if (a[i][j] && !a[i + 1][j] && !a[i][j + 1]) {
ans = false;
}
}
}
cout << (ans ? "YES" : "NO") << endl;
}
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<string> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
string ans = v[0];
for (int j = 0; j < m; j++) {
char save = ans[j];
for (char d = 'a'; d <= 'z'; d++) {
ans[j] = d;
bool flag = true;
for (int z = 0; z < n; z++) {
int cntErrors = 0;
for (int c = 0; c < m; c++) {
if (v[z][c] != ans[c]) {
cntErrors++;
}
}
if (cntErrors > 1) {
flag = false;
break;
}
}
if (flag) {
cout << ans << endl;
return;
}
}
ans[j] = save;
}
cout << "-1" << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int test;
cin >> test;
for (int tt = 0; tt < test; tt++) {
int h, w, a, b;
cin >> h >> w >> a >> b;
if (h * a != w * b) {
cout << "NO" << endl;
continue;
}
vector<vector<int>> result(h, vector<int>(w, 0));
int shift = 0;
for (shift = 1; shift < w; shift++) {
if (shift * h % w == 0) {
break;
}
}
for (int i = 0, dx = 0; i < h; i++, dx += shift) {
for (int j = 0; j < a; j++) {
result[i][(j + dx) % w] = 1;
}
}
cout << "YES" << endl;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cout << result[i][j];
}
cout << endl;
}
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
void solve() {
ll m, n;
cin >> n >> m;
vector<ll> v(n);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (char c : s) {
v[i] *= 2;
v[i] += c - '0';
}
}
ll need = ((1ll << m) - n - 1) / 2 + 1;
ll cur = (1ll << (m - 1)) - 1;
while (true) {
ll left = cur + 1;
bool flag = false;
for (int i = 0; i < n; i++) {
flag |= v[i] == cur;
if (v[i] <= cur) {
left--;
}
}
if (left == need && !flag) {
string s;
for (int i = 0; i < m; i++) {
s += (char)(cur % 2 + '0');
cur /= 2;
}
reverse(s.begin(), s.end());
cout << s << endl;
return;
} else if (left < need) {
cur++;
} else {
cur--;
}
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Video Tutorial for today's G
Really awesome, You try explaining your thought process as well while drafting editorials. Kudos!
He sucks at that.
true still i want him to make one for H
Am I the only one who felt G to be harder than H ??
Can you please explain me H question
great i know the tutorial isnt that great but u r a programmer not youtube ,it takes time don't worry.
Look who's saying
I didnt mean about the content of the tutorial rather the video quality and its editing !! Sry harsh if i hurt u in anyway
oh bhai, majak kar rha tha seriously mat le
Honestly speaking please don't make these videos, these are not helpful.
https://codeforces.me/contest/1360/submission/81283258 why a wrong answer on test case 3??
Try using this block of code... your code is missing the
(i<=k)
conditionI also missed out on this one and got the same 3rd testcase wrong. But I am not able to understand that if I am iterating from
i=2
then if(n%i==0)
then do we need to check that n/i is smaller? I meani
is already smaller and all the 'n/i
's are on the other side of sqrt(n). So, when we getn&i==0 && n/i<=k
we break and print the value ofi
. Is there an example to contradict this? The testcase is on a very large index so it is just ... and I'm not able to see it. Here is my submission : 81251157Try this case :
n = 14 , k = 2
I am sure you will understand why both theif()
conditions are necessary. Also seeing the constraints of the question I would not go for breaking out of loop just for the sake of execution time. Although one small improvement you can do is iterate on the smaller interval of[1,k]
,[1,sqrt(n)]
thanks it helps me too.
you are getting WA in tc3 ?
Yes
same case here
broooo what about this submission? https://codeforces.me/contest/1360/submission/81265491
Instead of above code you should write below one and also start iterating
i
from 1 instead of 2.Also , your code gives ans as n only when
(k==1) or (n is prime)
which is incomplete. Try this case :n = 49 , k = 6
Hey Can you help me with this submission https://codeforces.me/contest/1360/submission/81362630 @darshancool25
What I am doing is, I am creating a 2D array of characters. I am going through each element. If I find a 1 I am checking if the right element or bottom element is 1 or not for cells that are not in the last row or last column. If that is not true I am printing no and breaking out of the loop.
For the cells of last row or last column (i.e r+1==n ||c+1==n) i am just continuing to the next cell I am really stuck with this . please help :)) Thanks in advance
Your logic is correct... basically if there exists a 1 with its right and bottom element both equal to 0 , then ans is NO , else it is YES. I saw your implementation , its a bit complex to understand. Here's my code (I have used same idea as yours!)
@darshancool25 could u plz clarify or explain me that ur solution is of order of n square where n is size of matrix.. how this is working fine for such constraints?
It is clearly mentioned in the question statement that : "The total area of the matrices in all test cases in one test does not exceed 10^5". I hope that answers your question!
why this one is not working for(long long int i=2;i*i<=n&&i<=k;i++) { if(n%i==0) { ans=min(ans,i); if(n/i<=k) ans=min(ans,n/i); // ans=min(ans,n/i); } } if(k>=n) ans=1;
https://codeforces.me/blog/entry/77846?#comment-629110
For problem C case 2, how can we be so certain that we are only looking for one pair with a difference of 1?
A pair with a difference on 1 contains an odd number and an even number. Therefore removing that pair means that both the count of odd values and the count of even values is decreased by 1. We need both the count of odd values and even values to be even numbers (so that we can make pairs). Therefore if the count of odd values and even values are both odd, we can remove 1 pair with difference 1 to make them both even, and then do the rest of the pairing by parity.
We create pair of those numbers with diff 1 and after that we have even $$$e' = e - 1$$$ and $$$o' = o - 1$$$, then it is first case.
Max flow solution for G is easier and more straightforward. 81283859
Did someone else use flows in G xD? https://codeforces.me/contest/1360/submission/81285900
Yes and it's very neat
Bashing a simple problem with an overcomplicated tool is not "neat".
I don't see what's over-complicated but anyway it's just my opinion you know
If you don't see why flow is way more complicated than a cyclical filling pattern, then you're blind.
Replacing thinking ability by direct application of knowledge will be harmful to your long-term progression, especially in the current CP meta.
You didn't get me. I'm not saying my solution is easier than anyone's solution. But it's also not complicated as you're claiming, you just said it was direct application.
Flow is extremly hard to come up by yourself, way more than coming up with an elementary solution to this problem. That's why I say it's an overcomplicated concept for this problem.
Of course, copy-pasting Dinic is easy in itself. Everything is easy to copy-paste. But you're not training yourself to come up with new ideas. That's why I say it's not neat at all.
I was tempted to implement a flow-based solution but I figured that it would take me less time to come up with a "normal" solution than to copy-paste dinic, and I was right.
Also C can be done using the blossom algorithm
Meanwhile can any one explain the flow approach?
"Replacing thinking ability by direct application of knowledge will be harmful to your long-term progression, especially in the current CP meta."
How nicely you explained it! I always think that too. But couldn't come up with nice words like you.
[user:andr0901]Can you pls explain , how did you apply flows in this .... I know max flow algorithn but not able to figure the way to proceed with that
https://codeforces.me/blog/entry/16865 this would help
In G, isn't shifting by $$$a$$$ enough?
Worked for me 81291367
is your code same as this explanation link:stackoverflow, if not could anyone explain what language is used in this and how to solve this using linear programming.
Very neat code. Great!!
can you plz explain!!
Can you please explain after shifting each row by 'a' how are we ending up filling each column by b ones ?
I just put a 1 on the column that has the least 1's without exceeding $$$a$$$ for every row.
Doing that from left to right is the same as shifting by $$$a$$$ the previous row.
Sorry, I didn't answer your question.
In the editorial, we have to find a $$$d$$$ such that $$$(d\cdot n)\%m=0$$$. If $$$a\cdot n=b\cdot m$$$, then $$$b=\frac{a\cdot n}{m}$$$, which makes $$$(a\cdot n)\%m=0$$$
I got it. Thank you.
I really dont understand why any d such that (d*n)%m =0 would work?
i get very confused when working with mods
Yes,that works. 81375672
It was closer to a Div.4 than a Div.3, as far as I think!
Do you mean Div 3.51-3.99
True dat but this was previously a div 4 contest so yay similiraty is not that uncanny !
Video Tutorials for C, D, F, G, H
https://codeforces.me/contest/1360/submission/81263548 why is the ans wrong for test case 3
You are calculating the maximum value of "count", i.e. the maximum number of pairs that are similar because their difference is 1. This value can be even in some cases. You should stop as soon as you find odd number of such cases (might stop simply at 1). So after subtracting "count" (which is odd) from "x" and "y" (which are both odd), the resultant "x" and "y" will be even.
Lets say you have odd no of even no's and odd no's now as soon as you find a pair with diff 1 you can stop counting as in this case count of both even and odd no's will be (as x -y == 1 if x is even and y is odd or vice — versa ) so once you have gotten one such pair the job is done !
https://codeforces.me/contest/1360/submission/81251269 you can check this for reference
Why unnecessary $$$O(n^2)$$$ editorial solution for B? Even the explanation describes a $$$O(n \log n)$$$ solution.
I was also surprised, first they sort and then use O(n^2) complexity for judging all the pairs. xD
After checking their code, I went to check my code again for checking its correctness.
Next time, please mark such contests as Div 4
Totally agreed. Even the last questions were easy go.
can we do problem D using binary search?
can you binary search for factors of a number? not sure if you can
I've noticed that many of the test cases for D — Buying Shovels are just the same two numbers repeated t times. Is there a reason for this ?
It is a prime no. so O(n) solutions with a break statement would fail. A lot of same test cases as a the solution might barely pass on a single test case.
Alternative editorial: https://codeforces.me/blog/entry/77885 by Geothermal
I think there's a O(N*M) solution for problem F (and it works even if we aren't restricted to 26 letters).
Compare every string with the first string:
Commented python solution: https://codeforces.me/contest/1360/submission/81330345
I don't know much syntax in python but it is looking O(N*max(N,M)) to me. But n and m are small so no need to worry. If n>>m then it would cause problem.
Where does your N*N come from?
Diff N-1 strings with the first string, O(M) work per diff, for a total of O((N-1)*M).
If you found any diff with exactly two differences, you generate 2 solutions of length M which needs to be checked with all N strings for a total of O(2*N*M).
So total is something like O(3*N*M)
for comparing every N-1 strings, you call the function twoDiffAnswer. In that function, you run this loop "if all(sum(1 for x, y in zip(w1, w2) if x != y) <= 1 for w2 in A):" which I think runs almost N times.This gives O(N*N) if N>>M. But I am not that much familiar to python so maybe I am incorrect.
The line you quoted is O(N*M), not N.
But it's only ever ran twice (you return the answer after), not N-1 times.
I also found that your solution runtime(108,124,124,139) for first 4 test cases is larger than my solution runtime(30,0,30,30) https://codeforces.me/contest/1360/submission/81312565 which is same as editorial. Can you explain?
Python :(
how did you guys approach, your thought process to find out how to arrange all the one's
In the problem F- Spy strings,
Can we reduce the complexity of O(m * 26 * n * m)? If so, can anyone explain how to do so? Thank you.
I have done it in O(n*m*m). Initialise your answer with the first string and test 'm' versions of this string such that in version 'i', the ith character can be changed. For testing a version of the string, check all the characters except the one that can be changed. If the strings differ in exactly one place, then the ith character can be fixed according to the string it is being tested with. After you have changed the string, all the characters of the string should be tested. You can refer to my Solution
https://codeforces.me/contest/1360/submission/81249769
you can check my submission
Explaination: — Assuming s[0] as an answer now change every letter to a to z and check whether it is possible answer or not
Did in O(T * N * M) https://codeforces.me/contest/1360/submission/81291537
Wow, can you briefly explain?
Lets take two strings a and b , and solve for these two only for now. Lets define getDiff(a,b) = No of positions i in which a[i]!=b[i]. Let currAns = a.
if getDiff(currAns,b)<=1 , then you have found the answer.
else if getDiff(currAns,b) = 2 , then we need to change our currAns
else , we cannot find the answer you can prove that.
Lets modify currAns so that getDiff(currAns,b) <=1. How ? Let a = "abc" and b = "ebd" and currAns=a
We can see that getDiff(currAns,a) = 0 and getDiff(currAns,b) = 2
We have two options to reduce the difference.
One is change currAns[2]=b[2] , then our currAns = abd.
After changing one character we can easily see that getDiff(currAns,a) =1 and getDiff(currAns,b) = 1.
Second way is to change currAns[0]=b[0] , then our currAns = ebc and we can easily see that getDiff(currAns,a) =1 and getDiff(currAns,b) = 1.
I have used this idea to solve for n strings. Since we have proved that for solving for 2 strings we have only two options if getDiff(a,b) = 2 , we can use these answers to check if one of them satisfies all the strings or not else the answer wont exist.
Don't you think Codeforces has decreased the difficulty level of Div3 very much as compared to past contest.Even Question F and G based on implementation.
It is because this contest was previously designed as div4 and later converted to div3
If anyone is interested F-Spy-string Solution with explanation Here
Is there a more generalized solution for problem F? Not that the given solution is bad or anything.
check my submission
In problem G, can anyone explain What is the idea behind choosing d such that 0<d<m such that (d⋅n)%m=0. Please explain.
If we shift d in every row, then total shifts would be n*d. We want these shifts to be cyclic around m. Therefore n*d should be divisible by m, implies (d*n)%m=0.
Why do you even try explaining when you yourself have 0 understanding how it works. Did you even read you own explanation ?
Bi*ch where are the rating changes?
Did anyone try attempting problem E by BFS/DFS? or the trick stuck everyone right at the moment?
yes, i did with dfs. Too dumb to realize that observation
Can I ask how you modified DFS?
Yes, I also solved using DFS. link to solution-81299710
Someone please explain the C problem ,I really dont get the tutorial logic;
The problem wants you to partition the array in pairs. A pair is valid if both of its elements have the same parity. So if you have an even amount of, for example, odd numbers in the array, it means you can already put all of them in pairs. The issue is when the number of elements of the same parity is odd. If that's the case, you would be left with one element unpaired. So the only other way to pair that element, is if there's an element that's also unpaired, from the set of numbers of the other parity.
So at the end, you can partition the array if the amount of odd numbers and even numbers are both even (as you can pair them between themselves), or if both are odd and if you can find a pair of elements of different parity whose difference is 1, making it a valid pair. Those two you choose would be the unpaired ones I mentioned. Also, this means if the number of odd numbers is even, and the number of even numbers is odd, or vice versa, you can't partition the array as you would be left with one unpaired element.
Knowing all of this, approaching the solution is counting the number of even elements and odd ones, and if you have the special case where both quantities are odd, you can easily sort the array and check for adjacent elements if their difference is 1 (as in that case they would have different parity).
I am not able to find why I am getting run time error in test case 5 in problem H. Can someone please help. Link to my solution: https://codeforces.me/contest/1360/submission/81360379
You are using
int
andstoi
.m
can be60
, butint
has only 32 bits.So, you can see
stoi
throwing an instance of 'std::out_of_range'You should use
long long
andstoll
insteadThanks man!! that was so dumb of me.. got AC now!!.. Cheers
Your solution is really good and informative.!
thanks buddy
rating +300, LOL.
My solution for problem H in contest:
Realize that there's NO DIFFERENCE deleting TOO SMALL/BIG numbers and SMALL/BIG ENOUGH numbers. Just make [2^(m-1)-128,2^(m-1)+127] in a container, and delete numbers, output mid.
https://codeforces.me/contest/1360/submission/81278827
And another elegant solution. https://codeforces.me/contest/1360/submission/81358112
Could anyone explain "Binary Median" editorial ,i did not get how to proceed with this problem?
At the start, without removing any binary number, the median is 2^(m-1).
Then for each string removed:
If it is smaller than the current median, the median either goes up by 1 (if there is an even number of numbers left) or it stays the same (if there is an odd number of numbers left).
If it is more than the current median, the median either goes down by 1 (if there is an odd number of numbers left) or it stays the same (if there is an even number of numbers).
Note that you need to skip over all strings which have already been removed when you are going up or down by 1.
Here's my submission if you need it: 81298077.
what if it's the same element ??????
Then it depends on whether the current list has an odd or even number of elements.
For example:
[1,2,3,4,5] and you remove 3 (which is the median). The remaining list is [1,2,3,4] and the median is 2 which means the median goes down by 1.
[1,2,3,4] and you remove 2 (current median). The list is [1,3,4] and the median goes up by 1.
what if there are no elements left to go down in case of moving down or vice versa for moving up ??
There should always be space to move up or down. (at least I have not had any trouble with this problem)
why am i failing TC3 for https://codeforces.me/contest/1360/submission/81295890
Can anyone please tell me why my solution 81366886 is getting TLE on TC5?
I wanted to share my solution for G as my approach was a little different from editorial's and is easier to think and implement. I decided to iterate over columns from 1 to m and put b 1s greedily based on the number of 1s in each row. For that, I used a set of pairs {number of ones in this row, row number}. So for each column, just put 1s on the intersection of that column with the b rows with minimum number of 1s that is, first b rows in the set (and update set after putting each 1). And then check for the validity of solution by counting number of 1s in every row and column. 81293437
https://codeforces.me/contest/1360/submission/81366312
Why am I getting TLE for this approach, please help me I have just started ! P.s: Problem is D
And I really didn't understand the editorial for D !
You are iterating for 1 to k linearly and k can be as large as 1e9. You can perform upto around 1e8 iterations in 1 second time limit. That is why time limit is exceeded. Find a way to find divisors of n in less than linear time. See editorial for that.
For today's G there is a pretty simple and nice-looking solution. Check it here: 81371851
it's awesome, but why?
update:
understand, first n * a == m * b, that is count of '1', we can know that fact:
n * a >= m and n * a mod m = 0 and n * a / m = b.
make n * a divide by m, exactly perm b block, each block have m count of '1', distribute them by index [0, m — 1]. finally we get each index in [0, m — 1] count b times(for column).
for row, distribute n * a by divide a, also get index in [0, n — 1] count a times.
can someone help me in this for problem D. It is giving wrong answer on tc 3. https://codeforces.me/contest/1360/submission/81375221
thanks
You should put in if condition if (a%i==0 && i<=k) { ans=min(ans,a/i); if (a%(a/i)==0 && a/i<=k) ans=min(ans,a/(a/i) ) }
I can't understand your second condition
I was emailed about the violation that my solution 81275866 for the problem 1360F significantly coincides with solutions anishde85/81257823, ycui11/81275866, keep__calm/81282151. After I take a look at details, I found the only thing we are in commons is we used a template for FastIO to read input faster, and the template is used from the previous submmisoin, which the author published under contest blog, is it considered as a violation? Thanks! MikeMirzayanov
atcually, it was fastIO is from PyRival https://gist.github.com/ShubhamKJha/f16f5eb7e6da41da5f4b95d004b55d6e
Can someone explain how you can notice the solution for G?
First you must look whether answer is YES/NO. This can be easily be checked if a*n == b*m.
Now as you have asked how to notice the pattern , let me explain my thought process in approaching the answer.
First check on most basic cases. Ex. n=2, m=2, a=1, b=1. You may easily visualize it as a 2X2 matrix which has all the elements along main diagonal = 1 and rest = 0.
Now try a=2, b=2. When you check such 3 to 4 basic cases you will start finding a pattern.
So rather than trying to find answer for some random cases try building it step by step, you will figure out the way. This is not just an answer to a particular question, but rather applies to a variety of problems that require keen observation skills.
I hope this is what you wanted.
Thanks. I guess that's basically what I did, but I found the wrong pattern so I messed up :3.
please can you explain why we have to find 0<d<m such that (d*n)%m = 0
You forgot the -1 in the initial value of the median in problem H (the implementation has it).
Can someone explain that d*n%m condition geometrically or algebrically. I have no idea how that works
Can somebody please tell how to solve F without the brute force approach ?
The last problem H can be solved even in more easier way than the explained method in the editorial. First calculate the index using the formula (2^m-n-1)/2. Then check all the numbers which are to be deleted and maintain a cnt and prvCnt variable, where cnt is incremented when there exists some number in the deleted list which is less than the index, then set prvCnt = cnt. If at any stage cnt-prvCnt == 0, break the loop and there you go, you got the answer. At last just convert the decimal number to binary. https://codeforces.me/contest/1360/my
Wrong link kid.
https://ideone.com/eHsbhj refer to this then
I don't want to refer.
Why are you always rude and mostly make hate comments?
this tutorial for problem G, no mathematical explanation, suck.
My Solution for problem H. I think it's more clean. 81425658
An easier to think of solution for G is instead of doing the cyclic shift, simply take the first a columns with the smallest number of ones, and add ones to those in the next row. Code is here: https://codeforces.me/contest/1360/submission/81428756
It's a lot slower, but it still manages to fit within the time limit
Editorial of problem G doesn't make sense to me. Can anyone help me ? why cyclically shifted by d works?
In the matrix you can change the order of rows and columns, it is still valid. Which means order does not matter, we just have to distribute the 1 somewhat evenly.
I have similar solution to that of editorial.We have to first check if $$$a.n=b.m$$$ . If it holds we can construct the solution in following way : in first row fill '$$$a$$$' number of 1's . In second row start from a+1 column and fill '$$$a$$$' number of 1's and so on (if anytime position reaches beyond $$$m$$$ , change it to 1) . Since $$$b.m$$$ is divisible by $$$m$$$ , thus 1's are evenly distributed across all the columns. submission
i am not getting why we start to fill the next row with a+1 column
It's a constructive algorithm. By doing the method i have described we can equally distribute $$$1$$$'s in all columns .
Can somebody help, why this is failing in test 2? Submission: 81434111
You are only trying the largest factor <= sqrt(n) and n/largest_factor. So, you missed some factors.
Wrong Test Case: 1 36 4
Your Output: 36
Correct Output: 9 (9*4=36)
Yes, I rectified it some seconds ago and resubmitted with the submission 81439111, still it failed the same case.
Ah. I found the problem. On line 30: "else if( k >= p ){" where p is the smallest factor larger than or equal to sqrt(n). But, k can be larger than one of the factors which is larger than p.
For example: 1 36 18
Your code: p=6, k>=p is true, print 6
Correct answer: 2 (2*18=36)
A solution: Try all factors between 1 and sqrt(n) and their inversions. O(sqrt(n)) is good enough.
What's wrong with this solution for H:
Let $$$f_i=0$$$ if $$$i \in A$$$ else $$$f_i=1$$$. Let $$$b=\left\lceil\frac{2^m-n}{2}\right\rceil$$$. Then use binary searching to find the first $$$x < 2^{m}$$$ that $$$\sum_{i=0}^{x}f(x) = b$$$. Then $$$x$$$ is the result.
Can somebody help me with my solution to problem E?? my solution E
please make your array char and add this to if
P.S Do not forget a[i][j]=='1' not a[i][j] = 1
Why does the array needs to be of char type??
as you can see, the input numbers are not divided. if you write cin >> a[i][j], the compiler will not take only one number, he will take number before space or enter. just try to output your array.
Thanks i got it !^_^
or you can write like
Problem C:
Note that if the parities of e and of o do not equal, then the answer does not exist.
Given that n is always even, it is impossible.
In Honest Coach editorial i think that this code block is not necessary.
Since we've sorted the vector. When we slice it in the i'th position, maximum of left array would be (i-1)'th element and minimum of right array would be i'th element so that doing it in one iteration is enough.
Please correct me if i'm wrong
In Problem H, why does the approach below Doesn't work?
Approach:- We Need to find the median (let's call that median X, basically X=
floor((k-1)/2)
) from the K remaining strings.Since the numbers(binary strings) from
0 to 2^m
are lexicographically sorted, removing given n given strings, should not disturb the lexicographical order of the strings.Our Answer Would be Xth number, but since we have removed some numbers( n numbers/strings), From all those n numbers, we will find numbers which are smaller than X, therefore we need to increase X, by all the smaller numbers we encounter, and increase X ... until there are no smaller numbers are left.
And return the updated X to be our final answer.
My Code : 81399744
I am not able to understand can you explain again, why are we increasing X if a[i] <= X and what if we delete median itself ?
In the solution of G, why there are always $$$b$$$ ones in every column when the solution exists?
For a matrix of size $$$h * w$$$, let's represent the total number of ones in each column as a frequency array $$$F$$$ of length $$$w$$$ initially filled with zeros and for each time we place a 1 in the $$$i-th$$$ row and the $$$j-th$$$ column we increment $$$F[j]$$$, and let's periodically fill this array as the solution states, for example let $$$h = 4, w = 4, a = 2, b = 2$$$,
Iteration 1: $$$F = {1, 1, 0, 0}$$$ filling the first two columns in the 1st row
Iteration 2: $$$F = {1, 1, 1, 1}$$$ filling the second two columns in the 2nd row
Iteration 3: $$$F = {2, 2, 1, 1}$$$ filling the first two columns in the 3rd row
Iteration 4: $$$F = {2, 2, 2, 2}$$$ filling the second two columns in the 4th row
If a solution exists for a matrix of size $$$h * w$$$, we know for a fact that $$$h * a = b * w$$$. Observe from the example above that the total number of times we iterate $$$F$$$ (the number of times we iterated all $$$w$$$ elements of $$$F$$$) is equal to the total number of ones we have to place in the matrix divided by the size of $$$F$$$ which is equal to $$$(h * a) / w = b$$$, therefore, after we're done filling the matrix we know that for all $$$ (1 <= i <= w)$$$ $$$F[i] = b$$$
No offense but I wanted a proof, not an example.
I guess that is because if we sort the column numbers where we put ones in ascending order we will have m*b consecutive numbers, then we take $$$\bmod m$$$ and what we should have is the pattern $$$0,1,...,m-1$$$, b times.
Why (d⋅n)%m=0 tho , If anyone can explain than it would be of great help
Can someone explain editorial's construction for G. Basically I want to know how the following ensures the condition given in question:
And how does one come up with this idea.. why shifting by such a $$$d$$$ always ensure the condition in question?
I have the exact same doubt. I will try asking the contest setters in pm and let you know if they respond. Meanwhile please let me know if you get the answer :)
Yes I got some partial intuition in this regard. Consider that we fill in the manner described in tutorial, shifting that number $$$d$$$ to the right each time we enter next row. So in tutorial we are already filling $$$a$$$ ones in each row, so the only thing we need to worry about is that all columns are getting $$$b$$$ or equal number of ones.
Now the thing is that if we distribute the block of ones evenly, then each row will must have $$$b$$$ ones because $$$na = mb$$$.
So now we worry about the amount $$$d$$$ by which we shift. Following $$$0$$$ indexing, if first row has no shift, then our filling is done evenly iff the $$$n$$$th or one past the last row also starts its filling with no shift, right? So that means total shift is $$$nd$$$ and that must be multiple of $$$m$$$ (Why? because of the above line.)
The only other condition we must worry about is that $$$d \not\equiv 0 (\mod m)$$$ because in that case you keep filling the same columns!
I didn't understood your third paragraph, "that if first row has no shift, then our filling is done evenly iff the nth or one past the last row also starts its filling with no shift"
Consider this:
And this
yes, now i got it.thank you man
Explanation for tutorial of G. A/B matrix
Let we fill the first 'a' one's in first row then fill the second row by shifting the first row cyclically and so on. Let the shift be d. Then as there are n rows total number of shifts will be (n*d) as we have to fill the one's evenly number of shifts has to be distributed evenly among all 'm' columns (Imagine equal distibution of (n*d) sweets among 'm' children).It means that (n*d)%m should be zero. We can find d and build the matrix;
Small remark regarding G. As we have $$$n a = m b$$$ we can take $$$d = a$$$.
Though I still don't understand why the described tiling is correct.
I think this will help : https://codeforces.me/blog/entry/77846?#comment-760270
I personally found problem G's editorial hard to understand, and I thought it could be helpful for others if i shared my understanding.
First things first, notice that the number of $$$1$$$'s in the rows must be equal to the number of $$$1$$$'s in the columns. This means $$$n \times a = m \times b\;$$$. If this doesn't hold for given $$$n,m,a,b$$$ , the answer is
NO
. Otherwise, it can be shown that the answer is alwaysYES
. From now on, I am going to use zero-based indexing.We can follow a greedy algorithm :
In this way, we know that every row has exactly $$$a$$$ cells with $$$1$$$'s. The first condition is fulfilled.
Now it remains to check if we have $$$b\;\;1$$$'s filled for every column. Now when we fill the rows this way, notice the pattern of filling the columns :
First, we fill columns $$$0$$$ to $$$a-1$$$ for the first row , and then we fill columns $$$a$$$ to $$$2a-1$$$ for the second row and so on , and before ever going back to column number $$$0$$$ we fill the column $$$m-1$$$. We start again from column $$$0$$$ and keep doing the same thing until we fill $$$n \times a\;1$$$'s. The final filling sequence of columns looks like this :
$$$0,1,2,...,m-1,0,1,2,...,m-1,0,1,2,...,m-1,...,m-1$$$.
The sequence must finish at column $$$m-1$$$ because there is no remainder when $$$n \times a$$$ is divided by $$$m$$$. Since all the columns appear in the same frequency ,the sequence also shows that every column has exactly $$$\frac{n \times a}{m} = b\;\;1$$$'s filled.
I hope it helps.
it helped a lot...thanx.. your solution show that d=a for ever..why in editorial he didnot show that??
``
Proof for why the answer will always exist in Problem G when $$$a.n=b.m$$$
Denote $$$cnt_j$$$ as the sum of ones in $$$j^{th}$$$ column. Now, lets assume that each row contains $$$a$$$ ones. And now lets prove that when we are in some row and $$$cnt_j>b$$$ for some $$$j^{th}$$$ column, then there exists some column $$$k$$$ for which $$$cnt_k<b$$$ as well as cell is $$$0$$$ in the same row in this column.
Now, lets prove this by contradiction. There will be $$$m-a$$$ zeroes in that row and for each such column lets assume that count of ones in that column is at least $$$b$$$. So, there will be $$$(m-a).b$$$ ones in those columns which is equal to $$$n.a - b.a$$$ because $$$a.n=b.m$$$. Now, let's assume there are $$$k$$$ ones in the remaining columns, so $$$k=b.a$$$ as total ones are $$$n.a$$$. So, these remaining columns will contain $$$b$$$ ones each which contradicts our condition that one of these columns contain more than $$$b$$$ ones. So, the above statement must be true.
So the following algorithm works to solve the problem
Assign first $$$a$$$ cells equal $$$1$$$ for each row. Now, traverse the matrix row by row. While in some row, if at some columns the count of that columns is more than $$$b$$$ and that cell equals $$$1$$$, then find some cell in that same row where count of ones in column corresponding to that cell is less than $$$b$$$ and cell is equal to $$$0$$$, then swap them. Do this for all cells of matrix.
Probably nobody cares by now, but the editorial for G has a mistake. Choosing any $$$d$$$ such that $$$0 < d < m$$$ and $$$m | (d\cdot n)$$$ won't work in general. Indeed, it's easy to see that it doesn't work if $$$n, m, a, b, d$$$ are $$$15, 30, 2, 1, 6$$$ respectively.
However, any such $$$d$$$ such that $$$d | a$$$, will work.
The given solution works because it ends up choosing the minimum $$$d$$$, and the minimum $$$d$$$ will divide $$$a$$$.
I haven't yet figured out whether these are the only values of $$$d$$$ that will work.
Edit: In fact, if $$$0 < d < m$$$ and $$$m | (d\cdot n)$$$, then $$$d$$$ works iff $$$\gcd(d, m) | a$$$.