Codeforces Round #569

5 years ago, # |

+19

We hope for a good contest.

→ Reply

dusty

5 years ago, # ^ |

-6

when the contest delay for 30 minutes)

→ Reply

Adhami

5 years ago, # ^ |

+191

We hope for a contest*

→ Reply

5 years ago, # ^ |

Yes.

→ Reply

21August

5 years ago, # |

+187

The whole IOI Chinese team tested the round + 300iq coordinated it.

→ Reply

Brodicico

5 years ago, # ^ |

So we should expect for a very interesting and tricky contest. :D

→ Reply

21August

5 years ago, # ^ |

+46

We should expect strong pretests and no errors in the contest.

→ Reply

MultiTrackKind

5 years ago, # ^ |

← Rev. 2 →

+11

This comment didn't age well ;p

I loved Div.2 B's pretests. This was my first time hacking and I could hack 6!

→ Reply

ChthollyTree

5 years ago, # ^ |

You forgot Sulfox.

→ Reply

Roham

5 years ago, # |

-9

The whole IOI Chinese team tested the round!!!**- **

→ Reply

rmo

5 years ago, # ^ |

+29

I think you should write your own comments

→ Reply

YoshinoTomotake

5 years ago, # |

← Rev. 3 →

Round tested by Chinese.. Hope it will give me an unforgettable experience :)

→ Reply

21August

5 years ago, # ^ |

+12

It's actually a Russian round, it was tested by the Chinese.

→ Reply

The_Kings_Gambit

5 years ago, # ^ |

What exactly do you mean by unforgettable? Don't scare me :P

→ Reply

YoshinoTomotake

5 years ago, # ^ |

+26

It's 0:22 in the morning in China, and the contest will be start in 40+mins. It's very unforgettable, isn't it? (though in another way)

→ Reply

5 years ago, # ^ |

+31

have a nap in case of brain power outage

→ Reply

NxtEcho

5 years ago, # ^ |

← Rev. 2 →

I had just slept to 00:30,and when I woke up and saw the rest time to wait...It should be unfogettable.

→ Reply

The_Kings_Gambit

5 years ago, # ^ |

-11

Well, it indeed was unforgettable. B got hacked :/

→ Reply

codeforthrone

5 years ago, # |

" During the round you will be helping for pupils of one usual Moscow school." What does this mean?

→ Reply

5 years ago, # ^ |

i too want to know....

→ Reply

VadymKa

5 years ago, # ^ |

+32

pupils -> schoolkid / students.

→ Reply

5 years ago, # ^ |

+84

pupils -> between 1200 and 1400 rating

→ Reply

5 years ago, # ^ |

i don't think i can help them in any way , i started coding almost 3 months ago and my rating is falling continuously.... i think i need help ....

→ Reply

The_Kings_Gambit

5 years ago, # ^ |

It will increase once you forget thinking about it! (except just after the contest :P)

→ Reply

doped.silicon

5 years ago, # ^ |

+49

This is the theme of the contest, the questions will be like "Pupils of a school in Moscow want to perform a certain task, but its too difficult for them, so they are asking for your help..."

→ Reply

rahulb

5 years ago, # ^ |

+254

Nice. I am too tired of helping vasya and petya

→ Reply

smit.mangukiya

5 years ago, # ^ |

Nastya, Tanya

→ Reply

Adhami

5 years ago, # ^ |

Should I mention Alice and Bob? I still don't if Alice is a female or male XD

→ Reply

5 years ago, # ^ |

+20

The characters in these problem statements are more unrealistic than characters in porn movies.

→ Reply

Ozymandias

5 years ago, # ^ |

Main characters of problems will be school pupils/students.

→ Reply

4c5948

5 years ago, # |

← Rev. 2 →

Xuihan sunset Wang

I think Xuihan is a typo. You may mean Xiuhan.

(Sorry for my poor English)

→ Reply

4c5948

5 years ago, # |

← Rev. 2 →

-9

IOI Chinese testers team lol

→ Reply

shadaBhai

5 years ago, # |

← Rev. 2 →

+13

A 5 problem contest after long days

→ Reply

5 years ago, # |

Nearly 12 p.m at my place. But all love for programming, I will try my best.

→ Reply

5 years ago, # ^ |

for me it is nearly 12 am, but Im getting into skipping lunch, so not that bad as it is for you

→ Reply

5 years ago, # ^ |

VietNam and Brazil: 12 hours away ^^

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Now it is almost 2 a.m. for you '-' Are you going to participate?

→ Reply

5 years ago, # ^ |

At my place, the contest starts at 11.35 p.m and ends at 1.35 a.m. I think it'll be fine for me to participate

→ Reply

babin

5 years ago, # ^ |

I think you meant 12 a.m. because by convention, 12 p.m. is noon, not midnight.

→ Reply

5 years ago, # ^ |

Oh yes ^^. Then 11.59 p.m would by fine

→ Reply

I_Love_Tina

5 years ago, # ^ |

-27

Nerd

→ Reply

_vagabond

5 years ago, # |

+19

helping kids, noble task.....who's gonna help me help them......lol

→ Reply

K_K

5 years ago, # |

time to think

→ Reply

not.derwes.at.all

5 years ago, # |

Best of Luck for your first contest as a problemsetter.

→ Reply

Wesam

5 years ago, # |

+22

Whole people wrote the same comment "ioi Chinese testers team" What is happening!

→ Reply

Xellos

5 years ago, # ^ |

+20

social_credit++

→ Reply

Runtime.error

5 years ago, # |

-6

I wish positive rating for every participant :)

→ Reply

M.Ibrahim_

5 years ago, # ^ |

This is not possible :)

→ Reply

5 years ago, # ^ |

← Rev. 3 →

if you consider 0 as a positive number it is possible, LOL, just kidding.

→ Reply

ouuan

5 years ago, # ^ |

+114

The total rating decreases after every contest, otherwise, ratings will become higher and higher because new users will join Codeforces with the initial 1500 rating points.

→ Reply

rotavirus

5 years ago, # ^ |

+26

if no new users participate, then the total rating won't decrease

→ Reply

TripleM5da

5 years ago, # ^ |

Also if no users participate, then the total rating won't decrease

→ Reply

ILoveBitches

5 years ago, # ^ |

+12

Also if one user participates, then there won't be any change

→ Reply

shan61916

5 years ago, # ^ |

you cleverly wished for yourself. Nice

→ Reply

ouuan

5 years ago, # |

+65

In fact, Sulfox's name is not Sooke Gnar. However, he loves Gnar —— The Missing Link very much.

→ Reply

Sturdy

5 years ago, # ^ |

Chinese people have interesting names

→ Reply

smallguoguo

5 years ago, # |

-23

Ｔhis time is not friendly to Chinese players

→ Reply

no_ath

5 years ago, # |

Time changed from 19:35 UTC to 22:05 UTC.
Time increased = 150 minutes.
May we also get +150 rating today.

→ Reply

KGrader

5 years ago, # ^ |

Lol, sounds great! Good luck anyways!

→ Reply

DimmyT

5 years ago, # |

+36

New Codeforces round, new chance to fall!

→ Reply

5 years ago, # |

+616

→ Reply

tokkurospi

5 years ago, # ^ |

You're so cool :0

→ Reply

Vergara

5 years ago, # ^ |

+43

You're cool! You're all cool!

→ Reply

Nikhil1998

5 years ago, # ^ |

Keanu in the house!

→ Reply

C137

5 years ago, # ^ |

This meme never gets old :D

→ Reply

redmcgn

5 years ago, # |

So lucky that the contest starts right before I get home

→ Reply

alpha_q2

5 years ago, # |

A delayed contest has never been good for my rating.

→ Reply

5 years ago, # |

← Rev. 2 →

UPS is needed.

→ Reply

P___

5 years ago, # |

+21

What is the score distribution?

→ Reply

kwebi

5 years ago, # |

← Rev. 2 →

-19

。

→ Reply

5 years ago, # ^ |

+30

Don't remember asking you.

→ Reply

kwebi

5 years ago, # ^ |

+16

Dont't remember saying to you.

→ Reply

5 years ago, # ^ |

-16

did you take your memory pill??

→ Reply

kwebi

5 years ago, # ^ |

-7

you are not friendly, goog bay!

→ Reply

5 years ago, # ^ |

Sorry :-/

→ Reply

fallacy

5 years ago, # |

← Rev. 2 →

+71

When reading the comment section ends!!!

→ Reply

codewiz

5 years ago, # |

← Rev. 4 →

+41

System Test :(

->How 30 minutes before contest felt!!

→ Reply

Priyam2k

5 years ago, # |

Now we have Caseforces!

→ Reply

5 years ago, # |

+26

The pretest of problem B is BRILLIANT, because I have just made the first TWO Successful Hacking Attempt in my life !

→ Reply

alphatrance

5 years ago, # ^ |

What was the Hack?

→ Reply

5 years ago, # ^ |

The first one is 2\n 0 -1 (which get the wrong answer —— 0 -1), and the second one is 3\n -1 -1 -1 (which get the wrong answer —— -1 -1 -1). Hence , I guess the pretest of it is too big for some wrong program (?)

→ Reply

5 years ago, # ^ |

my program failed at 9th pretest ,can you help me....

→ Reply

_vagabond

5 years ago, # ^ |

What was ur logic?
The logic is simple make all non negative numbers negative by operating on them. If n is odd pick the number with highest magnitude and make it posetive.
Print all the numbers.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-15

I solved using C Language ,and used long long int for input but it's it shows large product not possible at test case #9 hence failed What to do?

→ Reply

dasfex

5 years ago, # ^ |

In this task max product can be (10^6)^(10^5), but max product that u can use in long long int is 10^18. Obviously, it shouldn't work because overflow.

→ Reply

https://codeforces.net/contest/1180/submission/55915141

5 years ago, # ^ |

-8

https://codeforces.net/contest/1180/submission/55892852 here is my solution ,see it failed at 9th pretest, i am not able to understand error;

→ Reply

_vagabond

5 years ago, # ^ |

That's part of the problem u have to do it without calculating the product of all the numbers...although there are techniques to manipulate big numbers but it isnt needed for this task... go through the editorial

and here is my soln as well

→ Reply

all_too_well

5 years ago, # ^ |

I got one on 3/n 1 1 -1

→ Reply

solvemproblr

5 years ago, # ^ |

pretests were too dumb, there is no pretest with a[i]=0

→ Reply

Nazarbek.Baltabaev

5 years ago, # ^ |

-11

no luck with getting a candidate

→ Reply

solvemproblr

5 years ago, # ^ |

-11

~~fuck this CM, I'm gonna be master~~

→ Reply

Nazarbek.Baltabaev

5 years ago, # ^ |

→ Reply

5 years ago, # |

+12

How to solve D?

→ Reply

RubenAshughyan

5 years ago, # ^ |

← Rev. 2 →

+34

A 6x6 can be traversed like this, other cases are also analogous. You can easily show that this method does not use the same vector twice.

1	23	25	36	14	12	
3	21	27	34	16	10	
5	19	29	32	18	8	
7	17	31	30	20	6	
9	15	33	28	22	4	
11	13	35	26	24	2

But most probably this is not the only solution. There can be other ways as well.

→ Reply

5 years ago, # ^ |

+11

Is it the only simulation or any proper mathematics.

→ Reply

https://codeforces.net/blog/entry/67813?#comment-520779

5 years ago, # ^ |

← Rev. 4 →

+19

You could call it intuition.

First check whether you can always do it for some $$$1$$$x$$$N$$$ grid.

Hint

Complete Solution

→ Reply

Mindjolt

5 years ago, # ^ |

← Rev. 2 →

Using that method, it's easy to show that once you take a certain vector, you never use it again. That's because the squares on which you could use that vector have already been visited before.

→ Reply

Hossam

5 years ago, # ^ |

what if columns are odd sized?

→ Reply

RubenAshughyan

5 years ago, # ^ |

It does not differ much

1	23	25	38	36	14	12	
3	21	27	40	34	16	10	
5	19	29	42	32	18	8	
7	17	31	41	30	20	6	
9	15	33	39	28	22	4	
11	13	35	37	26	24	2

→ Reply

Hossam

5 years ago, # ^ |

excellent pattern! How did you come up with it though?

→ Reply

RubenAshughyan

5 years ago, # ^ |

→ Reply

5 years ago, # ^ |

+30

Fun Fact: infinite recursion if you keep reading downwards, starting from above post.

→ Reply

SugA

5 years ago, # ^ |

I had to draw many grids for quite a few no. of pages to figure out this pattern.

→ Reply

Hossam

5 years ago, # ^ |

← Rev. 2 →

I did too! but unfortunately stopped at the idea of visiting the same line (going onwards and backward), the diagonal kind of moves is so brilliant! Kudos to you guys!

→ Reply

nic6200

5 years ago, # ^ |

nice!

→ Reply

mohamedeltair

5 years ago, # ^ |

+34

Starting from (1, 1), move to (n, m), then (1, 2), then (n, m-1), and so on till (n, 1). Then go to (2, 1), then (n-1, m), then (2, 2), then (n-1, m-1), and so on till (n-1, 1). Keep repeating this process. If you reached a row i where row i == n-i+1. Then just from (i, 1) move to (i, m), then (i, 2), and so on till you visit the whole row.

→ Reply

https://codeforces.net/contest/1180/submission/55902704

5 years ago, # ^ |

← Rev. 5 →

-10

Hey using the same logic I had a TLE, I’ve no idea why

→ Reply

mohamedeltair

5 years ago, # ^ |

Replace cout with printf.

→ Reply

5 years ago, # ^ |

Thanks, mate. The constraints seem to be too tight,

→ Reply

VadymKa

5 years ago, # ^ |

Well, jfyi std::endl is not the same as “\n” because of stream flush.

→ Reply

majdoor

5 years ago, # ^ |

← Rev. 2 →

For solving D, i converted it into 1-D array and then using two pointer i solved it . For eg . 2 3 ==> 2*3 = 6 we are firstly in 1,then i will visit 6 then 2, then 5, then 3 and so on .

→ Reply

Golovanov399

5 years ago, # |

Is div1E an exercise on the proportional cake-cutting + optimizations to pass $$$O(n^2\cdot\log{n})$$$ queries?

→ Reply

webmaster

5 years ago, # ^ |

← Rev. 2 →

The 3 accepted submissions seems like $$$O(n\cdot log n\cdot log 10^{18})$$$

→ Reply

gop2024

5 years ago, # ^ |

← Rev. 2 →

+10

Our solution seems to work in $$$O(n \cdot log(10^{18}))$$$ queries

→ Reply

5 years ago, # |

What is in pretest 9 of problem B Nick and Array?

→ Reply

_nathan_drake_

5 years ago, # ^ |

I got stuck on the same pretest :(

→ Reply

yoda69

5 years ago, # ^ |

Try 2 3 4. Answer should be -3 -4 4

→ Reply

_nathan_drake_

5 years ago, # ^ |

how did you solve B?

→ Reply

yoda69

5 years ago, # ^ |

← Rev. 2 →

The only way to increase product is by increasing |a| for each a in array. Only positive numbers can be increased in magnitude by the given method i.e. 4 becomes -5 so |-5| > |4|.

So first change all positive numbers like this including 0 to -1. Now all are negative. If even sized array, we cant do better. If odd sized change the largest negative number like -100 to 99. This makes product positive

→ Reply

new_bie_always

5 years ago, # ^ |

what is the logic behind taking the largest negative number in magnitude instead of smallest negative number in magnitude

→ Reply

aberent

5 years ago, # ^ |

When you change an element with value -x from negative to positive it becomes x-1. This multiplies the magnitude of the product by (x-1)/x. You want this to be as large as possible, and it gets larger as x gets larger.

→ Reply

sourabh54singh

5 years ago, # ^ |

No I don't think so . My answer is -3 -4 4 according to 2 3 4. I think it is 9 -4 -5. the answer should be 9 -4 -5 .

→ Reply

prabhtej

5 years ago, # ^ |

take the biggest negative number instead of least.

→ Reply

-sh

5 years ago, # ^ |

I was making this mistake, can you prove your greedy approach ?

→ Reply

AK18

5 years ago, # ^ |

if you are multiplying 2 numbers x and y, such that |x| > |y| then you can visualize it in 2 ways, first adding y x times and second adding x y times. Now if you decrease x then you are just removing 1 y and if you decrease y then you are just removing 1 x. Now you can see which one is optimal.

→ Reply

5 years ago, # |

please help me to identify my mistake in problem B https://codeforces.net/contest/1180/submission/55894819

→ Reply

5 years ago, # ^ |

6 -1 -2 -3 0 0 0 try getting this case correct, almost all hacks are the similar to this (afaik).

→ Reply

5 years ago, # ^ |

Thanks

→ Reply

yoda69

5 years ago, # ^ |

The order of array is destroyed after sort. Also, the logic is very convoluted. Observe that -a -1 only increases |a| for positive numbers. Try using this fact

→ Reply

5 years ago, # ^ |

Thanks

→ Reply

5 years ago, # ^ |

try this test case 3 -4 -9 -8 Your output is -4 7 8

→ Reply

5 years ago, # ^ |

Thanks

→ Reply

ajaymalik

5 years ago, # ^ |

← Rev. 3 →

have you change the element which is equal to zero 4 0 0 0 0 ans should be -1 -1 -1 -1 but your code print 0 0 0 0

→ Reply

5 years ago, # ^ |

Thanks

→ Reply

loc321

5 years ago, # |

shit that m1 range i took it int got wrong

→ Reply

Robbinb1993

5 years ago, # |

+13

I hope to finally become a candidate master :).

→ Reply

5 years ago, # |

I'm just gonna skip B in future rounds, C is almost always easier for some reason.

→ Reply

5 years ago, # ^ |

+17

The logic I used for b was much simpler than c imo, (convert all to negative and then convert the least to positive if n%2==1).

→ Reply

5 years ago, # ^ |

can u explain your logic with this test case ? 5 1 2 3 4 -1

→ Reply

AaronSwartz

5 years ago, # ^ |

it has not to be the least negative, it has to be the least negative different to -1

→ Reply

5 years ago, # ^ |

first you convert all to negative, ie -6 -2 -3 -4 -5 -1. now because n%2 is even, this is the answer. if it was odd, (if converted array is -6 -2 -3 -4 -5), then pick the smallest value and make it positive (5,-2,-3,-4,-5)

→ Reply

5 years ago, # ^ |

I mean this. 5 is the number of the element. 5

1 2 3 4 -1

→ Reply

5 years ago, # ^ |

-2 -3 -4 4 -1. you can look at my code in standings, its the same logic.

→ Reply

singhpankaj079

5 years ago, # ^ |

well after making all the integers negative I brute forced but even then I am getting the wrong answer for test case 9!!

→ Reply

agrawal117

5 years ago, # ^ |

but if u r done brute force then surely u r multiplying all the numbers initially but from that overflow occurs, due to than u cannot get yur answer correct in large value,

→ Reply

singhpankaj079

5 years ago, # ^ |

Oh yes,I realized that later.By the way thank you for reply.

→ Reply

prabhtej

5 years ago, # ^ |

me too

→ Reply

AaronSwartz

5 years ago, # ^ |

even that, C you did not have to think anything, just implement it

→ Reply

Galaxy_Pegasus

5 years ago, # ^ |

← Rev. 4 →

Take this case of length 3

-2 -3 -4
I think your logic will not work for this case

→ Reply

5 years ago, # ^ |

← Rev. 2 →

you can check my code directly, I used this logic. In this case the output is -2 -3 3.

→ Reply

5 years ago, # ^ |

its a very nice solution, a solution I never thought of, not even a slightest bit.

→ Reply

Noob_Noob_

5 years ago, # ^ |

← Rev. 2 →

Edit:nvm i got it

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Hey, you can either look it through an example: (-2,-3,-5) changed to (1,-3,-5) or (-2,-3,4). clearly, the 2nd product is greater.

Proof:

Let a1,a2,..., an be +ve numbers in sorted order.

It would be obvious that:

(a1-1)*(a2*a3*a4*...*an) < (an-1)*(a1*a2*...*a(n-1))

→ Reply

Noob_Noob_

5 years ago, # ^ |

thanks

→ Reply

Jatana

5 years ago, # |

← Rev. 2 →

+130

Very nice and enjoyable problems!

→ Reply

pa.n.ik

5 years ago, # |

+11

What concept was involved in Div1C ?

→ Reply

Adhami

5 years ago, # ^ |

Hint: imagine it as brackets

→ Reply

5 years ago, # ^ |

Consider suffixes of cummulative frequency of both dishes and people.

→ Reply

pa.n.ik

5 years ago, # ^ |

Can you please expand a bit on your solution, because I couldn't think of something with these hints. Thanks!

→ Reply

5 years ago, # ^ |

← Rev. 3 →

+71

Let $$$fstudents(i)$$$ be the frequency of students with money equal to $$$i$$$.
Let $$$fdishes(i)$$$ be the frequency of dishes that cost $$$i$$$ money.

We are looking for the greatest j such that $$$\sum_{k = j}^{1000000} fdishes(k) > \sum_{k = j}^{1000000} fstudents(k)$$$.

We can consider $$$dif(i) = fdishes(i)-fstudents(i)$$$. We want to find the rightmost index $$$i$$$ such $$$\sum_{k=i}^{1000000}dif(k) > 0$$$.

We can have a segment tree that stores the value of maximum suffix sum of $$$dif$$$ in range. The updates are just adding and substracting 1 from leaves of the tree. We can answer queries in $$$ O(Qlog^210^6) $$$ by binary searching to find the first $$$i$$$ such that the maximum suffix sum is greater than 0. We can do this faster, in $$$O(Qlog10^6)$$$ by the method of descending the tree. I hope i explained it clearly.

→ Reply

pa.n.ik

5 years ago, # ^ |

Thanks Charis02

→ Reply

Redux

5 years ago, # ^ |

+11

Hey, I think I’m missing something simple. Why is it sum(dif(k)) > 0 instead of sum(dif(k)) < 0? If the sum is positive for some i, doesn’t that mean that we have more students than dishes for that i, not that there’s a dish we can take.

→ Reply

5 years ago, # ^ |

Yes you are right, sorry. I meant to write $$$dif(i)=fdishes(i)-fstudents(i)$$$ . Thanks,I'll correct it.

→ Reply

code_kit

5 years ago, # ^ |

Hey, one doubt. If you just update the leaves in the seg tree will it be suffice ? Dont we need to update all suffixes of greater length than this ? I.e lazy prop. Bcoz if you just update one suffix then the suffix greater than this length won't have updated value and will have one student or dish less ?

→ Reply

5 years ago, # ^ |

No, because by updating the leave you update all ranges containing it (standard segment tree update). You don't need lazy prop because you update only one leaf not a range of them.

→ Reply

mohamedeltair

5 years ago, # ^ |

code_kit

By every node $$$nd$$$ storing the maximum suffix sum of $$$dif$$$ in range, Charis02 means suffix with respect to $$$nd$$$, not the whole array.

→ Reply

alimq

5 years ago, # |

+14

Can we actually solve D like this or is it just luck?

55894627

→ Reply

Tutis

5 years ago, # ^ |

It is almost the same solution everyone wrote.

→ Reply

webmaster

5 years ago, # ^ |

It's correct

→ Reply

lunga

5 years ago, # ^ |

← Rev. 2 →

Can you please explain its correctness ?

→ Reply

Tutis

5 years ago, # ^ |

Look at n=2

→ Reply

Andimeo

5 years ago, # ^ |

A clever implementation. I did the same but far more cumbersome.

→ Reply

https://codeforces.net/contest/1180/submission/55899448

5 years ago, # ^ |

← Rev. 2 →

Same here. Now it looks like I wasted a lot of time, after seeing this short submission.

→ Reply

Slow_But_Determined

5 years ago, # |

-12

Delay in System tests?

→ Reply

Mn619

5 years ago, # |

Can Someone explain why their code give TLE -

https://codeforces.net/contest/1180/submission/55903257

→ Reply

sevlll777

5 years ago, # ^ |

← Rev. 2 →

use '\n' instead of endl

→ Reply

5 years ago, # |

+70

→ Reply

gjaiswal108

5 years ago, # ^ |

+12

Is there again power outage??(Delay in systest)

→ Reply

5 years ago, # ^ |

← Rev. 2 →

→ Reply

5 years ago, # ^ |

Looks like Systest won.

→ Reply

solvemproblr

5 years ago, # ^ |

+14

memewoosh

→ Reply

Andimeo

5 years ago, # |

Is there a hacking phase? I suppose only Educational rounds have hacking phase.

→ Reply

5 years ago, # ^ |

Yes, only Educational rounds and div 3 rounds

→ Reply

lzoilxy

5 years ago, # |

+26

It is really a good contest.

→ Reply

5 years ago, # |

+25

It happened to me for the first time. My solution was hacked midway between the contest but after a while I got a notification that my solution was correct.

Link : https://codeforces.net/contest/1180/submission/55886651

→ Reply

joylintp

5 years ago, # ^ |

← Rev. 3 →

+156

I hacked you during the contest with the test case:

3
0 -1 -1

After pressing the hack button, I found that it should be an unsuccessful hacking attempt but it turned out to be a successful one

I thought it's quite strange and I've reported this to problem setters during the contest Few minutes later they replied "under investigation", and your code is Accepted, my hack became an "ignored"

Actually I'm not sure what's going on lol

→ Reply

5 years ago, # ^ |

+55

Thanks a lot buddy, You sacrificed 50(150) points just for honesty. Cheers.

→ Reply

5 years ago, # ^ |

But the setters might be having similar system tests as well, so setters please be careful of your system tests for Div2 B

→ Reply

gop2024

5 years ago, # ^ |

← Rev. 3 →

+26

We had a little bug in our checker and it didn`t work correctly when the answer is $$$0$$$ and the jury answer is different from the participant answer as a multiset. We are sorry for the mistake.

→ Reply

300iq

5 years ago, # ^ |

+76

Hello there.

Sorry, that was definitely my fault, because as a coordinator I missed this case with $$$0$$$ in the checker. There were no similar tests in other hacks or in systests, so everything should be fine.

My apologies to shpvb, who suffered from my mistake.

I will be more attentive to these kind of things next time, sorry again.

→ Reply

5 years ago, # ^ |

+49

No problem buddy, that is totally cool with me.

→ Reply

5 years ago, # ^ |

Hey 300iq, My submission has not been evaluated yet. Is there any problem?

→ Reply

5 years ago, # ^ |

Sorry, It got evaluated in the end.

→ Reply

300iq

5 years ago, # ^ |

+48

Also, thank you for your honesty! Without you, we wouldn't notice this bug.

→ Reply

joylintp

5 years ago, # ^ |

+37

Thanks for nice contest and interesting problems, too!

→ Reply

mango_lassi

5 years ago, # |

← Rev. 3 →

I think this works for E, but I wrote too many bugs so couldn't get it to work in time :(

Edit: 55909022. Turns out some constant optimization was required too, so I wasn't that close

solution to E

If $$$v = ask(i, x)$$$, let $$$x = rev(i, v)$$$. Set $$$t = \frac{L}{n}$$$.

We will first sort the functions into order $$$p_{1}, \dots, p_{n}$$$, then return the interval $$$[rev(p_{i-1}, ti), rev(p_{i}, t(i+1))]$$$ for $$$1 \leq i \leq n-1$$$, and $$$[0, rev(p_{0}, t)]$$$ for $$$i = 0$$$. This ordering will work, since due to the sorting we will do, the condition $$$rev(p_{i}, t(i+1)) \leq rev(p_{i+1}, t(i+1))$$$ will hold, and therefore $$$[rev(p_{i}, ti), rev(p_{i}, t(i+1))] \subset [rev(p_{i-1}, ti), rev(p_{i}, t(i+1))]$$$, and the function clearly increases at least $$$t$$$ in the subinterval, so it increases at least $$$t$$$ in the interval, so the solution works.

To find this ordering, we do divide and conquer. First, sort all points into the group of size $$$\left\lceil\frac{n}{2}\right\rceil$$$ with smaller $$$rev(i, t \left\lceil\frac{n}{2}\right\rceil)$$$, and the group of size $$$\left\lfloor\frac{n}{2}\right\rfloor$$$ with at least as large. Then recursively sort the smaller and larger subsets, but instead of using $$$rev(i, t \left\lceil\frac{n}{2}\right\rceil)$$$, we use $$$rev(i, t (k + \left\lceil\frac{n}{2}\right\rceil))$$$ where $$$k$$$ is the total size of the subsets we have sent to the left side of the recursion so far.

Doing this naively would require $$$O(n \log(n) \log(10^{18}))$$$ operations, which is too many, but we can do it smarter by applying randomized quickselect to split the groups. Randomly pick a pivot $$$i$$$, find $$$x = rev(i, t (k + \left\lceil\frac{n}{2}\right\rceil))$$$, and see if the value $$$ask(j, x)$$$ is at least $$$t (k + \left\lceil\frac{n}{2}\right\rceil)$$$ for the other $$$j$$$ in the current subproblem. By doing this we can split the functions into the functions less than the pivot, and functions more than the pivot.

This requires an expected $$$O(m + log(m) log(10^{18}))$$$ operations when splitting $$$m$$$ functions, so we need in total only $$$O(n \log(n) + n \log(10^{18})) = O(n \log(10^{18}))$$$ operations, which should fit into the bound.

→ Reply

5 years ago, # |

-47

I think can't pass D because of lines:

if (n > m) {
swap(n, m);
}

I did not find the anti test. Please count my solution as correct if this is the case :(

→ Reply

5 years ago, # ^ |

-70

gop2024 please look this. I know it looks stupid but I don't want to lose points because of this.

→ Reply

5 years ago, # ^ |

-51

Give me more minuses. My logic was correct. If it was n <= m code will passed. You are ratists even did'nt read what I wrote. I wish your solutions failed due to checker get Compilation Error on test 99 and etc.

→ Reply

BOOBA

5 years ago, # ^ |

Lol. If you swap lines, you swap coordinates. So you should also swap coordinates in your algorithm

→ Reply

Hsx

5 years ago, # |

Why the system test still pending?

→ Reply

nishit5

5 years ago, # ^ |

started !!

→ Reply

HYDROXIDE

5 years ago, # ^ |

It has started.

→ Reply

5 years ago, # |

-122

everyone should be given positive bonus rating because of unexpected power cut occurred before start of exam ..... it mentally affected many people ,hence not giving their best output in exam.....

note: if some one don't like it ,kindly don't down vote it as i already have negative contribution, just ignore this comment and move on.

→ Reply

KalasLavas

5 years ago, # ^ |

Actually it made me feel lucky, due to wrong timing I thought contest will start 1 hour later than actual time

→ Reply

5 years ago, # ^ |

-17

how do i delete my comment????

→ Reply

5 years ago, # ^ |

It is impossible, I think

→ Reply

5 years ago, # ^ |

+13

The power companies should give everyone free money because of unexpected power outage... it mentally affected many people.

→ Reply

5 years ago, # |

Any hints for Div1 D?

→ Reply

do_good_

5 years ago, # |

How to solve DIV2 E ?

→ Reply

5 years ago, # ^ |

I wrote a brief explanation here: https://codeforces.net/blog/entry/67813?#comment-520927

→ Reply

Jhin

5 years ago, # |

When your rate reach the buttom look at the bright side there's one way to go (me trying to motivate myself after my stupidity streak this month)

→ Reply

balanda_0iq

5 years ago, # |

Div2B have bad pretests.

→ Reply

5 years ago, # ^ |

And a lot of people had wrong solutions, FeelsBadMan

→ Reply

phyzzmat

5 years ago, # ^ |

+17

Strangely enough, almost always in Div. 2 problem B has the worst [pretests passed / accepted] ratio. Not sure about the reason for this phenomenon.

→ Reply

rajat_2548

5 years ago, # ^ |

div2B is pain in my ar**hole

→ Reply

5 years ago, # ^ |

That's what she said, not sure if it was about div2B :-/

→ Reply

5 years ago, # ^ |

It's a comparative thing. Before system test, my standing was 618, after system test, it's 557. So if you avoid all pitfall but others not, you can have a better standing. The contestants who found the pitfall and avoided it should have an advantage over those don't.

→ Reply

5 years ago, # |

+84

Good old five-problem contest. Skill over speed. Thank you.

→ Reply

do_good_

5 years ago, # ^ |

← Rev. 2 →

+25

I like this grand old way of 5 problems. I personally don't enjoy subtasks and contests which has very large problems like 7 — 8+. less and good questions are good to stay you focus during the contest, rather than moving here and there to solve subtasks.

→ Reply

5 years ago, # ^ |

+18

I doubt it's possible to make skill over speed contest if it lasts less than, at least, 2h30m. When contest lasts a bit longer even if it has more problems in it, there's much more bigger probability that you will reach problems you can't solve because of your skill and not speed before the contest time ends.

→ Reply

Nazarbek.Baltabaev

5 years ago, # |

-13

Hackforces

→ Reply

5 years ago, # |

← Rev. 2 →

-137

Please make pretests not so strong next time :)

It seems like there are no fails on systests at all

→ Reply

mango_lassi

5 years ago, # ^ |

+60

Are you really suggesting they should intentionally make pretests weaker?

Imagine failing to system tests because the specific corner case your code didn't handle was removed from the pretests, while others fail pretests and can fix their code. Yeah, no thanks, more rounds like this please.

→ Reply

5 years ago, # ^ |

-71

I suggest that pretests shouldn't cover, like, everything.

So it's more about they shouldn't make them intentionally strong.

→ Reply

ksun48

5 years ago, # ^ |

← Rev. 3 →

+18

If you are bored with nothing to do, I wouldn't mind knowing what's wrong with my D. :)

EDIT: I just mean I want someone to debug my code :)

→ Reply

5 years ago, # ^ |

+91

Well, it clearly says that.

wrong answer 1st numbers differ — expected: '204997350968', found: '204998250971'

You output incorrect number.

→ Reply

5 years ago, # ^ |

Brilliant explanation on how the WA verdict works! You should totally write a blog on that.

→ Reply

Benq

5 years ago, # ^ |

← Rev. 4 →

+13

Your code only computes the correct answer for paths through the first centroid found. This seems to suffice for almost all cases (as Radewoosh mentioned), but not always when the tree has two centroids (which test case 103 satisfies). Try comparing my getAns function with your get_subtree function.

EDIT: As saketh mentioned, there are also counterexamples where the tree has only one centroid.

(mine) 55894131

(yours) 55893926

→ Reply

agtxdy_orz

5 years ago, # ^ |

Can you please tell if my solution for D is correct?
The final structure will look like a cycle with branches coming out of the nodes which are a part of the cycle. Let there be 'x' nodes in the cycle and size of the subtree going out of these x nodes be a_1,a_2,...,a_x. So now there will be an extra path from any node in one subtree to other subtree. Thus there will be a_1*(a_2+a_3+...+a_x) + a_2*(a_3+a_4+...a_x) +...+ a_x-1*(a_x) extra paths. This can be written as: ((a_1+a_2+...+a_x)^2 — (a_1^2+a_2^2+...+a_x^2))/2 . First term is equal to n^2. So we need to minimize 2nd term.
So now choose arbitrary root. Let there be a node 'u' with 2 of its children u_1,v_1. let say we want to connect u_1 , v_1 then 2nd term of above equation will become u_1^2+v_1^2+(n-u_1-v_1)^2 . Similarly if want to connect a child of u_1 say u_2 to v_1 then the 2nd term will become u_2^2+(u_1-u_2)^2+(n-u_1-v_1)^2. This expression is less than that if we connected u_1,v_1. So we can say by induction that for any node 'u' we will want to connect 2 of its leaves such that their lca is 'u'. Now if sizes of subtree of node 'i' is denoted by s_i then we can define 2 values for each node: d_i=min(d_i,d_child+(s_i-s_child)^2) and f_i=d_i+(s_i)^2-2*n*s_i. We can show that the second term of above equation can be written as:
if a node 'u' has only one child: n^2+f_child.
if a node 'u' has more than one child: n^2+ f_child1 + f_child2 +2*(s_child1)*(s_child2).
Now our equation was telling us number of extra paths on adding an edge, so it must be positive and for any node 'u' if we subtract the second term from first we get -(f_child) or -(f_child1 + f_child2 +2*(s_child1)*(s_child2)) respectively which means that f_i will be negative. So for any node if we choose 2 of its children such that their f_i are smallest among all children we can get the max number of extra paths added. So we find this for all nodes and find their max.

My solution:55909246

→ Reply

5 years ago, # ^ |

-18

Better call GreenGrape

→ Reply

5 years ago, # |

+24

I have only looked at problem C so far, but it is already enough for me to conclude that it was a brilliant round. Thanks guys!!!!!!!!!!!!

→ Reply

coder_pulkit_c

5 years ago, # |

Wasn't Div2-C easier than Div2-B ?

→ Reply

5 years ago, # ^ |

-26

(Give me negative vote).Div2D was easier than B and C.

→ Reply

Mohammad.H915

5 years ago, # |

System testing completed good rate for everyon.

→ Reply

5 years ago, # |

+189

pctr

→ Reply

5 years ago, # ^ |

+70

XD I’ll try to write a new one tomorrow ;)

→ Reply

mnbvmar

5 years ago, # ^ |

+180

A new meme?

→ Reply

Froz

5 years ago, # |

I've never waited so long for systest/rating changes!! Good round tho :-)

→ Reply

5 years ago, # |

11 and counting :P

→ Reply

priyansupulak

5 years ago, # |

can someone help me in Div2 problem B.

I am getting wrong answer in test_case #60.

→ Reply

undefined_error_

5 years ago, # |

Any hints for div2C? Thanks :)

→ Reply

Sixpathsguy

5 years ago, # ^ |

See what happens after queries become very large

→ Reply

5 years ago, # |

+19

Is this true that in d1d optimal path will contain the centroid of the tree? Does anybody have a proof/a counterexample?

→ Reply

5 years ago, # ^ |

What do you mean by optimal path? Could you share some hints about how to solve the problem?

→ Reply

5 years ago, # ^ |

By optimal path I mean the path between vertices which will be connected with an additional edge. The hint is that if we group the vertices by the vertex on the path which is closest to them, only the sizes of the groups matter somehow (you have to minimize the sum of squares of these sizes).

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Hmm, don't know about centroids, but there always is an optimal path which connects two leafs.

(Guess it's obvious though)

→ Reply

saketh

5 years ago, # ^ |

← Rev. 2 →

+115

It's false. This type of graph produces a counter-example:

There are $$$N = W + 2T + 2$$$ nodes. When $$$2(W + 1) > N$$$, $$$C$$$ is the unique centroid.

The orange edge produces an optimal path going through $$$C$$$. The number of simple paths when adding it is $$$2 { N \choose 2 } - { T + 1 \choose 2 } - { W \choose 2 }$$$.

The blue edge produces $$$2 { N \choose 2 } - { W + 2 \choose 2 }$$$ simple paths. Any choice of $$$W$$$ and $$$L$$$ such that $$$C$$$ is the unique centroid and $$${ W + 2 \choose 2 } < { W \choose 2 } + { T + 1 \choose 2 }$$$ produces a counter-example.

$$$W = 17$$$, $$$T = 8$$$ is one such choice.

→ Reply

saketh

5 years ago, # ^ |

+59

E869120 may be interested in this type of graph.

→ Reply

EmilConst

5 years ago, # ^ |

← Rev. 2 →

+46

Lets give it to him as a gift for his next birthday :D

→ Reply

E869120

5 years ago, # ^ |

← Rev. 5 →

+81

After reading socketnaut's comment, I wondered that what is the minimum case which all of optimal path does not contain any of the centroid of the tree.

I wrote a brute-force code, and proved that there is no such case which is $$$N=3,4,5,6,7,8,9,10$$$ and $$$11$$$. Seems like socketnaut's counter-example ($$$N=35$$$) could be the minimum.

Source Code of Brute Force: Link

UPD: Finally I realized that socketnaut's second comment means my user photo :)))))))

→ Reply

saketh

5 years ago, # ^ |

:) "Who is this man and why is he trying to sell me this graph."

I have some intuition for why this form might produce the smallest possible. Adding leaves to $$$C$$$ is the best way to make it be the centroid without incentivizing the best path to go through $$$C$$$. Or to put it a different way, if the best path doesn't pass through $$$C$$$, we can reformat all of the subtrees that are below $$$C$$$ and away from the best path into leaves attached directly to $$$C$$$. Such a change doesn't worsen the best path and doesn't improve the paths going through $$$C$$$.

Going to the best path, suppose that the blue edge connects some vertices $$$u$$$ and $$$v$$$, and $$$\ell$$$ is their LCA when the tree is rooted at the centroid. If either $$$u$$$ or $$$v$$$ has a "worse" path coming down from $$$\ell$$$, the orange edge can always connect the centroid to the one that is better. So, we need them to be symmetric. Minimizing the path between $$$C$$$ and $$$\ell$$$ and making the trees from $$$\ell$$$ down to $$$u$$$ and $$$v$$$ linear gives the best configuration.

→ Reply

jef

5 years ago, # |

My solution to Div. 2 D TLEed on TC74 when compiled with MSVC++ while the same exact solution ran in 280ms when compiled with G++. A custom test shows that my solution ran in 1029ms when compiled with MSVC++. Is MSVC++ really that much slower than G++?

→ Reply

5 years ago, # ^ |

Ah that's sad. Probably the constraints were too tight. Even I got TLE & afterwards got an AC just by replacing all cout's with printf.

→ Reply

jef

5 years ago, # ^ |

Agreed. I was only able to get AC using VS by using printf, not even cout with ios_base::sync_with_stdio(false) ran in time, which I previously thought was only slightly slower than printf. I can't think of why the constraints need to be this tight, since as far as I can tell there isn't an easier solution that needs to be prevented from passing.

→ Reply

bugProductor

5 years ago, # |

I am not sure if this is a right place to put my idea/complaint . I am from Beijing,Chine, and in the contest last night , I refresh codeforces.com and m2.codeforces.com for 25 minutes only to find a series of "This site can’t be reached". And this situation is common before. According the comments following the blog of Round569 , people out of China didn't encounter this annoying process. So , I write this wanting you to know what happens in China and hoping for a response. Maybe you buddies can help me to let worker in codeforces know the situation? :)

→ Reply

300iq

5 years ago, # ^ |

+11

Try codeforc.es

→ Reply

joe_joe

5 years ago, # ^ |

that site works perfect , with only few seconds to load , which is uncommon in cf. thanks!!!

→ Reply

wangyiming123

4 years ago, # ^ |

good English, dude

→ Reply

5 years ago, # ^ |

I am from Shanghai China, I did not encounter the situation you said. Maybe it's because the Great Fire Wall. Because of 70th anniversary of China, the censorship is strong now. I use VPN to visit Codeforces. Try using VPN.

→ Reply

joe_joe

5 years ago, # ^ |

待我肉身翻墙日，youtube上把党夸

→ Reply

daniel14311531

5 years ago, # |

← Rev. 2 →

+13

I should try this round because I think I can solve all problems in div.2 , but I am afraid that I will get lower rating. Maybe I should be braver.

→ Reply

5 years ago, # ^ |

In the short run, your rating may fluctuate. But in the long run, your rating converges to your skill. Participating and practicing more improves skill. So just calm down and focus on the long term performance. That's how I convince myself to not afraid of a drop in rating and participate as many as possible. Hope that helps.

→ Reply

5 years ago, # |

Hi. So I was wondering about my submission for Problem B here.

The verdict says 'wrong answer multiply isn`t maximal possible', but not something like 'expected X but found Y'.

So, I just want to know whether there is some issue here? I don't see where my submission is wrong

→ Reply

nishant403

5 years ago, # ^ |

I have also done the same mistake , that you dont have to choose only positive max element. but negative max element (in absolute value) can be better choice .

Eg -5 2 3 Here answer will be 4 -3 -4

→ Reply

https://codeforces.net/blog/entry/67813?#comment-520927

5 years ago, # ^ |

← Rev. 2 →

Oh no! I messed up the compare function. Should have payed more attention while coding it.

UPD: Changing compare function still doesn't work sadly :(

→ Reply

alphatrance

5 years ago, # |

← Rev. 2 →

+12

Again Editorials are late.

This is actually becoming very common these days. Earlier the editorials were published right after the system tests, but now they come really late.

→ Reply

pupiI

5 years ago, # |

← Rev. 2 →

+88

the editorial flies away~~ pigeon is walking~~~

→ Reply

lzoilxy

5 years ago, # |

So where is the Editorial

→ Reply

manoj_269

5 years ago, # |

if my submission got hacked, then how to know for which test case the submission is wrong??

→ Reply

Sturdy

5 years ago, # ^ |

Resubmit the hacked solution

→ Reply

dhruv_garg

5 years ago, # |

How to solve Div 2(Problem E)??? Anyone..thankyou

→ Reply

soul_voyage

5 years ago, # ^ |

← Rev. 2 →

→ Reply

kansalanmol0609

5 years ago, # |

Problem D: I submitted Submission 1 but it was showing 'TLE'. But then I again submitted by just changing 'endl' to '/n' and it got submitted. Accepted Submission. Please explain why this happened?

→ Reply

as34

5 years ago, # ^ |

← Rev. 2 →

+14

endl always causes a flush oepration, "\n" does not!Thats why endl is slower.

→ Reply

goyal.amanrocks

5 years ago, # |

How to solve Valeriy and Deque? I have used this code (python) but I am getting TLE in case 4 ~~~~~ n, q = map(int, input().split()) s = list(map(int, input().split())) query = [] for _ in range(q): query.append(int(input()))

if  q > 0:
    for i in range(1,query[-1] + 1):
        if i in query:
            print(s[0], s[1])

        if s[0] > s[1]:
            temp = s.pop(1)
            s.append(temp)
        else:
            temp = s.pop(0)
            s.append(temp)

~~~~~ Please any help will be appreciated

→ Reply

VadymKa

5 years ago, # ^ |

Queries can be up to 10**18. Don't you think it is kinda big number, u know?

→ Reply

goyal.amanrocks

5 years ago, # ^ |

Yeah. Could you suggest a better solution? I saw various accepted solutions but its hard to understand the logic of whats happening there

→ Reply

5 years ago, # ^ |

After make the biggest number in the first place... Guess what will happen then.

→ Reply

goyal.amanrocks

5 years ago, # ^ |

After making the biggest element first all the element in the second place will move to the last position. And that would be a cycle. I under stand the part when the query is smaller than the position of biggest number in the list. But when the query is bigger than that no matter what the first number will be the biggest number but I do not understand a way to figure out second position number.

I have seen the editorial and don't understand how they got the index position of the second position number.

→ Reply

5 years ago, # ^ |

Just use an array to record the answer of a cycle. Record the length of a cycle as well. To a big query, notice that the answer is related to (query_num — p1)%p2 , where p1 is the length of getting the biggest number as the first number and p2 is the length of a cycle. https://codeforces.net/contest/1180/submission/55891794 You may refer to my solution.

→ Reply

pupiI

5 years ago, # |

Can someone prove the correctness of 55895158 (Div.1 D)? I calculated the answer using a method similar to the tree diameter. I just guessed it but don't know how to prove it.

→ Reply

fazeel

5 years ago, # |

+21

May I get the editorial for this contest? gop2024 for Contest #569 (Div.2)

→ Reply

5 years ago, # |

Can someone help me understand div1 D? I can't see why in the first sample case the answer is 2. Won't he just add an edge between both nodes, then there can only be one simple path containing both edges that goes to both nodes? Otherwise it would break the rule "we consider only simple paths of length at least two".

→ Reply