Educational Codeforces Round 38 [рейтинговый для Див. 2]

6 лет назад, # ^ |

+14

Are there rooms in this contest?

→ Ответить

006-20054-07-Kuralb-A.

6 лет назад, # |

+36

→ Ответить

SangBijaksana

6 лет назад, # ^ |

I really wonder who that person is.

→ Ответить

almasalmas

6 лет назад, # ^ |

chrome

→ Ответить

lin_diex

6 лет назад, # |

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

→ Ответить

haleyk100198

6 лет назад, # ^ |

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

→ Ответить

EternalFire

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

+67

Ordinary contest: Computer is used to test solutions.

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

→ Ответить

starboy_jb

6 лет назад, # |

halyavin is waiting for this contest.

→ Ответить

6 лет назад, # |

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

→ Ответить

mihelifi

6 лет назад, # |

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

→ Ответить

BenniKartefla

6 лет назад, # ^ |

This has also been happening to me sometimes in contests

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

Will tell them to use this trick. Thanks

→ Ответить

pratikwankhede

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

rizhiy

6 лет назад, # |

+11

How to solve C?

→ Ответить

6 лет назад, # ^ |

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]}$ .

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Serh.kry

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Morphy

6 лет назад, # ^ |

+10

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

→ Ответить

nimom

6 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

rohan1506

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

zetapi

6 лет назад, # ^ |

← Rev. 2 →

minimum value of x or maximum value of x?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

dhruvsomani

6 лет назад, # |

← Rev. 2 →

+18

How did you do D?

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

+17

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

andriy_zhuk

6 лет назад, # ^ |

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

6 лет назад, # |

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

→ Ответить

arknave

6 лет назад, # ^ |

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

→ Ответить

CODENT47

6 лет назад, # ^ |

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

→ Ответить

TShT

6 лет назад, # |

в C ответ n^2-[n/m]^2 = x ???

→ Ответить

6 лет назад, # ^ |

Это уравнение, из которого нужно найти m, перебрав n (оценив как корень * 2 + 1000, например)

→ Ответить

thienlong1511

6 лет назад, # |

Any idea of hacking yet ?

→ Ответить

teja349

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

teja349

6 лет назад, # ^ |

How to solve F??

→ Ответить

6 лет назад, # ^ |

← 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

→ Ответить

Um_nik

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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]}$ .

→ Ответить

Um_nik

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Um_nik

6 лет назад, # ^ |

That makes sense. Thanks.

→ Ответить

teja349

6 лет назад, # ^ |

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

→ Ответить

tfg

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # |

-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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

deep_learning

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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)

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

weights

6 лет назад, # |

could someone help me with problem B my code

→ Ответить

6 лет назад, # ^ |

Try 2 600000 800000

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # |

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?

→ Ответить

abx_2109

6 лет назад, # ^ |

Main tests will handle that issue.

→ Ответить

6 лет назад, # |

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

→ Ответить

U_Square

6 лет назад, # |

← Rev. 2 →

What is the difference between these two solutions ?

How priority queue works in both the cases?

→ Ответить

Panole2333

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

Idea for E?

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

→ Ответить

Serh.kry

6 лет назад, # |

← Rev. 2 →

del

→ Ответить

6 лет назад, # |

Idea for E?

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Ohhh.. I see... Thanks!

→ Ответить

21August

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

21August

6 лет назад, # ^ |

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

→ Ответить

HiamKing

6 лет назад, # ^ |

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

→ Ответить

21August

6 лет назад, # ^ |

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.

→ Ответить

HiamKing

6 лет назад, # ^ |

Ok, thank u.

→ Ответить

JayZhan

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

gs15120

6 лет назад, # ^ |

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

→ Ответить

imalgoholic

6 лет назад, # |

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

→ Ответить

ShowStopper728

6 лет назад, # ^ |

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

→ Ответить

katana_handler

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

+11

Yeah, that's definitely bannable.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

imalgoholic

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

vatsal

6 лет назад, # ^ |

+30

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

→ Ответить

dantrag

6 лет назад, # ^ |

+21

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

→ Ответить

vaibhav1997

6 лет назад, # ^ |

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

→ Ответить

amtematem

6 лет назад, # |

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!

→ Ответить

Hasan

6 лет назад, # |

+22

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

→ Ответить

I_Love_Nicki_Minaj

6 лет назад, # ^ |

Hahahahahaha

→ Ответить

CODENT47

6 лет назад, # |

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

→ Ответить

sansae

6 лет назад, # |

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

→ Ответить

EtCetera

6 лет назад, # |

+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

→ Ответить

buj

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

buj

6 лет назад, # ^ |

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

→ Ответить

sagarthecoder2

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

GreenGrape

6 лет назад, # ^ |

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

→ Ответить

buj

6 лет назад, # ^ |

I see now.

→ Ответить

Yoomov

6 лет назад, # ^ |

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

→ Ответить

tfg

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

sansae

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

yeah thank you ，i was stupid

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

sansae

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

yeah i just see ，thanks

→ Ответить

random_shuffle01

6 лет назад, # |

← Rev. 2 →

how to hack person ?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

random_shuffle01

6 лет назад, # ^ |

+12

Spasibo !)

→ Ответить

fullbuster

6 лет назад, # |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

deepak1527

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

yeah you are right，i was stupid

→ Ответить

hell_hacker

6 лет назад, # ^ |

What is the max possible value of n and m

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

→ Ответить

deepak1527

6 лет назад, # ^ |

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

→ Ответить

hell_hacker

6 лет назад, # ^ |

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

→ Ответить

deepak1527

6 лет назад, # ^ |

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

→ Ответить

fullbuster

6 лет назад, # ^ |

ok got it

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

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

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

→ Ответить

Tutis

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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?

→ Ответить

Tutis

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

tfg

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # |

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

→ Ответить

all_out

6 лет назад, # ^ |

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)

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

all_out

6 лет назад, # ^ |

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

→ Ответить

vaibhav1997

6 лет назад, # |

Would unsuccessful hacking attempt bring down the my ranking ?

→ Ответить

ilim

6 лет назад, # |

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)

→ Ответить

Ownography

6 лет назад, # ^ |

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

→ Ответить

ilim

6 лет назад, # ^ |

Good to know. Thanks!

→ Ответить

savelyevlad

6 лет назад, # |

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

→ Ответить

Serh.kry

6 лет назад, # |

who can explain dotorya's C? link

→ Ответить

Igorjan94

6 лет назад, # ^ |

+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

→ Ответить

aijey

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

Tests are visible after the end of hacking phase.

→ Ответить

aijey

6 лет назад, # ^ |

Thanks :)

→ Ответить

Bliss8

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

easyPici

6 лет назад, # |

The last was a bit difficult

→ Ответить

deep_learning

6 лет назад, # ^ |

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

→ Ответить

ohazyi

6 лет назад, # |

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?

→ Ответить

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

6 лет назад, # ^ |

Of course,SPFA is always unstable.

→ Ответить

NoTalentBug

6 лет назад, # |

Can i know why i got hacked in prob.D ?

→ Ответить

NoTalentBug

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

balalaika

6 лет назад, # ^ |

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

→ Ответить

nevermore

6 лет назад, # ^ |

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

→ Ответить

NourAlhadi

6 лет назад, # |

Waiting for rating?? SubSpring

→ Ответить

Anubis

6 лет назад, # |

← Rev. 2 →

Where is the system testing?

→ Ответить

Hepic_Antony_Skarlatos

6 лет назад, # ^ |

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

→ Ответить

nileshjha19

6 лет назад, # ^ |

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

→ Ответить

Hepic_Antony_Skarlatos

6 лет назад, # ^ |

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

→ Ответить

Fullmetal_Algorithmist

6 лет назад, # |

+31

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

→ Ответить

6 лет назад, # |

+37

Where is the system test?
Where is the tutorial?

→ Ответить

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

6 лет назад, # ^ |

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

→ Ответить

2022haha

6 лет назад, # |

+29

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

→ Ответить

deep_learning

6 лет назад, # ^ |

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

→ Ответить

Deba

6 лет назад, # ^ |

+16

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

→ Ответить

xht13127

6 лет назад, # |

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

→ Ответить

Ashishgup

6 лет назад, # ^ |

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

→ Ответить

redocyz

6 лет назад, # ^ |

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

→ Ответить

ZZZZZR

6 лет назад, # |

+35

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

→ Ответить

Hepic_Antony_Skarlatos

6 лет назад, # |

→ Ответить

HipHop

6 лет назад, # |

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?

→ Ответить

antoshkin

6 лет назад, # |

what about the rating for div2?

→ Ответить

6 лет назад, # |

When will the system test begin?

→ Ответить

6 лет назад, # ^ |

seems it is working now...

→ Ответить

6 лет назад, # ^ |

Yes,I see.

→ Ответить

Morphy

6 лет назад, # |

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.

→ Ответить

6 лет назад, # ^ |

You are a litter bit unlucky,bother. :D

→ Ответить

Davood

6 лет назад, # |

is it rated??

→ Ответить

antoshkin

6 лет назад, # ^ |

yes, only for div2

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

ZZZZZR

6 лет назад, # ^ |

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

→ Ответить

pratikwankhede

6 лет назад, # |

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.

→ Ответить

6 лет назад, # ^ |

then if I have to select a 4X4 squares

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

→ Ответить

aarcturus

6 лет назад, # ^ |

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.

→ Ответить