Educational Codeforces Round 38 [Rated for Div. 2]

7 years ago, # ^ |

+14

Are there rooms in this contest?

→ Reply

006-20054-07-Kuralb-A.

7 years ago, # |

+36

→ Reply

SangBijaksana

7 years ago, # ^ |

I really wonder who that person is.

→ Reply

almasalmas

6 years ago, # ^ |

chrome

→ Reply

lin_diex

7 years ago, # |

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

→ Reply

haleyk100198

7 years ago, # ^ |

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

→ Reply

EternalFire

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

7 years ago, # ^ |

+67

Ordinary contest: Computer is used to test solutions.

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

→ Reply

starboy_jb

7 years ago, # |

halyavin is waiting for this contest.

→ Reply

7 years ago, # |

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

→ Reply

mihelifi

7 years ago, # |

+18

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

→ Reply

BenniKartefla

7 years ago, # ^ |

This has also been happening to me sometimes in contests

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

Will tell them to use this trick. Thanks

→ Reply

pratikwankhede

7 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

rizhiy

7 years ago, # |

+11

How to solve C?

→ Reply

7 years ago, # ^ |

First, note that we are essentially just solving $\text{[math]}$ .

So iterate over n, check if n² - X is a square, and check whether m exists that satisfies the condition. The appropriate bounds for n are easy to find. Each TC will run in $\text{[math]}$ .

→ Reply

7 years ago, # ^ |

do we need to start the iteration from 10**9 ? Seems pretty large but maybe the loop doesnt run full?

→ Reply

7 years ago, # ^ |

I used the bound mentioned below by barkingdog, so I iterated n from 1 to about $\text{[math]}$ . (Of course, after handling edge cases)

→ Reply

Serh.kry

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

Morphy

7 years ago, # ^ |

+10

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

→ Reply

nimom

7 years ago, # ^ |

← Rev. 3 →

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

→ Reply

7 years ago, # ^ |

Given 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

→ Reply

rohan1506

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

zetapi

7 years ago, # ^ |

← Rev. 2 →

minimum value of x or maximum value of x?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

dhruvsomani

7 years ago, # |

← Rev. 2 →

+18

How did you do D?

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

+17

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

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

andriy_zhuk

7 years ago, # ^ |

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.

→ Reply

https://pastebin.com/7f6WPztq

7 years ago, # |

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

→ Reply

arknave

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

CODENT47

7 years ago, # ^ |

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

→ Reply

thienlong1511

7 years ago, # |

Any idea of hacking yet ?

→ Reply

teja349

7 years ago, # |

+10

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

teja349

7 years ago, # ^ |

How to solve F??

→ Reply

7 years ago, # ^ |

← Rev. 4 →

There is a simple $\text{[math]}$ solution: dp[m][mask] — best answer if we considered first m characters of the string and a mask of erased substrings.

Let's try to speed it up. If there are two states dp[m₁][mask₁] and dp[m₂][mask₂] such that the lengths of strings in these states are equal, but dp[m₁][mask₁] < dp[m₂][mask₂], then we are not interested in state dp[m₂][mask₂] at all. So let's change our dynamic programming to dp₂[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 $\text{[math]}$ , but in fact it's pretty fast since most states are unreachable.

Code: https://pastebin.com/K5cHmbgs

→ Reply

Um_nik

7 years ago, # ^ |

Isn't it $\text{[math]}$ ?

→ Reply

7 years ago, # ^ |

If we consider xor to have complexity O(1), then it's $\text{[math]}$ since checking if a number belongs to the base can be done in time $\text{[math]}$ .

→ Reply

Um_nik

7 years ago, # ^ |

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 $\text{[math]}$ for $\text{[math]}$ numbers.

→ Reply

7 years ago, # ^ |

+25

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

→ Reply

Um_nik

7 years ago, # ^ |

That makes sense. Thanks.

→ Reply

teja349

7 years ago, # ^ |

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

→ Reply

tfg

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

7 years ago, # |

-16

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

→ Reply

7 years ago, # ^ |

I didn't completely go over your code yet, but using int for x seems a bit dangerous.

You are calculating x * x sometimes, where x may run up to 10⁵. Yet you used int for x...

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

deep_learning

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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)

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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

→ Reply

weights

7 years ago, # |

could someone help me with problem B my code

→ Reply

7 years ago, # ^ |

Try 2 600000 800000

→ Reply

7 years ago, # ^ |

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

Basically, the key thing for B is to

Make sure that if you are moving simultaneously
In order to make sure you don't over or undercount intervals, try each interval.

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.

→ Reply

7 years ago, # |

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?

→ Reply

abx_2109

7 years ago, # ^ |

Main tests will handle that issue.

→ Reply

7 years ago, # |

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

→ Reply

U_Square

7 years ago, # |

← Rev. 2 →

What is the difference between these two solutions ?

How priority queue works in both the cases?

→ Reply

Panole2333

7 years ago, # |

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

→ Reply

Serh.kry

7 years ago, # |

← Rev. 2 →

del

→ Reply

7 years ago, # |

Idea for E?

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

→ Reply

7 years ago, # ^ |

+48

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 are u occurrences of x, and there are v numbers that are larger than x. Then, x appears in our summation if and only if the v numbers that are larger than x appear AFTER at least one x appears. The "probability" for this is $\text{[math]}$ , so the number of permutations that add x to our summation is $\text{[math]}$ . Now it's just some partial sums, easy calculation. Time Complexity $\text{[math]}$ just for sorting.

→ Reply

7 years ago, # ^ |

Ohhh.. I see... Thanks!

→ Reply

21August

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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 $\text{[math]}$ (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.

→ Reply

21August

7 years ago, # ^ |

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

→ Reply

HiamKing

7 years ago, # ^ |

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

→ Reply

21August

7 years ago, # ^ |

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.

→ Reply

HiamKing

7 years ago, # ^ |

Ok, thank u.

→ Reply

JayZhan

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

gs15120

7 years ago, # ^ |

← Rev. 3 →

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)

→ Reply

imalgoholic

7 years ago, # |

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

→ Reply

ShowStopper728

7 years ago, # ^ |

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

→ Reply

katana_handler

7 years ago, # |

← Rev. 2 →

+14

Yazdanra 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!

→ Reply

7 years ago, # ^ |

+11

Yeah, that's definitely bannable.

→ Reply

7 years ago, # ^ |

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

→ Reply

imalgoholic

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

vatsal

7 years ago, # ^ |

+30

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

→ Reply

dantrag

7 years ago, # ^ |

+21

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

→ Reply

vaibhav1997

7 years ago, # ^ |

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

→ Reply

amtematem

7 years ago, # |

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!

→ Reply

Hasan

7 years ago, # |

+22

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

→ Reply

I_Love_Nicki_Minaj

7 years ago, # ^ |

Hahahahahaha

→ Reply

CODENT47

7 years ago, # |

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

→ Reply

sansae

7 years ago, # |

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

→ Reply

EtCetera

7 years ago, # |

+20

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

→ Reply

buj

7 years ago, # |

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²) solution (if we take that operations with integers take O(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? >:)

→ Reply

7 years ago, # ^ |

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

→ Reply

buj

7 years ago, # ^ |

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

→ Reply

sagarthecoder2

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

GreenGrape

7 years ago, # ^ |

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

→ Reply

buj

7 years ago, # ^ |

I see now.

→ Reply

Yoomov

7 years ago, # ^ |

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

→ Reply

tfg

7 years ago, # ^ |

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.net/contest/938/submission/35380385

→ Reply

7 years ago, # |

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

→ Reply

sansae

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

yeah thank you ，i was stupid

→ Reply

7 years ago, # ^ |

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

→ Reply

sansae

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

yeah i just see ，thanks

→ Reply

random_shuffle01

7 years ago, # |

← Rev. 2 →

how to hack person ?

→ Reply

7 years ago, # ^ |

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

→ Reply

random_shuffle01

7 years ago, # ^ |

+12

Spasibo !)

→ Reply

fullbuster

7 years ago, # |

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.

→ Reply

7 years ago, # ^ |

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

→ Reply

deepak1527

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

yeah you are right，i was stupid

→ Reply

hell_hacker

7 years ago, # ^ |

What is the max possible value of n and m

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

→ Reply

deepak1527

7 years ago, # ^ |

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

→ Reply

hell_hacker

7 years ago, # ^ |

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

→ Reply

deepak1527

7 years ago, # ^ |

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

→ Reply

fullbuster

7 years ago, # ^ |

ok got it

→ Reply

GLAYS

7 years ago, # |

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

→ Reply

Tutis

7 years ago, # ^ |

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.

→ Reply

GLAYS

7 years ago, # ^ |

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?

→ Reply

Tutis

7 years ago, # ^ |

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

→ Reply

GLAYS

7 years ago, # ^ |

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

→ Reply

tfg

7 years ago, # ^ |

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.

→ Reply

7 years ago, # |

← Rev. 2 →

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.

→ Reply

all_out

7 years ago, # ^ |

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)

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

all_out

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

ilim

7 years ago, # |

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)

→ Reply

Ownography

7 years ago, # ^ |

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

→ Reply

ilim

7 years ago, # ^ |

Good to know. Thanks!

→ Reply

savelyevlad

7 years ago, # |

← Rev. 2 →

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.

→ Reply

Serh.kry

7 years ago, # |

who can explain dotorya's C? link

→ Reply

Igorjan94

7 years ago, # ^ |

+15

We should find such n and m, that $\text{[math]}$
It means $\text{[math]}$ , or t₁ * t₂ = X in his notation.
It means that $\text{[math]}$ and $\text{[math]}$ and $\text{[math]}$ .
Then check if condition holds and print n and m

→ Reply

aijey

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

Tests are visible after the end of hacking phase.

→ Reply

aijey

7 years ago, # ^ |

Thanks :)

→ Reply

Bliss8

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

easyPici

7 years ago, # |

The last was a bit difficult

→ Reply

deep_learning

7 years ago, # ^ |

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

→ Reply

ohazyi

7 years ago, # |

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?

→ Reply

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

7 years ago, # ^ |

Of course,SPFA is always unstable.

→ Reply

NoTalentBug

7 years ago, # |

← Rev. 2 →

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

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

→ Reply

7 years ago, # ^ |

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

→ Reply

balalaika

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

nevermore

7 years ago, # ^ |

← Rev. 4 →

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)

void Solve()
{
	while (!pq.empty())
	{
		auto top = pq.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 = it.to;
			int64 costEdge = it.cost;
			int64 newCost = costEdge + cost;
			if (g[to].cost > newCost)
			{
				g[to].cost = newCost;
				pq.push({ newCost,to });
			}
		}
	}
}

→ Reply

NourAlhadi

7 years ago, # |

Waiting for rating?? SubSpring

→ Reply

Anubis

7 years ago, # |

← Rev. 2 →

Where is the system testing?

→ Reply

Hepic_Antony_Skarlatos

7 years ago, # ^ |

← Rev. 2 →

-20

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!

→ Reply

nileshjha19

7 years ago, # ^ |

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

→ Reply

Hepic_Antony_Skarlatos

7 years ago, # ^ |

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

→ Reply

Fullmetal_Algorithmist

7 years ago, # |

+31

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

→ Reply

7 years ago, # |

+37

Where is the system test?
Where is the tutorial?

→ Reply

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

7 years ago, # ^ |

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

→ Reply

2022haha

7 years ago, # |

+29

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

→ Reply

deep_learning

7 years ago, # ^ |

← Rev. 2 →

+18

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

→ Reply

Deba

7 years ago, # ^ |

+16

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

→ Reply

xht13127

7 years ago, # |

+46

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?

→ Reply

Ashishgup

7 years ago, # ^ |

+19

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.

→ Reply

redocyz

7 years ago, # ^ |

+10

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.

→ Reply

ZZZZZR

7 years ago, # |

+35

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

→ Reply

Hepic_Antony_Skarlatos

7 years ago, # |

→ Reply

HipHop

7 years ago, # |

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?

→ Reply

antoshkin

7 years ago, # |

what about the rating for div2?

→ Reply

7 years ago, # |

When will the system test begin?

→ Reply

7 years ago, # ^ |

seems it is working now...

→ Reply

7 years ago, # ^ |

Yes,I see.

→ Reply

Morphy

7 years ago, # |

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.

→ Reply

7 years ago, # ^ |

You are a litter bit unlucky,bother. :D

→ Reply

Davood

7 years ago, # |

is it rated??

→ Reply

antoshkin

7 years ago, # ^ |

yes, only for div2

→ Reply

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

ZZZZZR

7 years ago, # ^ |

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

→ Reply

pratikwankhede

7 years ago, # |

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.

→ Reply

7 years ago, # ^ |

then if I have to select a 4X4 squares

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

→ Reply

aarcturus

7 years ago, # ^ |

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.

→ Reply