Recent actions

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)

Ok, thank u.

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.

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

template 2 isn't fine:

vector<vector<T>> table; auto it = table.begin() + i; sort(all(*(it++))); //expected sort(table[i+1].begin(), table[i+1].end()) //after macro substitution sort((*it++).begin(), (*it++).end()); //which means sort(table[i+1].begin(), table[i+2].end()) //->ERROR

Do you mean char[1'000'005]? That's why I just use std::string.

Thanks for your time. Got it. :)

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

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

Created or updated the text

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

Because we need to maximise the number of 1s.

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

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1

which have 24 1s.

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

then if I have to select a 4X4 squares

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

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.

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

I do want the editorials too.

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

minimum value of x or maximum value of x?

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

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.

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

If 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

yes, only for div2

You are a litter bit unlucky,bother. :D

Yes,I see.

seems it is working now...

is it rated??

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.

When will the system test begin?

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

f(0, 100, [](int i){

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)

To be absolutely sure, i think. Another example, when string has not more than 1e6 chars, many create char[100005];

what about the rating for div2?

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?

When will the editorials be published ?

Can you explain the equation: n^2 - (floor(n/m))^2 = X? Why and how you derived it? rkm0959

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

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 :)

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

I really wonder who that person is.

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.

Will tell them to use this trick. Thanks

#define f(i, x, y) for(int i = x; i < y; i++)
#define all(X) X.begin(), X.end()

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

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.

Few contests back for some contests, i solved D, E etc but recdently im completely fucked up

its good to be frustrated. use that energy next time.

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.

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.

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?

Ohhh, ok, thank you very much!!! Now i got it.

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

when will be the tutorials be published for this contest?

AFAIK In every educational rounds after Hacking phase it says
Final standings, open hacking phase finished
But after that System test starts.

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

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...

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

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.

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.

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


  1. was g[k].cost = 9,

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

  3. but you RUN EDGES CYCLE for old value and new

(Sorry for bad english)

void Solve()
	while (!pq.empty())
		auto top =; pq.pop();
		int64 v = top.second;
		int64 cost = top.first;
		if (g[v].cost != cost) continue; // it important !!!!!!! 
		for (const auto& it : g[v].e)
			int64 to =;
			int64 costEdge = it.cost;
			int64 newCost = costEdge + cost;
			if (g[to].cost > newCost)
				g[to].cost = newCost;
				pq.push({ newCost,to });

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.

Where is the system test?
Where is the tutorial?

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.

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.

You can check the single vertex up to n times. If this vertex has degree n, you have O(n2) operations.

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

0x3f3f3f3f I think.

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

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)

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

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


Sorry for that!

Where is the system testing?

Waiting for rating?? mr.Spring

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

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

That's because the numbers which are larger than x should appear after at least one x,but the numbers which are smaller than x could appear anywhere.So you have to location the smaller numbers,which're (c is the size of smaller numbers),and c! for every permutation,then the larger numbers(or equal numbers) should fill the last positions,which is (n - c - 1)!,and the position for x is settled.

Of course,SPFA is always unstable.

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.

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?

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

The last was a bit difficult

Very elegant solution! Thanks a loot.

thank you very much

We should find such n and m, that
It means , or t1 * t2 = X in his notation.
It means that and and .
Then check if condition holds and print n and m

I 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.

hi, could you explain your solution for C? i see many solutions that use % 2 but can't understand their logic

Thanks :)

Tests are visible after the end of hacking phase.

Good to know. Thanks!

IMG_20180217_020414254_BURST000_COVER_TOP 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.

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

My (really ugly) code of that complexity passed in under 700ms. It'd be fun if someone hacked it :D

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

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.

why do you need isqr method? doesn't casting double to ll just remove fractional part?

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

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

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

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?

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??

who can explain dotorya's C? link

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.