Hello Codeforces!

On February 16, 18:05 MSK Educational Codeforces Round 38 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for Div. 2**. It will be held on extented ACM ICPC rules. After the end of the contest you will have **12 hours** to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were prepared by Ivan BledDest Androsov, Sahand Xahandd Alitanloo and me.

Thanks Mike MikeMirzayanov Mirzayanov for great system Polygon!

Good luck to all participants!

**UPD:** Since there will be another Div. 2 contest soon, the hacking phase will be shorter (only 12 hours). Before CF Round 464 we will actualize the registrations in such a way that Div. 2 will be officially registered, and Div. 1 participants — unofficially.

**UPD2:** We also have a message from our partners Harbour.Space:

We are excited to announce that some of the world’s strongest teams will come to our Hello India x Russia Programming Bootcamp: MIPT and all top India’s Universities that qualified to the World Finals!

As always, the boot camp isn’t only about the training — we’re in the process of getting renowned keynote speakers from all over the globe to come and speak about life and all the opportunities at your fingertips after ACM-ICPC.

We look forward to seeing you all there this spring! For those of you who haven't registered, there's still time.

If you have any questions we can help you with, please connect with us:

Phone number: +34 674 291 422 Email Address: hello@harbour.space

**UPD3:** Editorial is published

sooo fast people, wait we're still in a contest

lol

Imagine if we have rated contest every day! That actually happened for three days. Actually four(Saturday contest)

Score distribution?

Will be announced later as usual.

but when "later" is?

UPD: Educational round!! nileshjha19

Educational round. ACM ICPC style. All problems have same value.

Hat-trick of Rated Contests! :O

Wow! Rated educational rounds are really great initiative for div2 contestants. Just ❤️ it!

Is it

Rated?Will educational rounds normally have 7 problem from now on?

A back to back series of contests continues.......

Wow, four rated contests in four days. Keep it going Codeforces! :)

just like if we are in the heaven , Contests everywhere :D

Maybe educational rounds should be rated for div 3 :) just like atcoder abc contests.

I think div3 is a good idea

many contests! it's a chance for me to rescue my rating.

Let's see how many hacks halyavin takes in this round! XD

1e9+7

0x3f3f3f3f I think.

Codeforces seems to be quite excited. 4 rated contests continuously. Wow !

It's a week of "Love to Contests" !

My life these days,

Eat — sleep — codeforces contest

REPEAT

Our recursive routine these days : contest->upsolve->contest->upsolve->contest..........

Is hacking solution outside the room allowed during the contest time ?

Are there rooms in this contest?

I really wonder who that person is.

chrome

Okkk.............

Help: what is the difference between an educational contest and an ordinary contest?

ER features trivial/classic problems, don't be surprised if you have seen some of them before

Ordinary contest:

Different points on different problems

Hacks in-contest (you can't hack after round)

Educational contest:

Problems have the same points (like ACM — ICPC rules)

Hacking phase opened after round. Usually it's 24 hours (but it's 12 this time).

Ordinary contest: Computer is used to test solutions.

Educational contest: a human named halyavin is used to test the solutions.

halyavin is waiting for this contest.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).I'm getting codeforces crashes in the last 3 contests I've been participating, I cannot submit solutions...I'm getting: Ooops! Something has broken down in Codeforces. Do not panic, you can try to reload the page or return Home. Anyway we will carefully read megabytes of logs, analyze stacktraces and fix the problem.

etc... and pictures of bug "ALL YOUR BUG ARE BELONG TO ME" — "I'd rather feel they're mine"...

This has also been happening to me sometimes in contests

clear your caches and cookies, maybe your csrf token is not refreshing

My friends lokpati and bitcyber face similar issue in almost all contests. Whenever they click submit button , it doesn't proceed to 'status' page. Also they do not get any error message like mihelifi . MikeMirzayanov can you look into the issue?

P.S: They have pretty fast Internet connections.

look for errors in console, also see post request in network tab, what do you see when you submit?

See the little spinning icon on the right side of submit button(which usually appears for a moment after you click submit) .In their case, it keeps spinning and this page does not proceed to 'status' page.Same happens even if they submit code via CF editor. I hope I've made the point clear.

It happens to me when i go back and forth after putting a hack testcase for someone.

To fix that, i copy url, close the tab. reopen in tab and paste url.

on the surface it seems once a pub sub connection is opened in a tab, it doesn't allow new connections unless old one is closed. I havent investigated much though.

Will tell them to use this trick. Thanks

I faced a similar problem, here is a verified solution:

It happens when you write like this:

some code{

}

instead write this way -

some code

{

}

It may appear silly, but it works, see it for yourself.

What???!!! :D Ok, we'll change the coding style too, if that's the issue. :D Thanks for your valuable suggestion.

Just try it once for the sake of it.

Braces should be on seperate lines in your entire code.

feel free to downvote if it doesn't work. Worked for me though :)

How to solve C?

First, note that we are essentially just solving .

So iterate over

n, check ifn^{2}-Xis a square, and check whethermexists that satisfies the condition. The appropriate bounds fornare easy to find. Each TC will run in .do we need to start the iteration from 10**9 ? Seems pretty large but maybe the loop doesnt run full?

I used the bound mentioned below by barkingdog, so I iterated

nfrom 1 to about . (Of course, after handling edge cases)why do you need

`isqr`

method? doesn't casting double to ll just remove fractional part?To be absolutely sure, i think. Another example, when string has not more than 1e6 chars, many create char[100005];

Do you mean

`char[1'000'005]`

? That's why I just use`std::string`

.if we factorize the left side we can iterate over divisors of X

Can you explain the equation:

`n^2 - (floor(n/m))^2`

= X? Why and how you derived it? rkm0959Given x, first You have to find n, k such that n^2-k^2 = x, and second check and find whether n/m = k is possible.

Since n^2 <= 4/3*x, the range of n is not that big, and you can easily match k for all n which satisfies x <= n^2 <= 4/3*x by check whether n^2-x is square. Then by calculate candidate of m = n/k, you can know whether n/m = k is possible

Sorry, but I didn't understand the n/m = k part.

Also, can we say that find an m such that sqrt(n^2 — x) is a perfect square?

I want to ask u 1 thing that how do u have come to the conclusion that n^2<=4/3*x ?

maximum number of zeros you can have is when

`m = 2`

, and it will be n^2/4.and

`x = ones`

..so minimum value of x = n^2 — (n^2/4) (when m = 2) ; so`x = 3/4 *(n^2)`

at least.minimum value of x or maximum value of x?

minimum value, x will be at least that much, in other cases when m = 3,etc. x will be even more

How did you do D?

Using Greedy & Priority queue, expand the routes by increasing order of cost of arriving concert.

Since number of road is also small, you don't have to care about multiple visit.

Essentially Dijkstra's algorithm starting with all vertices in the priority queue.

Doesn't that take too long? It's NlogM * all vertices.

You don't run Djikstra's on every vertex, you run it once but starting with every vertex in the priority queue. Initially every vertex is pushed with a weight equal to a[i], and then Djikstra's is the same from then on.

You may create one "new" vertex and conect it with all other vertices puting the walue of the road equal to a[i]. Then run Dijkstra algo from it. And it will work N*logM.

https://pastebin.com/7f6WPztq

Can anyone tell me why my code wouldn't work for D? It kept on failing on test case 3. :(

You can take a path through multiple cities that might be cheaper.

Say the concert costs are 100 100 1 And the edges are 1 2 1 2 3 1

Then it's cheaper to take both edges from city 1 to city 3. Your code only considers taking 1 edge.

Can anyone tell me what's wrong with my approach for D.link to my solution

Any idea of hacking yet ?

is G using idea similar to solving dynamic connectivity offline.But now maintaining basis of cycles possible in that component also and maintaining components as dsu with weights on edges for maintaining xor distances.

Or any other easy solution???

You may maintain the base of cycles by Gaussian elimination. Since the size of each base is not larger than 30, and each edge adds at most one number to the base, we can easily rollback the base in dynamic connectivity.

How to solve F??

There is a simple solution:

dp[m][mask] — best answer if we considered firstmcharacters of the string and amaskof erased substrings.Let's try to speed it up. If there are two states

dp[m_{1}][mask_{1}] anddp[m_{2}][mask_{2}] such that the lengths of strings in these states are equal, butdp[m_{1}][mask_{1}] <dp[m_{2}][mask_{2}], then we are not interested in statedp[m_{2}][mask_{2}] at all. So let's change our dynamic programming todp_{2}[m][mask] = 1 if we can reach this state with optimal answer (and otherwise it's 0).To calculate it, you have to iterate on the ''layers'' of states (here by layer I call a set of states with equal length of resulting strings) and find the minimum character that allows to go to the next layer from the current one.

Its complexity is , but in fact it's pretty fast since most states are unreachable.

Code: https://pastebin.com/K5cHmbgs

Isn't it ?

If we consider

xorto have complexityO(1), then it's since checking if a number belongs to the base can be done in time .Probably I need to wait for editorial. I don't understand how you are doing dynamic connectivity offline with gauss. For me it seems that when you merge two components you will need to do gauss in for numbers.

We don't have to store a separate base for each component. Since the graph always stays connected, we may instead store a base of all cycles in the graph (even if some of them are disconnected now, they will become connected later).

That makes sense. Thanks.

But if the graph is not connected. then we cannot do better than O(logC*logC) for merging two guass right??

Also in this question except to eliminate the logC in complexity,is there any other need of connected graph??

My (really ugly) code of that complexity passed in under 700ms. http://codeforces.com/contest/938/submission/35374477. It'd be fun if someone hacked it :D

I have been trying 1 hour with this solution. Can someone plz tell me what is wrong with this solution https://ide.geeksforgeeks.org/s3ldY59oii

I didn't completely go over your code yet, but using int for

xseems a bit dangerous.You are calculating

x*xsometimes, wherexmay run up to 10^{5}. Yet you used int forx...I defined int as long and long. And i also checked for random 100 cases > 1e8. No time limet exceeded. I also compared 10 to 500 but no errors. But i cant find what is wrong. Ill again go to specialist. For the past few contests my rating are going down. But as i solve problems more and more my ratings are going down. Few contests back for some contests, i solved D, E etc but recdently im completely fucked up.

Excuse me but where did you define

`int`

as`long long`

? I only saw you define`ll`

as`long long`

. Would you please point it out? Thx a lot.its good to be frustrated. use that energy next time.

why aren't you using templates, this can lead to bugs which will waste time at the least.

How it can be replaced by templates? 1) something like

imho isn't simpler than just for() 2) I have no ideas how to make same with templates

(I don't use such macros, I don't think they give speedup)

I was wrong. I think they are fine. Just need few more brackets to be sure.

Personally i think it might give speed up to people who make typo when trying to type faster (like me). Those typos sometimes irritates and takes brain bandwidth.

template 2 isn't fine:

could someone help me with problem B my code

Try 2 600000 800000

Here's my code: https://pastebin.com/attptiBj

Basically, the key thing for B is to

Find the minimum distance from current start to the next interval greater, and current end to the previous interval smaller, then shift whatever is closer.

This prevents you from moving a large interval and missing certain intervals.

So for start = 1, end = 10^6. If the intervals are 1, 500000, 600000, you don't want to be double counting 400000+500000, because if you moved 400000 on both sides, then you only have to move an additional 100000 from start to get to 500000.

Constantly update start and end with the new closest intervals to count correctly.

You also want to break out of the program and return when start and end intersect, which signals that you have seen all the intervals so you should exit.

In problem C,I wonder we can hack only with testcases equal to one, but how about those coder whose solution may got time limit exceed due to more testcases?

Main tests will handle that issue.

Problem C: I'm really confused by the case2,can anybody express it?thanks so much

What is the difference between these two solutions ?

WA

AC

How priority queue works in both the cases?

What's "Unexpected verdict" when I try to hack others?

del

Idea for E?

I find some equation but it is O(N^2)...

For

E. First by sorting, compress the array as (number, occurrences).Now, we will calculate how much time each number will by added in our summation.

Let's look at this number

x— say there areuoccurrences ofx, and there arevnumbers that are larger thanx. Then,xappears in our summation if and only if thevnumbers that are larger thanxappear AFTER at least onexappears. The "probability" for this is , so the number of permutations that addxto our summation is . Now it's just some partial sums, easy calculation. Time Complexity just for sorting.Ohhh.. I see... Thanks!

But is there another way of calculating the number of ways for all v's to be after x? I don't know how probabilities work in this kind of cases so another solution would be clearer. This code seems very nice but i can't understand the part with binom(n,c) .

That's because the numbers which are larger than

xshould appear after at least onex,but the numbers which are smaller thanxcould appear anywhere.So you have to location the smaller numbers,which're (c is the size of smaller numbers),andc! for every permutation,then the larger numbers(or equal numbers) should fill the last positions,which is (n-c- 1)!,and the position forxis settled.Ohhh, ok, thank you very much!!! Now i got it.

can u tell me what inv[] and ifac[] mean ?

inv[i] is the modular inverse of number i and ifac[i] is the modular inverse of i! (i factorial). You can learn about it on the internet. It is the way of calculating combinations for large numbers.

Ok, thank u.

why the "probability" for this is u/(u+v)? isnt it u!*v!/((u+v)!)?

Since there are u+v numbers which are not small then x, x appears if and only if the first of the u+v numbers is equal to x. There are u numbers same as x, the probability is u/(u+v)

can i hack soultions if i haven't submitted any solution? Does it count for any rating changes?

yes you can . no it won't be counted .

Yazdan_ra is a genius cheat! lol!! he submitted multiple solutions for the same question from another account Double-D (owned by him) in which a specific case will fail and then he hacked all of them from his real account!!! ![ ]() isn't that totally unfair!

Yeah, that's definitely bannable.

Hacking doesn't benefit the hacker in educational rounds, apart from getting a green plus next to your name in the standings.

Is the prelim standing final for div2 rating changes? P.S. : I haven't participated in the contest.

No. Ratings will be updated after the 12 hours when after the actual system tests finish.

Poor fella doesn't know hacking will not affect his rating.

That is just stupid. One has no profit of hacking himself in this round.

So in a way he hacked the hacking system ...lol

Why does the meaning of the term "submatrix" in task C differ from conventional one? "A submatrix of a matrix is obtained by deleting any collection of rows and/or columns." https://en.wikipedia.org/wiki/Matrix_(mathematics)#Submatrix

Here "submatrix" means some square area of adjacent elements. That's misleading!

There is no need for System test, we already have one halyavin :D

Hahahahahaha

Can anyone tell me what's wrong with my approach for D. link

anyone can tell me the difference between GNU C++ 11 & GNU C++ 14?

this one is my submission during the contest, which got tle on testcase 37.

35369457 (C++ 11)

and this one is my submission right after the contest, which is exactly same code with above, and got ac.

35370185 (C++ 14)

only difference between two submissions is the language i choose...

got confused

Lel, in my language vowels are considered to be 'a', 'e', 'i', 'o', 'u', and I didn't read that there was 'y' as well xD

What's with the time and memory limits in codeforces rounds? I find them way too harsh. Today I got TLE on F with an

O(n^{2}) solution (if we take that operations with integers takeO(1) time), and memory limit exceeded on D using Dijkstra's algorithm.Of course, there may be something wrong with my code (Problem D, Problem F), but I don't see it. Do you? >:)

Maybe it won't help you, but try to add

ios_base::sync_with_stdio(false); cin.tie(nullptr);

to your D submission. My solution is using Dijkstra to, and it passed tests and is not hacked yet. Also, recently I have TL due to missing io boost

That sped it up quite a bit, but it didn't reduce the memory consumption. :/

If I use "ios_base::sync_with_stdio(false); cin.tie(nullptr); " what is the benifit of this ???

By default, you can mix c++-style io (cin cout) with c-style(scanf printf) without any problems (it should work as expected), but results in performance. ios_base::sync_with_stdio(false) — disable this sync-tion. cin.tie(nullptr) disable sync-tion of cin and cout.

Not sure, but in F it seems (for * (for auto) * (for .. state.second) might be

n^{3}.I see now.

use normal array for dist[] and link list for edges instead of vector?

It took me a while but I found the mistake. In the edge loop inside the while you put the weight into a variable that is declared as int, that makes it overflow and possibly means an negative loop so it makes sense that it is MLE. http://codeforces.com/contest/938/submission/35380385

In problem C,can anybody explain why the answer is 999954147 when n=36514,m=2? thanks so much

you need to write one zero in four squares.

i mean, you can write zero in (x, y) if x and y are both even, otherwise write one

then you can write 36514*36514*0.75=999954147 one(s).

yeah thank you ，i was stupid

I think it should be 36514*36514-[36514/3]*[36514*3]

why?

i think you mean you will put only one zero(0) in 3*3 square,

but you can find 2*2 square which doesn't contain any zero(0)s.

yeah i just see ，thanks

how to hack person ?

For example, you can open submission page (like this) and press "hack it"

Spasibo !)

In C answer for 48 is 8 2 for many people but for 8 2 maximum possible ones are 55. Can someone tell where I am wrong. Thanks in advance.

i think so，8*8-3*3，why is this wrong？

maximum possible 1's = n*n-(n/m)*(n/m)

yeah you are right，i was stupid

What is the max possible value of n and m

In question it is given 1e9 but can it ever reach 1e9?

max possible N will be sqrt((4*x)/3)

Thank you. Could you please tell how to find the maximum value. I was thinking something like this n*n*(1 — 1/(m*m)) = x so n*n = x if I assume 1/(m*m) to be small enough so n = sqrt(x).

n will be maximum when m=2 hence n*n-(n/2)*(n/2)=x therefore (3*n*n)/4=x hence n=sqrt((4*x)/3);

ok got it

Can anyone tell me if my approach for D is correct? The contest ended before I got to finish it..

For each component of the graph, I will construct it's MST, because no answer for any node will contain an edge not present in the MST(needs proof).

Then, I choose a root for each tree and start traversing from root to leaves(dfs2), and for each node I will update it's answer as following:

`ans[current]=min(ans[current],ans[child]+2*edge(current,child))`

The initial answer for every node is it's concert price.

Then I will do another dfs(dfs3), this time; I will update the answer of the child with the answer of it's parent(going up).

It needs: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm And using MST doesn't help, because you need to use the sum of the weights, not the max.

MST for MinimumST. I still don't see where it doesnt work.

Anyway, can you elaborate more? How do I apply Dijkstra on the graph?

cmon, i know you can do it by yourself, don't spam :) It is a simple algorithm, easier than Kruskal's or Prim :)

No no I know the algorithm very well, I also thought about using it in the contest, but I have no idea HOW to do it for every node

I'll find out..

Thanks a lot, you've been very helpful :D

Let's say a concert is a vertex. Create the graph that the problem gives to you but with weights doubled. Also, create edges from the concert to vertex i with weight a[i]. The distance between the concert and vertex i is exactly what you want so just start from the concert.

Very elegant solution! Thanks a loot.

I have been trying 1 hour with this solution. Can someone plz tell me what is wrong with this solution https://ide.geeksforgeeks.org/s3ldY59oii. No TLE . I also compared 10 to 500 but no errors. But i cant find what is wrong. Ill again go to specialist/pupil. For the past few contests my rating are going down. But as i solve problems more and more my ratings are going down. Few contests back for some contests, i solved D, E etc but recdently im completely fucked up.

Your output for 3 is -1, but correct output should be 2 2.

Don't be upset if u can't solve much problems. You do your best, and try to upsolve them after contest. Rating really doesn't matter, whether you are pupil or expert. (Sorry for bad english)

Yes, Rating doesnt matter, but i cant find the simple error and i make many silly mistakes and if a new problem comes, only if i ve already seen it previously, i can solve it, else i cant. I dont know how many problems i need to see. I ve already seen more than 1500 to 2000 problems, and still not a CM or even expert, as i ll go down now.

more problems you solve, more you will able to find the logic behind a problem. Again don't think that you are not CM or expert.

Do successful hacking attempts provide the challenger with extra points in educational rounds? I was lucky enough to make my first successful hack in an educational round, and wanted to learn about this since the scoreboard does not show any points, or changes in my standing. (i.e. rank)

No, hacking in educational rounds doesn't increase nor decrease your points.

Good to know. Thanks!

Can someone hack my solution for D?

I sort edges, then I look at every edge and try to improve answer for every verticle:

If I have an edge from a to b which costs d, and ans[a] > ans[b], I make ans[a] = min(ans[a], ans[b] + 2 * d); ans[b] = min(ans[b], ans[a] + 2 * d) otherwise.

I do this stuff 50 times, then output the ans array.

Sorry for my english btw.

who can explain dotorya's C? link

We should find such

nandm, thatIt means , or

t_{1}*t_{2}=Xin his notation.It means that and and .

Then check if condition holds and print

nandmWhen we'll be able to see tests on which solution was hacked?

Tests are visible after the end of hacking phase.

Thanks :)

hi, could you explain your solution for C? i see many solutions that use

`% 2`

but can't understand their logicI need to solve x = u^2 — v^2 = (u — v) * (u + v). So I factor x into 2 factors. But not all factors produce integer u and v. I can restore integer u and v from factors f1 = u — v and f2 = u + v if and only if f1 equals f2 modulo 2. Since the answer of the problem equals n^2 — [n / m]^2, I have n = u and can restore m from v.

thank you very much

The last was a bit difficult

Well I don't think so. It's super easy, especially compared with round #462...

In problem D, why my solution that uses SPFA got TLE in the last test(test17), is it a requisite to use dijkstra to calculate the minimum route in this problem?

Of course,SPFA is always unstable.

http://codeforces.com/contest/938/submission/35361791

Can i know why i got hacked in TLE (prob.D) ? with dijkstra?

PS. What a newbie's mistake !! everybody thank you !!

You can check the single vertex up to

ntimes. If this vertex has degreen, you haveO(n^{2}) operations.Your solution does't work with two components. Try this test

4 2

1 2 1

3 4 1

1 10 1 10

Answer must be 1 3 1 3

P.S. Sorry,false alarm. Didn't read code correctly.

NoTalentBug you make unnecessary vertex run(n^2), look my solve

Example:

was g[k].cost = 9,

you updated it g[k].cost = 8,

but you RUN EDGES CYCLE for old value and new

(Sorry for bad english)

Waiting for rating?? SubSpring

Where is the system testing?

There is no system testing. These are the final results. Now we are just waiting for the rating.

(THE ABOVE INFO IS WRONG !!!)

Sorry for that!

There will be system testing brother. All the hack cases will be added and the solutions will be rejudged.

Ahh the hacks will be added to everybody ? Sorry I did not know that. Good to know !

Will the system testing and rating update happen before the next contest starts?

Where is the system test?

Where is the tutorial?

You can usually expect tutorial no later than 24 hours after the end of the contest (coding phase in this case).

emmm..when will the rating change? Next contest will come.

But the bad news is that the system test hasn't begun yet... There are still only two test cases for problem C. According to the rules, all the hacks will be added into test data and rejudge. I'm wondering why it's called final standings instead of current ones...

AFAIK In every educational rounds after Hacking phase it says

`Final standings, open hacking phase finished`

But after that System test starts.

when will be the tutorials be published for this contest?

Here comes "Codeforces Round #464 (Div. 2)" and the ratings haven't been updated yet. So what will happen if some 1800-rating person who should gain +200 rating in the last round takes part in the #464?

If the ratings aren't updated before the contest, one possible solution is to evaluate the ratings of Education CF Round and then make it unrated for the people who became Div 1 in that round.

that's a solution, but that would consume people's time and then after that make it unrated. Like I wouldn't want to participate if it's unrated for me, but it's hard for me to decide now, since I don't know whether it would be rated.

So when will the rating change?The next contest is coming soon.And the editorial hasn't been published either.

http://codeforces.com/blog/entry/57819?#comment-414872

When will the editorials be published ?

I do want the editorials too.

Can u write the tutorial for this Ed.Round please

I don't understand in which moment I should stop search the answer and write "-1" (938C - Constructing Tests). Could somebody help me with it?

what about the rating for div2?

When will the system test begin?

seems it is working now...

Yes,I see.

Holly Dijkstra, nobody hacked my D! For one second I did dijkstras from the cheapest cities, and in the other second I did iterations of bellman ford.

You are a litter bit unlucky,bother. :D

is it rated??

yes, only for

div2If you try to use a case in which t=100 and all x=1000000000 in CUSTOM INVOCATION, then you will find an amount of solutions in problem C will get time limit at the last of sorted by Execution Time

The system test is really weak and we are forbided to hack with t over 1.I think that shall be a point for hacking

Why are those solutions slow, are they doing more than sqrt(10**9) operations?

If we can hack with t over 1,we have to wait much more time for the system test.

In Question C, for input = 21, why isnt "5 4" a valid solution?

Suppose we have a 5X5 square with all 1s except on the 4 corners where we have 0s, then if I have to select a 4X4 squares, there are 4 squares of 4X4 I can choose and each of them would contain a 0.

Please correct me if I'm wrong, help is appreciated.

not "a" but all such 4X4 squares should be with atleast 1 zero

Because we need to maximise the number of 1s.

Therefore, the input 5 4 will likely generate a matrix like this

which have 24 1s.

Indeed, if the problem asks for 24 instead, then 5 4 will be a correct solution.

I think you misunderstood the task:

You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1's in this matrix is maximum possible. Print the maximum possible number of 1's in such matrix.meaning that values in matrix must be arranged so that the number of 1's is maximum.For example, for n = 5 and m = 4 the maximum would be 24

1 1 1 1 1

1 1 1 1 1

1 1 0 1 1

1 1 1 1 1

1 1 1 1 1

So, your solution is undermining the word "maximum". For 21 one of the answers might be n = 5 and m = 2

1 1 1 1 1

1 0 1 0 1

1 1 1 1 1

1 0 1 0 1

1 1 1 1 1

Thanks for your time. Got it. :)

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