?detaR ti sI

6 years ago, # |

+72

Would you consider making the hacking time 6 hours instead of 12 hours as it has been discussed before.

→ Reply

kukyo

6 years ago, # |

+33

No weak pretest plz.

→ Reply

PyAlpha

6 years ago, # |

+31

Can the contest be rescheduled as it clashes with the FIFA WC 3rd Place match tomorrow? Probably delay it by 1 or 1.5 hours?

→ Reply

Ashishgup

6 years ago, # ^ |

+63

Will provide a nice breathing space after the AtCoder Grand Contest that ends 5 minutes before this contest too

→ Reply

SevenDeadlySins

6 years ago, # ^ |

Ya Plz

→ Reply

jamoniberico

6 years ago, # |

+61

How to solve div 2a?

→ Reply

just9n

6 years ago, # ^ |

+43

We got a guy from future here, peeps.

→ Reply

flygrounder

6 years ago, # ^ |

+21

It is not so easy, that we can solve it without a statement

→ Reply

jamoniberico

6 years ago, # ^ |

+12

sorry, I thought I was writing in the previous contest :(

→ Reply

Princ_iple

6 years ago, # ^ |

← Rev. 2 →

however you got +30 upvotes :D

→ Reply

Ahnaf.Shahriar.Asif

6 years ago, # ^ |

-9

just do whatever you want. you can use some convex hull tricks, or persistent data structures, just do it :)

hahah

→ Reply

Zaee

6 years ago, # |

The penalty for WA is 20 or 10?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Should be 20. I believe, this change will only affect Div.3 rounds.

UPD: I'm wrong, check later comments.

→ Reply

FieryPhoenix

6 years ago, # ^ |

What about this comment?

→ Reply

6 years ago, # ^ |

+27

Okay, sorry for misleading information then, I wasn't notified of it. Then it's 10 minutes.

→ Reply

ouuan

6 years ago, # |

I can watch Hataraku Saibou right after this contest! It's great!

→ Reply

6 years ago, # ^ |

My hero academia too

→ Reply

ouuan

6 years ago, # ^ |

Now I can enjoy it.

→ Reply

ez_zh

6 years ago, # |

Educational WorldCupForces Round!

→ Reply

dxymaster2002

6 years ago, # |

-32

?detaR ti sI

→ Reply

dxymaster2002

6 years ago, # |

-29

?detaR tI sI

→ Reply

masterbios

6 years ago, # |

Minimize hacking phase to 6 hours

→ Reply

Ghazoo

6 years ago, # |

+14

→ Reply

indian_luftwaffe

6 years ago, # |

awoo What will be the penalty in this round, 10 or 20 ?

→ Reply

raja1999

6 years ago, # ^ |

It is 10,read this comments.

→ Reply

lolxxx

6 years ago, # |

its reated? lol OALollolol xDXDxD :)))))))))))))))))))

→ Reply

Wael.Al.Jamal

6 years ago, # |

-42

btw :: How to solve div2 D,E?

in this contest yes .

→ Reply

nirvana

6 years ago, # ^ |

← Rev. 2 →

Not sure if this comment meant to gain upvote like before or to gain more downvote so he could be on the last page of contribution rank.

Edit : he's already on the last page !

→ Reply

solvemproblr

6 years ago, # ^ |

Maybe he is trying to be on the last place.

→ Reply

_FariD_

6 years ago, # |

-23

Why Codeforces (Contest writer) doesn't mention directly that this Educational Round will be rated for Div 3 participants also? As they mention "Rated for Div 2" directly.

→ Reply

6 years ago, # ^ |

+36

¯\_(ツ)_/¯

→ Reply

6 years ago, # ^ |

+22

div3 is a subset of div2 maybe that's why who knows

→ Reply

tafit3

6 years ago, # ^ |

← Rev. 2 →

IMHO whether the round is rated and for which divisions should be an attribute of the contest like "Writers", "Start" and "Length", and not be part of the "Name" of the contest.

→ Reply

6 years ago, # ^ |

Using the same logic, Why he didn't mention that it is unrated for Div. 1 participants also? Maybe because they are smart enough to know the contest is unrated for them.

→ Reply

__noob__

6 years ago, # |

Penalty Time??

→ Reply

MikeMirzayanov

6 years ago, # ^ |

+15

→ Reply

TheOneYouWant

6 years ago, # |

When you want to take part badly but your laptop's display broke 3 hours before the contest :(

→ Reply

xdc2017

6 years ago, # |

-66

problem E is too poisonous,i mod 10^9+7 instead of 998244353.

→ Reply

6 years ago, # ^ |

+38

Well, it's even somewhat bold in the statement. And also repeated a couple of times. Should be noticeable.

→ Reply

6 years ago, # ^ |

But why though? Why did you choose this mod?

→ Reply

6 years ago, # ^ |

+41

Well, there are two reasons.

The first is that nowadays problemsetters tend to choose this modulo for all problems (not only ones requiring modular FFT) so that people don't see this modulo and instantly react like "Ok, we need a convolution here".

And the second reason is that, when I started preparing this problem, I didn't understand that there is a simple math solution, and tried to solve it with online modular FFT instead xD

→ Reply

6 years ago, # ^ |

Makes sense now. Thanks =D

→ Reply

killer_god

6 years ago, # ^ |

Hey why wouldn't you use mod 10^9+7 for fft as well?

→ Reply

latvian

6 years ago, # |

← Rev. 2 →

-21

OEIS is your friend for Problem E : link

Edit: this sequence gives the number of occurences of each element in reverse order (last one occurs 1, second to last 3 times etc.)

→ Reply

6 years ago, # ^ |

aah shit

→ Reply

reeWorld

6 years ago, # ^ |

← Rev. 2 →

But 40343744 ??? I think that problem E require another sequence 40349064

UPD: sorry, my wrong, I just forgot about modulo

→ Reply

lrvideckis

6 years ago, # ^ |

Not sure why this is being downvoted, I found the exact same sequence online during the contest.

A fairly common problem solving technique: 1) write naive solution 2) find pattern (possibly look online) 3) hard code in formula

→ Reply

Ahs_58

6 years ago, # |

What is the 5th test case for problem C?

and someone also give me some hard test case for this problem.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

It's a greedy problem.

→ Reply

Scandium

6 years ago, # ^ |

This one is for B.

→ Reply

6 years ago, # ^ |

Sorry, Updated!!

→ Reply

JovanB

6 years ago, # ^ |

In your code, "sum" overflows for very large N.

→ Reply

Ahs_58

6 years ago, # ^ |

JovanB

now i have also tried by long long int instead of double.but i am getting WA at 5th test case :(

→ Reply

JovanB

6 years ago, # ^ |

← Rev. 2 →

N should be long long, because even if sum is long long, (N*(N+1))/2 is int, and can go up to 10^10, which is bigger than the limit for int

→ Reply

6 years ago, # ^ |

Make n also long long int. You have ll sum = (n*(n+1))/2 but n is an int — the overflow will happen first so sum will end up with a weird value for large enough n.

→ Reply

jamienguyen

6 years ago, # ^ |

Small datatypes may overflow, so long double should fix the problem.

→ Reply

Scandium

6 years ago, # |

← Rev. 2 →

For problem C, Why my solution failed? http://codeforces.me/contest/1009/submission/40348123

Edit: Failed on pretest 5

→ Reply

WolfBlue

6 years ago, # ^ |

n is an int up to 10^5 and you are doing n*(n+1) when you calculate beech

→ Reply

6 years ago, # ^ |

One obvious reason is overflow. You have beech = n*(n-1), but n is an int. See what happens when n = 100000 or n = 99999.

→ Reply

Chilli

6 years ago, # |

I've been really enjoying this series of contests, but out of curiosity, wouldn't it be better advertising to create Div 1 rounds? I'd love to go to the camp, but considering how far away I am from making ACM worlds, it's hard to justify the expense.

I think Div 1 participants are more likely to take the plunge and spend 1000+$ and a week away from school.

→ Reply

WolfBlue

6 years ago, # |

← Rev. 2 →

+26

A very good contest with a very smooth difficulty curve, not an easy thing to make. Good job to the writers

→ Reply

6 years ago, # |

When can we submit?

→ Reply

Ashishgup

6 years ago, # |

+61

Taking strong tests to another level :P

→ Reply

6 years ago, # ^ |

+110

There are actually 130 tests in this problem.

It was originally used in Saratov SU trainings a few days ago, and there was a man who managed to receive RE 130.

→ Reply

rtanmay

6 years ago, # ^ |

← Rev. 3 →

How can one get RE at 131 if there are only 130 test cases? Am I missing something?

→ Reply

6 years ago, # ^ |

Successful hacks are added to the testcases for systests, so there are 130 pretests + any successful hacks.

→ Reply

rtanmay

6 years ago, # ^ |

Oh so thats why. I didn't knew that before. Thank you

→ Reply

dalex

6 years ago, # ^ |

-15

Yeah, strong tests in tree problem without test "1-2-3-...-N". This is Educational round.

→ Reply

kayak

6 years ago, # |

← Rev. 3 →

Can somebody explain why my code for E got TLE in Test Case 9 (though I think it's O(n)) and for C got WA in test 5 ?

Intercity Travelling

#include<iostream>
using namespace std;
const long int prime = 998244353;
const long int N = (1e6)+7;
long long int coeff[N] = {};
void precompute(){
    coeff[0] = 1;
    long int mul = 1;
    for (int i = 1; i< N; i+=1){
        long long int jk = (2*coeff[i-1] + mul)%prime;
        coeff[i] = jk;
        mul = (mul*2)%prime;
    }
}

int main(){

    int n; cin>>n;
    int arr[n];
    precompute();
    for (int i = 0; i<n; i+=1){cin>>arr[i];}
    unsigned long long int sum = 0;
    for (int i = 0; i<n; i+=1){
       unsigned long long int foo = (arr[i]*coeff[n-1-i])%prime;
       sum = (sum + foo)%prime;
    }
    cout<<sum;
    return 0;
}

Annoying present

#include<iostream>
#include<iomanip>
using namespace std;
long long int mini(int n){
    if (n%2 == 0){
        int k = n/2;
        long long int x = k*k;
        return x;
    }
    else{
        int k = n/2;
        long long int x = k*(k+1);
        return x;
    }
}
long long int maxi(int n){
    long long int y = (n*(n-1))/2;
    return y;
}
int main(){
    cout<<setprecision(16);
    int n, m; cin>>n>>m;
    long int neg = 0, pos = 0;
    long int sx = 0;
    for (int i = 0; i < m; i+=1){
        int x, d; cin>>x>>d;
        sx += x;
        if (d < 0){
            neg += d;
        }
        else{
            pos += d;
        }
    }
    long double foo = (long double)neg*mini(n)/n;
    foo += (long double)pos*maxi(n)/n;
    foo+= (long double)sx;
    cout<<foo;
    return 0;
}

→ Reply

6 years ago, # ^ |

For C: check overflow. You're multiplying two ints and storing the result in a long long. Overflow happens before the storing does.

→ Reply

kayak

6 years ago, # ^ |

← Rev. 2 →

Thanks for finding the error in both the codes :)

→ Reply

6 years ago, # ^ |

For E: You're reading 10^6 numbers using cin. Speed it up with ios::sync_with_stdio(0) and cin.tie(0) or use printf/scanf.

→ Reply

Lelouch

6 years ago, # |

Could someone please explain why this code doesn't work for problem D? http://codeforces.me/contest/1009/submission/40345268

Here's the approach I used —

Since the graph has to be connected, the M has to be >= N-1 otherwise impossible. I then proceeded to take the sum of all phi(n) from 1 to N (phi(n) being the Euler Totient Function). If this sum >= M, I then use sieve to create the graph.

I started matching 1 to all nodes from 2 to N, thus making the graph connected. This meant I had M — N + 1 edges left to add. I used sieve to find relatively prime numbers and as soon as the count of edges hit 0, I returned 0 and proceeded to print the graph.

I would really appreciate a counter-test so that I know where I was going wrong. Thank you!

→ Reply

Diegogrc

6 years ago, # ^ |

I tried 20 45 and the last edge you print is 4 10. GCD( 4 , 10 ) = 2. Hope this helps

→ Reply

6 years ago, # ^ |

Looks like you're just counting multiples of a number as non-coprime with it, which is only true for primes — not composite numbers. Try 6 11. You print 4 6.

→ Reply

Firastic

6 years ago, # ^ |

For every x, sieve will only delete every multiple of x (not relatively prime of x). So your sieve will delete every multiple of x, add every y where y is not multiple of x, and readd every multiple of x

→ Reply

Lelouch

6 years ago, # ^ |

← Rev. 2 →

Got it, thank you Diegogrc, IceKnight1093 and Firastic! I'll upsolve this now.

→ Reply

starboy_jb

6 years ago, # |

Educational.....

→ Reply

6 years ago, # |

← Rev. 2 →

I don't know why I was getting TLE on test case 6 on problem C here. The time complexity looks linear to me. Maybe the logic for the problem I am using is wrong. But stil I shouldn't get TLE as I guess the complexity of the code I am using is O(n). Can someone explain both the logic and the problem with my code?

→ Reply

MijPeter

6 years ago, # ^ |

I'm not sure but i think your arrays are too small (10000 instead of 100000).

→ Reply

6 years ago, # ^ |

Damn! I also figured that out like a minute ago and yeah the array size is small. I just missed it literally by a '0'. It's frustrating. But the contest was really good. Hats off to problem writers!.

→ Reply

6 years ago, # ^ |

So if there is a segmentation fault then TLE is given as error on codeforces right?

→ Reply

djm03178

6 years ago, # ^ |

It means it failed to meet the segmentation fault. Instead, it probably got into an infinite loop by changing the value of nearby variables (i.e., 'i' or 'm'), therefore getting TLE from it.

→ Reply

Linkus

6 years ago, # |

+32

Great difficulty balance of the problems, shoutout to the writers!

→ Reply

jugol

6 years ago, # |

Oh.... I fall a trap in Problem B and got confused a lot on that problem

→ Reply

Azurey

6 years ago, # |

How to solve B?

→ Reply

jugol

6 years ago, # ^ |

1011201120112 is 0111111120202

→ Reply

BeardAspirant

6 years ago, # ^ |

greedy doesn't work? I am getting the same soln but still dreaded test case 4 fails

→ Reply

forgotter

6 years ago, # ^ |

It works perfectly. my submission : http://codeforces.me/contest/1009/submission/40342688

Greedy doesn't mean that you put all small values before bigger ones, we have to do so but under some constraints.

Explanation of my solution: Maintain a reverse_ans string, initially null.

Start from last, if there is a '0' or a '1' increase the counter for '0' or '1. If there is a '2', we know that we can't shift any '0' beyond this point, so first put all found zeroes to reverse_ans and reset its counter and now put '2' in reverse_ans.

Important step (greedy but different to what is done above)

At the iteration is over, first put all '1' to reverse_ans and then all zeroes.

reverse the reverse_ans and print it.

→ Reply

BeardAspirant

6 years ago, # ^ |

what I thought was get all 21 and convert to 12 and 10 to 01. The only exception to this rule was 201 which becomes 120. run this till I have no 201, 21 or 10 in my string. this soln fails and I want to know why or what test case am I missing.

→ Reply

forgotter

6 years ago, # ^ |

2121111111111111111111111111111(up to 10^5 length)

If you look for all occurrences of "12" or "21", you should get a TLE.

For WA, 0000212000001 Answer : 0000112200000

→ Reply

latvian

6 years ago, # ^ |

Put all '1' s just before first "2". 012012 becomes 011202 , whereas your code gives 012012

→ Reply

jugol

6 years ago, # ^ |

so, count '2' and '0' from first '2' and put them back of the string with same order. fill the rest of numbers 1

→ Reply

6 years ago, # ^ |

← Rev. 3 →

count 1 in string then count 0 before any 2 comes then print 0 as per count then print all 1, then just print 0/2 as they come in string. for eg. 101201120 becomes 011112020

→ Reply

killer_god

6 years ago, # ^ |

Maintain the order of 0's ans 2's. Take all 1's and put them just before 1st occurence of 2.

→ Reply

Ali_Pi

6 years ago, # |

+33

1:59:59 :D

→ Reply

Heart_Blue

6 years ago, # ^ |

← Rev. 3 →

Amazing

But what's more Amazing is that you just submit the first 3 problems in 3 minutes

→ Reply

Medusa

6 years ago, # |

Cool problems, thanks to round authors.

why is this recurrence wrong for E?

$\text{[math]}$

where dp[0] = 0 and a[i] is the prefix sum. I can use fenwick tree for prefix sum but why logic error? I am choosing the rightmost stop and then I calculate difficulty for remaining sub problem.

→ Reply

6 years ago, # ^ |

This recurrence is wrong because it doesn't take probabilities into account.

For example, suppose you are analyzing 4-th kilometer and trying to find a closest rest stop before it. The probability that it will be on position 3 is 0.5, the probability that it is on coordinate 2 is 0.25, and so on. So we can't just sum all these dp values up, we need some coefficients.

→ Reply

JettyOller

6 years ago, # |

How to solve E ?

→ Reply

Doriath

6 years ago, # ^ |

← Rev. 3 →

Note: I didn't actually solve E but I got the problem right after contest ended...

The answer is: $\text{[math]}$

where

P[i] = 2^{N - i - 1}·(N - i + 2) for i = 1...N-1

P[N] = 1 (technically same as above but 2^- 1 is fractional)

mod MOD at each step of course

I used brute force to find array for first 10 numbers and entered the list into OEIS

edit: off by 1

→ Reply

6 years ago, # |

← Rev. 2 →

Why this got MLE 40349306 and this didn't 40349677? Very strange, how much memory deque uses...

→ Reply

6 years ago, # ^ |

stl deque many times proves inefficient for many problems in time n memory usage

→ Reply

chemthan

6 years ago, # ^ |

I think .clear() doesn't free memory. Could you try delete operation?

→ Reply

Mikaeel

6 years ago, # |

+10

NEVEEER USE DEQUE If you don't like to get MLE :(

→ Reply

6 years ago, # ^ |

SAAAME

→ Reply

ay2306

6 years ago, # ^ |

I use them. Never experienced ML till now because of them.

→ Reply

XORier

6 years ago, # |

problem B was very good!

→ Reply

6 years ago, # ^ |

With a greedy taste.

→ Reply

bluecoffee8

6 years ago, # |

Huh. For problem E if you use cin, you get TLE on test case 7, but if you use scanf you get AC :O

→ Reply

dlwocks31

6 years ago, # ^ |

try using ios::sync_with_stdio(false);cin.tie(NULL);. It can boost up speed of cin/cout to that of scanf/printf. See 40351502

→ Reply

bluecoffee8

6 years ago, # ^ |

oh i used scanf during contest

→ Reply

yashgulani

6 years ago, # |

← Rev. 3 →

In D problem even the custom invocation is showing possible but the test case 18 is giving Impossibe for my code Please check out this solution http://codeforces.me/contest/1009/submission/40348587

Same Code gets submitted after ccontest http://codeforces.me/contest/1009/submission/40350442

OOps figured out n*(n-1) crossed int limit

→ Reply

6 years ago, # ^ |

Looks like your solutions just overflows in m>(n*(n-1)/2).

→ Reply

6 years ago, # ^ |

The problem with the first one was overflow: you were comparing m with (n*(n-1))/2 where n was an integer. If n is large enough the product will overflow and become negative. Second submission doesn't have that comparison so it passed.

→ Reply

Taran106

6 years ago, # |

For C i used double instead of long double to store (double)total_sum / n. Can it cause wrong ans in main test due to precision issue?

→ Reply

XORier

6 years ago, # ^ |

← Rev. 3 →

-7

double ans = (double)sum/n

ans might overflow, you should've typecasted sum to long double!

→ Reply

6 years ago, # ^ |

sum will not overflow, it's about O(n³·maxn) which is smaller than 10¹⁸

→ Reply

XORier

6 years ago, # ^ |

← Rev. 2 →

I meant after typecasting long long int to double it might overflow!

Updated!

→ Reply

Linkus

6 years ago, # ^ |

No, it should be okay.

→ Reply

_Dark_Shadow_

6 years ago, # |

Today's D was easier (till now I think) compared to the last contests. And I wasted my time to look for corner cases and if any case that will lead me to TLE. Could not get time to solve E (which had a nice pattern). Anyway, educational contests are fun than the usual ones. Though I messed up today's one badly. Did not think today's one was going to be simpler than the past.

→ Reply

Assaduzzaman_Sohan

6 years ago, # |

← Rev. 6 →

-26

...

→ Reply

6 years ago, # ^ |

We can always bring any 1 to the beginning of the string, since we can swap 1 with any other digit.

→ Reply

hayman42

6 years ago, # ^ |

because there are sufficiently many 1s in the string, the 0 and 2s have become invisible after the moves.

→ Reply

hayman42

6 years ago, # |

guys someone sent me a message which asks me to help him solve C and that he will help me solve B. Fortunately I was not noticed with that message during the contest and as you guys can see I ended up without solving B and after the contest i solved it by myself. My question is: how can I report him for cheating?

→ Reply

tokitsukaze

6 years ago, # |

← Rev. 2 →

+19

In the test 11 of problem C:

Checker comment ok found '621354311313.3487500', expected '621354311564.2170400', error '0.0000000'

Why is the output correct?

→ Reply

6 years ago, # ^ |

+12

Its relative error is smaller than 10^- 6

→ Reply

6 years ago, # ^ |

In terms of relative error, it's correct.

If it is stated that "Your answer is considered correct if its absolute or relative error doesn't exceed 10^- x", then checker considers the minimum of absolute and relative errors.

→ Reply

pk842

6 years ago, # |

how to solve D?

→ Reply

6 years ago, # ^ |

Run two loops(1 to n and from i+1 to n)and calculate gcd (i,j)if it is 1 then print as m can be atmost 100000 so the both loop terminates after m iteration. And if n>m-1 you have to print impossible as the graph then can't remain connected

→ Reply

pk842

6 years ago, # ^ |

"as m can be atmost 100000 so the both loop terminates after m iteration" can you please prove it or can give some intuition behind it?

→ Reply

6 years ago, # ^ |

It's not true, using this method at least. Since every pair is being checked, even those with gcd(i, j) != 1 will be checked, leading to more than m iterations in total.

→ Reply

6 years ago, # ^ |

for(int i=1;i<=100000 && al.size()<=100000;i++){
        for (int j = i+1; j <=100000 && al.size()<=100000; j++) {
            if(gcd(i,j)==1){
                al.add(new pair(i,j));
            }
            x++;
        }
    }

x came out to be 100002

→ Reply

6 years ago, # ^ |

← Rev. 3 →

The worst case for this will actually be with a somewhat smaller n but large m. Maybe something like n = 10000, m = 100000 will work, I haven't tested exactly. If n is very large, most of the edges will come very quickly since you get n-1 from 1, and 2 and 3 are both prime. Only when you need i to go fairly high (and be composite) do you start getting less edges added per iteration.

Edit: n = 10000 and m = 100000 gives x = 161528. This algorithm is probably going to be fast enough, but certainly not going to stop in exactly m steps.

→ Reply

dmkz

6 years ago, # ^ |

← Rev. 2 →

The ratio of number of relatively prime pairs (i, j) that 1 ≤ i ≤ j ≤ n and all pairs is:

$\text{[math]}$

Probability of coprimality. We can generate random pairs using uniform distribution and choose only $ m $. In C++ I used std::uniform_int_distribution, std::mt19937 and my hastable and got accepted.

→ Reply

6 years ago, # ^ |

+13

Given n, the number of possible edges is basically all those (unordered) pairs (x, y) such that x, y ≤ n and gcd(x, y) = 1 and x ≠ y. This number is simply φ(1) + φ(2) + ... + φ(n) - 1, where φ is the totient function. (subtracting 1 since we can't have the pair (1, 1).

This gives us 2 edge cases: if m is greater than this number or m < n-1 it's not possible to create such a graph — either it won't be connected or there won't be enough edges.

In every other case, it's possible. Connect 1 to every other node first to connect the graph. Then, for each pair (i, j) such that gcd(i, j) = 1, i ≤ j, 1 < i, j ≤ min(n, 600) you have one edge. 600 because φ(1) + ... + φ(600) > 100000 so you're guaranteed to have enough edges with just that.

→ Reply

pk842

6 years ago, # ^ |

nice observation! and thanks a lot.

→ Reply

ay2306

6 years ago, # ^ |

In D, the most important task was to check possible or not because other than that, we just need to output co-primes together.

In order to check co-primes of available, you just need to implement Euler's totient function. Thus in O(n), we can check possibility or not.

We could have stored this value in a vector to check is total count is greater than required and n-1 as well. But that can bring TLE for large cases.

Submission

→ Reply

https://codeforces.me/blog/entry/44351

6 years ago, # |

How to solve F? Can it be done in O(NlogN) or O(N)?

→ Reply

YogayoG

6 years ago, # ^ |

→ Reply

6 years ago, # ^ |

Do dfs on a tree, and for every node x, you can find the array d(x). You can make it in O(nlogn) if you merge there arrays carefully. MLE solution: 40349306 Correct: 40349677

→ Reply

6 years ago, # ^ |

This technique is called dsu on tree?

→ Reply

6 years ago, # ^ |

Idk, I just call it merging vectors on trees.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

In fact, we can even make it O(n) if we merge the structures for subtrees not according to their sizes, but according to their heights (merge lower subtree to higher).

→ Reply

6 years ago, # ^ |

Can you explain this, how to merge in O(n)?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

It seems that 40349677 (if I understood the code correctly) actually uses this method of merging in O(n). You just need to do the same things you do in standard small-to-large approach, and it "magically" works in O(n) time if the size of subtree's structure is proportional to its height (and merging two structures can be done in time proportional to the size of a smaller structure).

A more detailed explanation, proof and my implementation will be in editorial.

→ Reply

6 years ago, # ^ |

Okay , thanks!

→ Reply

coquillage

6 years ago, # |

Can someone confirm if everything is okay with Problem-D ? My solution SEEMS to be working well on my system but failed pretest number 3.

→ Reply

coquillage

6 years ago, # ^ |

Turns out my solution was wrong. Sorry.

→ Reply

lnzva

6 years ago, # |

← Rev. 2 →

Obviously http://codeforces.me/contest/1009/submission/40351881 submission will eventually fail, because of taking limit small, but I can't for the life of me figure out why it is getting wrong answer on test case 4. Could someone please help me out? Every single thing besides considering number of nodes(which should in no way be a cause of getting wa at this test case) seems fine in here to me and yet I'm getting WA on F, test case 4

→ Reply

6 years ago, # |

Can anyone tell why my solution got hacked after passing the preliminary tests here

→ Reply

6 years ago, # ^ |

Maybe using long double instead double will help?

→ Reply

6 years ago, # ^ |

long double where?

→ Reply

6 years ago, # ^ |

cout<<fixed<<setprecision(8)<<(long double)su/n;

→ Reply

6 years ago, # ^ |

I tried, still, it got hacked :(. My solution here. Any idea what the failed test case might be?

→ Reply

Vsevolod_Kaplin

6 years ago, # ^ |

← Rev. 2 →

The answer can be up to 5.0005 * 10^12 * 10^5 = 5.0005 * 10^17 — when n, m = 10^5, all x = 1000 and all d = 1000. So 8 digits isn't enough.

→ Reply

6 years ago, # ^ |

Please try this test: 3 1 0 -1 The answer must be -0.6666667

→ Reply

6 years ago, # ^ |

if d<0 we need to take into consideration 2 cases: n is odd and n is even. 40355675

→ Reply

6 years ago, # ^ |

It's working now and I got it. I just considered the case of n is odd. Thanks a lot!.

→ Reply

6 years ago, # ^ |

You're welcome! Good luck!

→ Reply

Arkcy

6 years ago, # |

+36

Maybe it's one of the simplest solutions on problem E.

#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
int n,x,l,s;
int main(){
	cin>>n;
	while(n--){
		l=(l*2%p+x)%p;
		cin>>x;
		s=(s*2%p+l+x)%p;
	}
	cout<<s;
}

→ Reply

6 years ago, # |

In Problem D . I tried to use totient function to find out if it's possible or impossible to form the graph. And then just printed out the no whose __gcd(i,j) == 1. Is this approach correct although I'm getting wrong answers . Am I missing some vertices? http://codeforces.me/contest/1009/submission/40351068

→ Reply

Arkcy

6 years ago, # ^ |

The graph should be connected.So your solution got wrong when m<n-1

→ Reply

https://en.wikipedia.org/wiki/Coprime_integers#Generating_all_coprime_pairs

6 years ago, # ^ |

So what's the correct procedure to print?

→ Reply

Arkcy

6 years ago, # ^ |

You are supposed to print "Impossible" when m<n-1,since in that case you can't connect all n vertices within m edges.

→ Reply

Shutterbug

6 years ago, # ^ |

← Rev. 7 →

Yes, 3 things-

1) Your graph is not necessarily connected so include all the edges of type 1 i ,i>=2

2) Check condition for p>=m and m>=n-1 in your if part

3) Run loop only till 600 because summation of euler function is >100000 for 600 i.e upto 600 you will get enough edges to make the graph connected satisfying condition for m edges.

→ Reply

Zaee

6 years ago, # |

+62

Can't be more accurate

→ Reply

Redux

6 years ago, # |

Recurrence for generating coprime pairs for D.

→ Reply

http://mathworld.wolfram.com/RelativeError.html

6 years ago, # ^ |

This works, but wouldn't there be any overlapping cases ?

→ Reply

Redux

6 years ago, # ^ |

It says that "This scheme is exhaustive and non-redundant with no invalid members" so it shouldn't produce overlaps.

→ Reply

wery0

6 years ago, # |

Sequence A001792 in OEIS for task E.

→ Reply

Diegogrc

6 years ago, # |

-8

Was the evaluator for problem C correct? My solution ( 40334143 ) got hacked after the contest, and after checking the test cases that were ok i found something weird. In Test 11 my answer was off by more than 100 and the evaluator returned ok. Is this a problem with the evaluator? I believe this shouldn't happen

→ Reply

yassin_

6 years ago, # ^ |

→ Reply

2014CAIS01

6 years ago, # ^ |

In terms of relative error, it's correct

→ Reply

jkeyser

6 years ago, # |

None of this matters much, but I'm curious how the standings and problems solved vary during the hacking phase. I understand that as solutions get hacked, people lose credit for problems, so their ranking would go down. That means that if you don't have a solution hacked, your rank tends to get better. And, the dashboard generally shows fewer of each problem solved, as solutions get hacked.

But, I've also seen my ranking get worse (without having a solution hacked) at some points during the hacking phase — generally just a little bit — maybe 10 places. And, I occasionally see the number of solved problems go up during the hacking phase. I imagine the number solved might include people submitting them afterward, but presumably that doesn't affect ranking. Any ideas how this is happening?

→ Reply

6 years ago, # ^ |

Virtual participators.

→ Reply

6 years ago, # ^ |

Uncheck the checkbox stating "show unofficial" on top right corner of Standings page.

→ Reply

subhamastoo

6 years ago, # |

In today's contest I saw many solution of C got hacked,after the hacking phase could anyone please state in what case many of the contestant's solution went wrong.

→ Reply

__TooLazy

6 years ago, # ^ |

most of them have kept of datatype of sum variable as double which will overflow for large values x and d when summed across m queries.So use long double instead!!

→ Reply

6 years ago, # ^ |

I also have used double, but when I tried to hack my solution by putting maximum constraints, even then it passed the test.

→ Reply

_Dark_Shadow_

6 years ago, # ^ |

+17

I used long long. Still no hack. And a lot of used long long. long long sum and then cout << fixed << setprecision (10) << (double) sum / n * 1.0 << endl;

This seems to work fine. So, I am curious about what the hack case is.

→ Reply

AceIn

6 years ago, # ^ |

← Rev. 3 →

I see that Test #11 says "ok found '621354311564.2196000', expected '621354311564.2170400', error '0.0000000'". Umm why is this? Edit: Sorry for the mistake, I just found out that it is the relative error.

→ Reply

subhamastoo

6 years ago, # ^ |

Yeah I just checked the sizes of double and long double.Double is of 8 bytes while long double is 16 bytes on C++ 14. I kind of had a misconception both were of 8 bytes,but now I see those were for older versions.

→ Reply

Vsevolod_Kaplin

6 years ago, # |

Can somebody please explain how double in C++ works? I was sure it takes 8 bytes and has diapason from -9 * 10^18 to 9 * 10^18. Where am I wrong?

→ Reply

ljupche98

6 years ago, # ^ |

+11

Double (and other data types for real numbers) can have precision errors. The numbers in computers are represented by bits. Int takes 4 bytes, long depends on the OS, long long 8, float 4, double 8 and so on.. Check this link for more information: https://www.tutorialspoint.com/cplusplus/cpp_data_types.htm

I think you know that int data type is limited to values between -2^31 to (2^31 — 1). In that range, there are exactly 2^32 different numbers which is the maximum we can represent with 32 bits. Float is a data type for real numbers and its size is 4 bytes (same as int). That means, we have 32 bits and we can represent at most 2^32 different values. We know that float can be used to represent some real numbers which we cannot represent with int. That means for one real number, we have used one of those 2^32 combinations for its representation. Then if we try to represent every possible integer in the int range, there will be some numbers whose int and float values will be different. Thus those floats will be rounded to another value.

Real numbers can be represented with the IEEE 754 standard. You can Google it for more information if you want to see how it works. That representation, allows us to represent very high numbers (I think it’s something like 10^308). But, we can only represent 2^size different numbers where size is the size of the data type in bits.

I explained you about float, and I hope you understand what’s the problem with those representations. It’s similar for double, its length is just 8 bytes.

Try the following program. An example of an integer that gets rounded when represented by double.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

int main()
{
    ll x = (1LL << 61) + 13213124123213213LL;
    db y = (db) x;

    cout << fixed;
    cout << x << endl;
    cout << y << endl;
    return 0;
}

And since some integer numbers get rounded by real data types, it’s also true that some real numbers will get rounded as we don’t have infinite precision. And if your program rounds the number many times, you may get wrong answer verdict for some example.

I fixed your program: http://codeforces.me/contest/1009/submission/40360084 My advice is, try to use as less real data types as possible. In line #13, you were using double to calculate a number which can be as big as 10^10 (= (10^5)^2) and as I explained you, it’s a bad idea.

→ Reply

Vsevolod_Kaplin

6 years ago, # ^ |

Thank you very much!

→ Reply

srijan123j

6 years ago, # |

+33

halyavin is doing wonders!!! What a hacker!!

→ Reply

6 years ago, # ^ |

True hacker

→ Reply

6 years ago, # ^ |

That's system testing in disguise

→ Reply

6 years ago, # |

I think that for C the judge should be made with integers, because it can be not fair sometimes.

→ Reply

vaibhavvg

6 years ago, # |

After how many hours does system testing start for educational CF rounds?

→ Reply

6 years ago, # |

+12

Where's editorial?

→ Reply

ksohan

6 years ago, # |

Can anyone please tell me what is wrong with this 40362288 ?

40362440 This one gives me AC. The Only difference is I have declared the variable sum as long long is this submission and as double in the previous submission ? How can this give me wrong answer ?

→ Reply

parimal7

6 years ago, # |

Can someone help me with problem A? My solution passed all test cases yesterday but now it shows wrong output on test case 9, but on my machine the output matches correctly with the answer.40325412

→ Reply

MesbahTanvir

6 years ago, # ^ |

← Rev. 2 →

Before accessing any kind of container (queue,stack,set etc.) You should always check either it empty or not.

→ Reply

6 years ago, # ^ |

Use this as condition

if(!wallet.empty() && arr[i]<=wallet.front())

→ Reply

masterbios

6 years ago, # |

← Rev. 2 →

how did halyavin hack 600+ in 12 hours manually?

→ Reply

6 years ago, # ^ |

You still think he did it manually

→ Reply

scoobydoo

6 years ago, # |

I don't understand why my solution got Hacked

→ Reply

chielo

6 years ago, # ^ |

double has problems with precision. For example, calculating 1e18 - 1 - 1e18 sequentially results in 0.0 instead of -1.0.

View test provides the generator of the hack. It constructs a general input hacking all solutions that accumulate the answer with double.

→ Reply

scoobydoo

6 years ago, # ^ |

thanks!!! and can you suggest how can I tackle this problem

→ Reply

chielo

6 years ago, # ^ |

The answer before being divided by n won't exceed mn²(d + x) about 1e18. Thus int64 (long in Java?) is efficient to store the answer. Then you can output the answer divided by n in double.

→ Reply

scoobydoo

6 years ago, # ^ |

thanks!!! finally got Accepted

→ Reply

6 years ago, # |

Can anyone tell if my submission for problem C is correct or not? Whether it will pass the tests used in the hacking. http://codeforces.me/contest/1009/submission/40330305

I used double in the end for division and before that used long long to store the sum. Can’t double store till 10^18?

→ Reply

normit

6 years ago, # |

← Rev. 2 →

I didn't understand problem F.

How depth array of vertex 1 of example 1 look like?

I thought it would be {0, 1, 1, 1, 0, ...} and the dominant index would be 1 but 0.

Is a vertex an ancestor of itself?

→ Reply

raja1999

6 years ago, # ^ |

It depends on how we define i guess. I think it should have been specified to consider a vertex as ancestor of itself,but by looking at the sample tests you can get it.

→ Reply

halyavin

6 years ago, # ^ |

Yes, vertex is an ancestor of itself in this problem.

→ Reply

ljupche98

6 years ago, # ^ |

The array is actually [1, 1, 1, 1, 0, 0, ...]. The first element is 1 because (by definition) there is one vertex so that the simple path between 1 and y contains 0 edges. Path with 0 edges means its the vertex itself, so it's 1. And yes, the vertex is its ancestor. The same is true any other vertex, so the array always starts from 1.

→ Reply

normit

6 years ago, # ^ |

Thank you all for kind reply.

During the contest, I was searching the definition of ancestor over and over... to understand example

→ Reply

Odin-

6 years ago, # |

Great contest

→ Reply

caojielong

6 years ago, # |

can you tell me why my submission 40370101 is WA at test 39?PLz PLz PLz

→ Reply

6 years ago, # ^ |

← Rev. 3 →

precision error,use long double or change approach slightly and use int64

→ Reply

ay2306

6 years ago, # |

Can someone list what should I study to solve C, E and F. Thank you.

→ Reply

6 years ago, # |

Where's editorial ?? Also what's the approach of E? Or should we just use OEIS to find the pattern?

→ Reply

Jakube

6 years ago, # ^ |

The editorials for educational rounds are always really late. Probably will take a few more hours/days. :-(

E is just dynamic programming. Find a recursion for dp[i] = sum of all path between 0 and i. Hint: think about the location of the last rest site.

→ Reply

6 years ago, # ^ |

Editorial will be published in 4-5 hours, sorry for the delay.

→ Reply

Vinhspm

6 years ago, # |

How to solve F with dsu?

→ Reply