Codeforces Round #453 (Div. 1 & Div. 2)

7 years ago, # |

← Rev. 2 →

Welcome to the world of extremely unoriginal problems, awkwardly long and boring statements and trifling jokes in anouncements.

sees some problems from his past contests

Okay I'm bracing myself :D

→ Reply

aiwprton

7 years ago, # |

+69

Isn't this clashing with Topcoder SRM 726 ?

→ Reply

PriyamV_181

7 years ago, # |

+27

how many number of problems will be there?

→ Reply

21August

7 years ago, # |

-55

FUCK TC SRM. It is clashing with cf round so no way i'm missing it!!!

→ Reply

lolzano

7 years ago, # |

+40

hope for no long queues. c:

→ Reply

M_H_H_7

7 years ago, # |

-48

awkwardly long problems??? why??? ):

→ Reply

M_H_H_7

7 years ago, # ^ |

-11

negative comment seriously? do you really like them?:D

→ Reply

7 years ago, # |

+111

Nooooo... CF and SRM are clashing :/??? Seriously?

→ Reply

HOMIARA_RUBY

7 years ago, # ^ |

Hope either Codeforces or Topcoder will change starting time as soon as possible.

→ Reply

7 years ago, # ^ |

+45

Unfortunately, when we announced this round, there was no SRM on this date on their schedule. When they announced it, it was too late for us to move this round.

→ Reply

square1001

7 years ago, # ^ |

← Rev. 4 →

Hi, I think there was Data Science Newsletter (of Topcoder) titled "It's Data Science Newsletter Time! SRM this Saturday & the 19th!" in December 9th (10 days ago) and it has a schedule — "SRM 726: December 19 at 11:00 UTC -5". And I remember that the date that announced this round was less than 10 days ago. So I think "When they announced it, it was too late for us to move this round." is not true, isn't it?

→ Reply

7 years ago, # ^ |

+28

I've put Round 453 on the schedule on the 7th. You know, it is the end of the year, we have a lot of rounds and I also have a lot of other things to finish, so wasn't able to move it, sorry about that.

→ Reply

I_Love_Tina

7 years ago, # ^ |

But that's a matter of 90 minutes, was it so hard to put the contest in the 'usual' time (19:30 MSK)?

→ Reply

7 years ago, # ^ |

+46

After SRM we can start no earlier than 21:05 MSK, it is too late. Before it we can start no later than 16:35 MSK, it is too early.

→ Reply

7 years ago, # ^ |

-22

1) So if I understand correctly following events happened in this order: a) you scheduled round on today, b) topcoder announced their SRM date, c) you announced cf date. If that's correct you can't blame them for putting SRM at clashing time.

2) 21:05 MSK is too late? Many people from Russia participate in SRM at 5:00AM MSK. Or did you mean some other issues?

→ Reply

7 years ago, # ^ |

+32

1) By scheduling I mean posting it on the public schedule at /contests which propagates to calendars and so on. So I use this word in the same meaning as announcing.

2) Yes, it is too late. Rounds are made not only for red coders who write contests even at 5:00 AM, but for everybody.

→ Reply

7 years ago, # ^ |

1) In that case I'm sorry for suggesting wrong statements.

2) IMHO 21 is perfect time to have a contest. 18 or something can always be troublesome because some people still have courses on university or work. 21 is safely after all such activities and 23 is not too late to end contest (for me, but it depends on a particular guy). And even if it is too late for some people then I guess that having two contests, one at 19MSK and second at 21 MSK is significantly better than one at 18:35 MSK and 19 MSK. Did you try contacting TC to reschedule their SRM since CF was announced first? I guess this is worse for TC than for CF, so if they value what they do they should at least consider this.

→ Reply

Geothermal

7 years ago, # |

-63

Will the rounds be rated?

→ Reply

Saidbek_Sarimsakov

7 years ago, # ^ |

+24

Maybe! It will be specified Later. Anyway, That is enough to have contest to learn and enjoy. :)

→ Reply

yashar_sb_sb

7 years ago, # ^ |

+14

Maybe semi-rated!

→ Reply

islamdidarmd

7 years ago, # ^ |

-19

Or x-rated!

→ Reply

adamant

7 years ago, # ^ |

+79

xxx-rated round, not safe for work.

→ Reply

harshits2808

7 years ago, # ^ |

← Rev. 2 →

phew...and i was worried no one's gonna ask that...XDDDDD

→ Reply

Grunt

7 years ago, # |

After retired from ACM-ICPC, I still have something to do with Codeforces, something like becoming a MASTER, just for fun. # Hello the world without training!

→ Reply

tenacious

7 years ago, # |

Intriguing announcement :D !

→ Reply

getSchwifty

7 years ago, # |

-8

Every Third Contest I do on Codeforces becomes unrated due to Server Issues / Test Cases Issues etc. FINGERS CROSSED

→ Reply

7 years ago, # ^ |

Not today, I hope :D

→ Reply

_Mr_Fab

7 years ago, # |

← Rev. 2 →

-40

I request the problem setters to restore the difficulty level of problems, the last 2 contests were a bit easier.

→ Reply

Emiway

7 years ago, # ^ |

Even then you didn't participated.

→ Reply

athin

7 years ago, # |

+325

→ Reply

7 years ago, # |

+53

adamant gonna be pulling our strings tonight (ahem).

→ Reply

getSchwifty

7 years ago, # |

+27

This was the contribution to Global Warming :) [ LOTS OF TREES ].

→ Reply

nimom

7 years ago, # |

Why can't I see other's solution to hack? Only thing I see after clicking the solution is Update adobe flash. I use chrome browser.

→ Reply

7 years ago, # ^ |

Have you tried updating Adobe Flash Player?

→ Reply

attiw

7 years ago, # ^ |

← Rev. 2 →

I too cant hack after locking the problem. I have all the tools installed

→ Reply

Azret

7 years ago, # ^ |

Try Firefox

→ Reply

we7d

7 years ago, # ^ |

maybe flash is disabled in chrome, click the circle near codeforces url and allow flash.

→ Reply

ChickenInKitchen

7 years ago, # |

How to solve Div1 C?

→ Reply

7 years ago, # ^ |

+28

for each i , find smallest j such that [i,j] induced subgraph has a cycle , to do that , build a max spanning tree(weight = min(i , j) for an edge i <-> j) , now its just some path queries.

→ Reply

RestingRajarshi

7 years ago, # ^ |

thought this. couldnt implement in time. sad.

→ Reply

ChickenInKitchen

7 years ago, # ^ |

nice !

→ Reply

TooWeak_TooSlow

7 years ago, # |

How To Solve Div2 Problem A? Can anyone Explain?

→ Reply

Vsevolod_Kaplin

7 years ago, # ^ |

Maybe I can.

So, you should initialise "int RightCan[submission:33422641] = 0" — the farthest point you can reach. (And you can also reach ALL the points before it — from 0 to RightCan).

If a[i] <= RightCan — then we can reach the start point of teleport[i]. So, we can change RightCan to b[i], if (b[i] > RightCan). (This if very impotant... becouse otherwise we can decrease RightCan!).

It's know that a[i] >= a[i — 1], so we don't miss anything.

And now, if (RightCan < m) you should print "NO\n", otherwise — you can reach your goal and print "YES\n".

Here is my solution: 33422641

→ Reply

kbulavenko

7 years ago, # ^ |

← Rev. 2 →

If it is possible. Can you help me, please? In pretest 5 we have:

In what way can we teleport from 11 to 13? Thank you in advance. In my solution http://codeforces.me/contest/902/submission/33436932 i had wrong answer.

→ Reply

Vsevolod_Kaplin

7 years ago, # ^ |

← Rev. 3 →

Well, look here:

3 7

0 6

1 2

4 7

Your solution gives the answer "NO". But your can reach point 7: 0 -> 4 -> 7.

port 1: [0 _ 1 _ 2 _ 3 _ 4 _ 5 _ 6]

___port 2: [1 _ 2] ___ [4 _ 5 _ 6 _ 7] <-port 3.

This happens because your looks only on the 2 last teleports. _____________________________________________________________

And yes, isn't mivael right?

→ Reply

UnfilledDreams

7 years ago, # ^ |

The basic idea behind the solution is you have to find is there any discontinuity between 0 to M.
To check this Take an array A of size M or greater having initial value 0.
now take the input [x;y] and do this.
A[x]+=1;
A[y]-=1;
after doing this take prefix sum of array a using A[i]+=A[i-1] form i=1 to M.
now if any element in array A [ 1 to M ] is equal to 0 except last value then answer will be 'NO' Otherwise 'YES'

→ Reply

TooWeak_TooSlow

7 years ago, # ^ |

Can you explain how prefix sum work in this case?

→ Reply

UnfilledDreams

7 years ago, # ^ |

Take an example.
N=3 M=5
0 2 ; a[0]=a[0]+1,a[2]=a[2]-1
2 3 ; a[2]=a[2]+1,a[3]=a[3]-1
3 5 ; a[3]=a[3]+1,a[5]=a[5]-1
after doing this your array will look like
[1 0 0 0 -1]
now after taking prefix sum your array will become.
[1 1 1 1 0]
no element is 0 except last one so your answer will be "YES" in this case.

→ Reply

fmota

7 years ago, # |

What's the pretest 3 on C ?

→ Reply

OneClickAC

7 years ago, # |

← Rev. 2 →

How so solve Div2D?

Also, though I was able to solve Div2C , someone please share the logic of it. I saw some people did C quite quickly. That was like fucking awesome.

Was it so easy or some general problem that I don't know?

→ Reply

Phanix

7 years ago, # ^ |

What I did was for one tree, I kept adding all the children to a single node. And for the other tree, i just remove one child and put under some other parent. Hope this is the right logic though

→ Reply

OneClickAC

7 years ago, # ^ |

Hmm seems nice and same as mine. :)

Although I was able to come with one more logic though a bit late but I believe this will work.

No two consecutive terms should be not equal to 1.

I mean to say that no two non unity terms should have distance less than or equal to 1.

This will suffice as a condition. For designing a tree, your and my logic should work I suppose.

→ Reply

Phanix

7 years ago, # ^ |

There can be consecutive 1's. The condition is there should be atleast 2 consecutive 2's(or numbers >1)

→ Reply

OneClickAC

7 years ago, # ^ |

Yes..That is the thing what I wanted to write. :)

→ Reply

deinier

7 years ago, # ^ |

This is what I implemented. Let's see if it is right, lol.

→ Reply

Divyansh_19

7 years ago, # |

How to solve Div2 D/Div1 B?

→ Reply

BeardAspirant

7 years ago, # ^ |

-17

B. I went for a DFS solution. set the root color and then dfs iteratively coloring the nodes

→ Reply

7 years ago, # ^ |

+12

He's mentioning the Div1B, not the Div2B.

→ Reply

harshit23897

7 years ago, # ^ |

He is asking Div1B.

→ Reply

7 years ago, # ^ |

+64

lets work on $\text{[math]}$
f₀ = 1
f₁ = x
f_i = f_i - 1 * x + f_i - 2
answer is f_n, f_n - 1

→ Reply

Don_1234

7 years ago, # ^ |

Yeah I did exactly the same.

→ Reply

Azret

7 years ago, # ^ |

Or use Google: https://en.wikipedia.org/wiki/Fibonacci_polynomials

→ Reply

7 years ago, # ^ |

+10

Usually I self-proclaim myself as someone who knows many things about math, but here you proved the opposite.

Thanks for the enlightenment you brought ;) I got stuck for an entire hour with D and not even knowing about this ;)

→ Reply

7 years ago, # ^ |

How do you use Google in such problems? I guess that searching "polynomials euclid algorithm small coefficients" would yield no useful result and even on that page you provided I see no useful info (without that mod 2 trick that I still don't understand these Fibonacci polynomials are useless).

→ Reply

adamant

7 years ago, # ^ |

You can do it by arbitrary mod. Mod 2 is to keep coefficients below 2. The thing is that if you calculate gcd using some mod and has k steps you will have at least k steps calculating it in rationals.

→ Reply

Divyansh_19

7 years ago, # ^ |

Using this formula,

f2 = x*x + 1 = x^2 + 1 and f3 = x*(x^2+1) + x = x^3 + 2x

Since, the coefficients should be from -1 to 1. So how did you handle this part?

→ Reply

7 years ago, # ^ |

+24

mod2

→ Reply

Divyansh_19

7 years ago, # ^ |

Thankyou! :)

→ Reply

skpro19

7 years ago, # ^ |

Instead of mod 2, can we multiply it with (-x) ?

→ Reply

HaabyHings

7 years ago, # ^ |

Yes but some higher degree polynomials may contain coefficients outside the range. So you need to multiply with x or -x depending on the current situation.

→ Reply

Kaneki_04

7 years ago, # ^ |

But the coefficients won't be -1 0 or 1 right?

(I don't know.. I am probably wrong but please tell me where I am wrong)

→ Reply

Ari

7 years ago, # ^ |

Working in $\text{[math]}$ means the coefficients are taken mod 2

→ Reply

Pennyroyal_Tea

7 years ago, # ^ |

← Rev. 2 →

f3 = x^3 + 2x, however all the coefficents must be in [-1;1]. How did you solve this issue?

UPD: solved

→ Reply

7 years ago, # ^ |

+45

What? I have no idea why this works :f. This $\text{[math]}$ seems like key idea here, but I see no meaning behind it.

→ Reply

Pennyroyal_Tea

7 years ago, # ^ |

-30

It's well known that GCD takes the longest time on fibonacci numbers. This is just an extension of the idea from numbers to polynomials

→ Reply

7 years ago, # ^ |

+35

If we abandon condition about coefficients being from set {-1, 0, 1} then this problem is trivial, I was well aware that without it we can do f_i = xf_i - 1 + f_i - 2... What is tricky here is that reducing mod 2.

→ Reply

7 years ago, # ^ |

if we work on $\text{[math]}$ instead of $\text{[math]}$ , then this obviously works since f_i mod f_i - 1 = f_i - 2 since x * f_i - 1 + f_i - 2 mod f_i - 1 is obviously f_i - 2
in $\text{[math]}$ , this fact still remains true , since degree of f_i = degree of f_i - 1 + 1 and powers of x are independent over $\text{[math]}$ .

→ Reply

7 years ago, # ^ |

+32

I still have no clue about your solution. It is of course true that $\text{[math]}$ over $\text{[math]}$ , but I see no connection of that fact to Euclid algorithm in $\text{[math]}$ and have no idea what this independence has to do with anything.

→ Reply

7 years ago, # ^ |

well f_i mod f_i - 1 = f_i - 2 even in $\text{[math]}$ , are you sure you didn't misread the question and thought that coefficients should be {-1,0,1} even for immediate steps?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

+11

Let's make it clear what is obvious ans what is not:

Obvious fact 1: If we define f_i = xf_i - 1 + f_i - 2 over $\text{[math]}$ then we have $\text{[math]}$ over $\text{[math]}$

Obvious fact 2: If we define f_i = xf_i - 1 + f_i - 2 over $\text{[math]}$ then we have $\text{[math]}$ over $\text{[math]}$

Obviously false statement: If we define f_i = xf_i - 1 + f_i - 2 over $\text{[math]}$ then we have $\text{[math]}$ over $\text{[math]}$

Since that last fact is not true, I see no connection of your solution to Euclid algorithm.

And regarding "are you sure you didn't misread the question and thought that coefficients should be {-1,0,1} even for immediate steps?" — during contest I was solving that wrong question you mentioned (however I am pretty sure you meant "intermediate" not "immediate" :)), but I realized it was not necessary some time ago and still have no clue about it.

EDIT: Sorry, I made a typo in first version of that post in "obviously false statement"

→ Reply

7 years ago, # ^ |

ah , i finally get your point , i completely forgot this during contest and just implemented it straight away thinking "its just a div1B , it can't be that hard".
Let me think about it for a while

→ Reply

desert97

7 years ago, # ^ |

The proof isn't that hard. Start from the two polynomials f_n, f_n - 1. Now do Euclidean algorithm over $\text{[math]}$ on these.

You can show the following claims by induction. First, all fractions during the process will have odd denominator. Also, the numerators of a polynomial p_i(x) you get during the Euclidean algo over $\text{[math]}$ will have even numerator if and only if the corresponding coefficients in f_i(x) is 0. In particular, all leading coefficients will be fractions with odd numerator and denominator.

→ Reply

7 years ago, # ^ |

okay here is a much simpler reasoning of why this takes n steps
Suppose on the contrary , it takes < n steps , then for some i , f_i mod f_i - 1 has degree < i - 2.
f_i = f_i - 1 * (ax + b) + r(x)
degree of r(x) is less than i - 2
let f_i(x) = ... + px^i - 2 + ...
and f_i - 1(x) = ... + cx^i - 2 + ... dx^i - 3 + ...
then we have p = bc + ad in $\text{[math]}$ , since each of them are rationals and 2 is obviously a prime , each of these terms exist in $\text{[math]}$ as well hence this holds in $\text{[math]}$ as well and we have degree of r(x) is less than i - 2 in $\text{[math]}$ as well which is a contradiction.

→ Reply

Alpha_Q

7 years ago, # ^ |

← Rev. 2 →

Just try random polynomials: one of degree n and another of degree n - 1 till it works.

→ Reply

desert97

7 years ago, # ^ |

Alternatively, you can set P₀(x) = 1, P₁(x) = x and for i ≥ 2, set

P_i(x) = x·P_i - 1(x) ± P_i - 2(x)

for some choice of sign. Exactly one choice of sign works once you fix $P_2(x).$ A computer can verify that this works, but I have no proof.

→ Reply

7 years ago, # |

how to solve c and D?

→ Reply

TShT

7 years ago, # ^ |

...... ( f(x) , x+1) -> (x+1 , x ) -> (x,1) -> (1,0)

→ Reply

TShT

7 years ago, # ^ |

-6

каждый раз надо находить такой f(x) что f(x) mod (x+1) = x (в нашем случаи ) но я так и не смог написать )

→ Reply

VoIdJMp

7 years ago, # ^ |

I think Div2C Greedy problem

→ Reply

7 years ago, # ^ |

can you please help me with my code : https://ideone.com/talzy9

→ Reply

VoIdJMp

7 years ago, # ^ |

← Rev. 11 →

test
5

1 2 1 2 1 2

You program is wrong Answer is "perfect"

→ Reply

7 years ago, # ^ |

← Rev. 3 →

can you please explain why the answer is perfect in this case?

EDIT : my bad now i understood thanks a lot for the help ! :)

btw if i am correct the cases of perfect are those which don't have two consecutive ai > 1 ? if i am incorrect please correct me!

→ Reply

VoIdJMp

7 years ago, # ^ |

← Rev. 2 →

I change you code. I think its correct

→ Reply

Kaneki_04

7 years ago, # |

+38

"awkwardly long and boring statements"

Lol so true

→ Reply

eric

7 years ago, # |

i dont understand problem C, output sum(a[i]) E i = 0->h

→ Reply

Phanix

7 years ago, # ^ |

That refers to the number of integers you are to print. The summation is nothing but the number of nodes in the tree

→ Reply

madn

7 years ago, # |

How to solve div1B?

→ Reply

7 years ago, # |

+46

What was the purpose of putting "tree" in title of D? To give a hint for contestants :f?

→ Reply

Djok216

7 years ago, # ^ |

+51

In Russian is graph instead of tree :/

→ Reply

EbraM96

7 years ago, # |

← Rev. 3 →

+14

For those who ask about seeing others' submissions/hacks/adobe flash player:

set these settings:

Allow website to use Flash

→ Reply

7 years ago, # ^ |

i am able to see others submission history but unable to see solution even after locking!

→ Reply

fmqjpt

7 years ago, # |

← Rev. 2 →

Lol, I hacked a few people on Div1A because they did something like cout << ans[i] where ans was of size ~10^5.

→ Reply

HosseinYousefi

7 years ago, # ^ |

+12

NOOOOOOOOOOOOOO!

→ Reply

Ros9

7 years ago, # ^ |

1e5 ?

→ Reply

hungry_fool

7 years ago, # ^ |

Can you elaborate?

→ Reply

21August

7 years ago, # |

-7

Nice contest. Couldn't understand C for an hour and after i understand it i solved it in 20 mins. But in general nice.

→ Reply

Emsawy

7 years ago, # |

What Div2 (A) pretest 6 ?!

→ Reply

samyakjain

7 years ago, # ^ |

May be something like.. 3 10 0 9 1 5 7 10

→ Reply

Emsawy

7 years ago, # ^ |

← Rev. 4 →

Ooooh, I did break while getting input. My output in pretest 6 was: -- NO NO --

→ Reply

L0rdV0ldemort000006

7 years ago, # |

This is the way a codeforces contest should be prepared.Kudos to problem setters.

→ Reply

hocky

7 years ago, # |

← Rev. 2 →

Overall, the problems are good. I think ive seen Div2B & A with some changes, the C and D are so challenging. Even though, i almost made it, apparently i didnt. (._.)/, I'm actually really tired but i rushed to join this contest because i wanted to get my expert rating (AHAHAHAH), I ended up doing really sucks, and sloppy (Because of my skill in graph). Lesson I learned in this contest, sometimes you need a rest between contests. :). Merry Christmas !

Update : I think B is easier than A. A is kinda "tricky"

→ Reply

madn

7 years ago, # |

+14

I've just ruined another div1 contest and now i'm thinking whether it's even possible to come up with an idea for div1B if you've never seen anything similar before -_-

→ Reply

hocky

7 years ago, # ^ |

Well everyone had their own bad day :(. I can relate to what you feel.

→ Reply

Radewoosh

7 years ago, # |

Anybody anything to E? I can only generate 10^8 pairs as candidates for (sum of a_i, sum of a_i²) :/

→ Reply

adamant

7 years ago, # ^ |

There will be editorial very soon, please be patient :)

→ Reply

7 years ago, # |

-25

Hey, is he a cheater or acts like tourist in the last cs round ? :‑Þ

→ Reply

7 years ago, # ^ |

Could you explain exactly what makes you think he could possibly be a cheater?

→ Reply

7 years ago, # ^ |

maybe submissions time?

→ Reply

7 years ago, # ^ |

How is solving three problems in 1 hour and 52 minutes suspicious?

→ Reply

7 years ago, # ^ |

so you c am asking if a cheater || !

→ Reply

7 years ago, # ^ |

Are you a cheater, by the same token?

→ Reply

7 years ago, # ^ |

+44

with 2 years in gray ? -___-

→ Reply

Ahmad1

7 years ago, # |

-10

I finished coding C/div1 5 minutes after the contest with O(n log n) solution :(

→ Reply