Codeforces Round #321 (Div. 2)

9 years ago, # |

Do you mean Kefa ?

→ Reply

HIT_Attacker

9 years ago, # |

i just want raising rating .......

→ Reply

tahankentut

9 years ago, # ^ |

+21

Unfortunately, the probability of all users get raising rating is zero :(

→ Reply

Afrouz_Jabal

9 years ago, # |

-16

hope to see hard math problems :)

→ Reply

9 years ago, # ^ |

Maths problems is sometimes interesting(brainstorm). But too many maths problems will make my brain feel tired.

→ Reply

Huyum_nik

9 years ago, # ^ |

-14

Занимаешся футболом и любишь матиматические задачки????

Страный ты однака...

→ Reply

Fake.No1

9 years ago, # ^ |

i agree

→ Reply

Huyum_nik

9 years ago, # ^ |

-9

i too

→ Reply

9 years ago, # |

+16

Div. 1 guys do not make new accounts please. :)

→ Reply

Azret

9 years ago, # ^ |

-14

Toooo_Simple

→ Reply

Kareem

9 years ago, # ^ |

+37

Why did you make a new account then ?
You're unrated and you know that some of div1 contestants make new accounts and you know the whole story, Then definitely you're not new to Codeforces and I can say that you already have another account!

→ Reply

-_-

9 years ago, # ^ |

Why did you?

→ Reply

m.Elbarbary

9 years ago, # ^ |

The one who is doing that is a retarded person!

→ Reply

strange_voice

9 years ago, # |

← Rev. 2 →

I hope that it does't be dynamic. How about you? Do you agree with me?

→ Reply

Gold_Soul

9 years ago, # |

-8

we want div.1 contests .

→ Reply

9 years ago, # |

← Rev. 2 →

My last contest in summer! I'm going to school on Wednesday! Hope a good contest! Good Luck!

→ Reply

ialwaysusethisaccount

9 years ago, # ^ |

but from your profile it looks like this will be your first contest.

→ Reply

9 years ago, # ^ |

this will be My first contest but My last Summer contest , ok ?

→ Reply

Fake.No1

9 years ago, # ^ |

Oh My God :) , are You sure this contest your first contest? But I think this contest is your first contest by fake Account

→ Reply

9 years ago, # |

+94

I am no longer scared of fake contestants. If my rating goes down, its because I suck, and not because of anyone else.

→ Reply

tourleader

9 years ago, # ^ |

+28

Yes the sucker man!!!

→ Reply

9 years ago, # ^ |

Lol

→ Reply

9 years ago, # ^ |

Get better than their main accounts and take their real rating as revenge!

→ Reply

winnerofround321

9 years ago, # |

← Rev. 2 →

-20

Hello my friends ;)

→ Reply

9 years ago, # ^ |

+13

Check the 1st version of his comment . He called everyone b*****s >_<

→ Reply

winnerofround321

9 years ago, # ^ |

← Rev. 2 →

-23

It was just a typo my friend ;)

→ Reply

9 years ago, # ^ |

+18

Ugh!!! Don't you just hate it when you write "friends" and codeforces autocorrect changes it to "b*****s" ? :p

→ Reply

latisel

9 years ago, # |

Scoring will be 500-1000-1500-2000-2500?

→ Reply

Vladik

9 years ago, # ^ |

→ Reply

branimir116

9 years ago, # |

In my whole country adsl is down. I'll be solving this contest on mobile net :)

→ Reply

Afrouz_Jabal

9 years ago, # |

750 points for div2 A :| from where that it cant be very nice i think it will be a long boring brute force :(

→ Reply

9 years ago, # ^ |

This can also mean difficulty of A,B,C is not necessarily in that order.

→ Reply

huge_kuriboh

9 years ago, # |

Why doesn't codeforces allow a little bigger hack files? There are solutions that will get time limit exceeded when the constraints are used but the files are bigger than 256 KB.

→ Reply

Kvark161

9 years ago, # ^ |

You must write a test generator

→ Reply

huge_kuriboh

9 years ago, # ^ |

There's only field for writing the test case, right?

→ Reply

diptesh1ce3

9 years ago, # ^ |

In such case, you should write test-case generator.

→ Reply

uSeemSurprised

9 years ago, # |

MLE on pretest 1 in D :(

→ Reply

CrazzyBeer

9 years ago, # |

← Rev. 4 →

What for the sake of God is wrong with pretest 9 Div 2 C?

Isn't it finding the longest non zero subsequence from an arbitrary vertex I with no childs?

→ Reply

micklepru

9 years ago, # ^ |

i believe there was situation when parent has larger index than a child

→ Reply

CrazzyBeer

9 years ago, # ^ |

Damn, should have thought about this. I shall try after the system testing.

→ Reply

geekSoul1

9 years ago, # ^ |

I don't know maybe my approach is wrong but I run DFS to see if we can reach at leaf without consecutive vertices's containing cat or not and add it to the result! But my code was failing on test case 8 and 9

My code was failing on test case 8 This code http://paste.ubuntu.com/12523672/ and after swapping the index of the x and y when x > y My code failed on test case 9 http://paste.ubuntu.com/12523669/

→ Reply

zoomer

9 years ago, # ^ |

just add an extra line:

adj[x].push_back(y);

to:

adj[x].push_back(y);
adj[y].push_back(x);

and I don't know what the if statment while reading really does!!

→ Reply

9 years ago, # ^ |

My wrong assumption — If 1 is leaf, don't count it in answer. I kept counting it and kept getting failed submissions.

→ Reply

conal

9 years ago, # ^ |

How can 1 be leaf when 1 is root and n>2

→ Reply

9 years ago, # ^ |

1-2 2-3 3-4 3-5

1 is root and a leaf(in a way)

→ Reply

branimir116

9 years ago, # ^ |

How is 1 a lead in a way? I has 2 for a child

→ Reply

9 years ago, # ^ |

Draw it on a paper, ad see for yourself. Clearly, assuming 1 to be leaf was wrong n this problem, but not in general, when the tree is unrooted. That's why it was failing.

→ Reply

conal

9 years ago, # ^ |

Leaf is a node with no child. 1 has a child 2. Seems like you got bit confused about leaf.

→ Reply

9 years ago, # ^ |

I suppose yes. I used the condition 'only 1 adjacent node' to identify leaf.

→ Reply

conal

9 years ago, # ^ |

How can 1 be leaf when 1 is root and n>=2

→ Reply

RetiredAmrMahmoud

9 years ago, # |

A lot of pretests, yet smooth system testing and no issues. Really nice contest.

→ Reply

Boxer

9 years ago, # |

How to solve E problem?

It was so interesting.

→ Reply

sgtlaugh

9 years ago, # ^ |

I passed pretests with hashes + segment tree for updating hash value in a range.

→ Reply

Reyna

9 years ago, # ^ |

Segment + Hash

→ Reply

9 years ago, # ^ |

← Rev. 2 →

I pass the pretests by compressing all values to bits.

→ Reply

RetiredAmrMahmoud

9 years ago, # ^ |

I thought about this and hashing also, but I couldn't figure out a way to check the query correctness except by iterating on each block and check if the hashes/bits equal.

How to do this part quickly?

→ Reply

ifsmirnov

9 years ago, # ^ |

+29

String s[l, r] has period d if s[l, r-d] = s[l+d, r]. You can get the hash of a substring with a segment tree.

→ Reply

RetiredAmrMahmoud

9 years ago, # ^ |

I feel so stupid right now ._.

→ Reply

-Wave-

9 years ago, # ^ |

+11

That's brilliant, I've never seen this trick before.

→ Reply

sgtlaugh

9 years ago, # ^ |

← Rev. 3 →

-8

Except when d = r — l + 1. Nice observation though :)

→ Reply

9 years ago, # ^ |

+21

I get TLE after system test. XD

→ Reply

9 years ago, # ^ |

In my room, MrDindows successfully solve it by treating all character as long long. You can refer his code: http://codeforces.net/contest/580/submission/13165100

→ Reply

ashish1610

9 years ago, # ^ |

Hey, can you explain his code. He is using memset and that is O(n) if I am not wrong. His solution seems to be O(n) per query.

→ Reply

9 years ago, # ^ |

You can find many information about memset from Internet.

→ Reply

ashish1610

9 years ago, # ^ |

Lets ignore the memset part. His query is still O(n).

→ Reply

9 years ago, # ^ |

He do some thing to speed up the constant part of his algorithm such as treat character as long long and expand the while loop.

I guess these changes of code will make CPU execute lesser command. (I'm not familiar with the detail, but I know these are common trick to speed up your code.)

→ Reply

manishabukhredia7

9 years ago, # ^ |

How to deal with cyclic dependcy in D ?

→ Reply

gvishal

9 years ago, # ^ |

Since the constraints are small, it can be solved by dp + bitmasks.

→ Reply

SirNickolas

9 years ago, # ^ |

Does anyone have any ideas how to solve Div2E without using hashing?

→ Reply

M.Mahdi

9 years ago, # ^ |

← Rev. 4 →

Ignore... It's wrong.

→ Reply

9 years ago, # ^ |

← Rev. 3 →

Why lcm(next_k1, $next_{k2}

Unable to parse markup [type=CF_TEX]

) | d ?

What do your k_i means?

→ Reply

M.Mahdi

9 years ago, # ^ |

Sorry, I just figured out it's wrong.

→ Reply

himanshujaju

9 years ago, # |

how to solve E ?

→ Reply

fr0st

9 years ago, # |

Pretest 9th for C ?

→ Reply

CrazzyBeer

9 years ago, # ^ |

Maybe here

→ Reply

ha1vanka

9 years ago, # |

+24

I was unable to submit in the last 60 seconds because codeforces was too busy. I hate it when that happens.

→ Reply

gepardo

9 years ago, # ^ |

And I was unable to hack in the last 60 seconds.

→ Reply

sampriti

9 years ago, # ^ |

Same here :/ I tried to hack in the last 20 seconds, but the challenge wasn't submitted.

→ Reply

MrNull

9 years ago, # ^ |

← Rev. 3 →

same as your problem :|

solved D but It didn't submited, also in previous contests I have this problem too!!!

→ Reply

grayhathacker

9 years ago, # ^ |

same here...

→ Reply

Huyum_nik

9 years ago, # ^ |

-18

Блин решил последние две задачи а кодфорцез затупил и я не сумел послать(((((((((( уверен, это дело рук красных они бояться конкурентов и поэтому зажимают F5 на последних минутах и кодфорса ломаеца. предлагаю ограничивать красным доступ на сайт на время контестов.

→ Reply

LashaBukhnikashvili

9 years ago, # |

← Rev. 2 →

I don't like problem scores!!! u think difference between problem C (or B) and D should be ONLY 500 (or 750).than it's same to solve A+B instead of D. May be my fault coz I solved only A,C,D(coz of not enough time),but anyway I don't think that this correct: man who solved first 3 problem is in front of me in list... D is much harder than A+B+C -_- sorry for my open mind

→ Reply

ilidar

9 years ago, # |

What's the problem with code generated tests ? I've got this one:

Validator 'valid.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]

Thanks in advance.

→ Reply

Kvark161

9 years ago, # ^ |

validator wants '\n' in the end of a test.

→ Reply

ilidar

9 years ago, # ^ |

Check this out.

→ Reply

KolopJr

9 years ago, # ^ |

Your test has extra space

→ Reply

Kvark161

9 years ago, # ^ |

Error: space is in the end of the second line.

It's correct:

for (int i = 0; i < 100000; ++i) {
  printf("%d", i + 1);
  if (i + 1 != 100000)
     printf(" ");
}

→ Reply

ilidar

9 years ago, # ^ |

← Rev. 3 →

Thanks, guys. That's just hilarious ;-(.

→ Reply

9 years ago, # |

Is there anything need to pay attention to in the C problem? I failed to pass the 8th test and i can't find any mistakes.

→ Reply

suraj021

9 years ago, # ^ |

Me too. :(

→ Reply

9 years ago, # ^ |

I just see the test data and I found it was because I wrongly think xi and yi in input mean xi is yi's father node.

→ Reply

lifecodemohit

9 years ago, # ^ |

You assumed given graph(tree) to be directed.

→ Reply

CATIGERN

9 years ago, # |

Can someone suggest an approach for 2nd? I basically sorted the friends based on their money, and I was then going to group friends based on the condition and sum their friendship factor, and check which group has the most. Is there a better way to do it? or any flaw in my solution.

→ Reply

brighterstill

9 years ago, # ^ |

← Rev. 3 →

you can read about the two pointer technique , and try solving the problem.

→ Reply

9 years ago, # ^ |

Firstly,sort the friends based on their money.Then,enumerate every element in array and use the function "lower_bound" to find the first element which is bigger than the it.And use the sum of factor between the two element to update your answer

→ Reply

9 years ago, # ^ |

← Rev. 3 →

1) sort based on money

2) find prefix sums for friendship factors

3) for i=1 to n
a) use any O(log n) mechanism to find index j such that money[j]>=money[i]+d ... I used c++ map for this.
b) ans = max (ans,prefix_sum[j-1]-prefix_sum[i-1])

→ Reply

xennygrimmato

9 years ago, # ^ |

I had the same solution. Used std::lower_bound(a + i, a + n, a[i] + d) to find the least index ahead of i which I can not select, if I select i.

→ Reply

binary_eagle

9 years ago, # ^ |

Index j is also invalid so why are you doing prefix_sum[j-1] and not prefix_sum[j] ?

Am assuming that i > j as we are considering the ith element and the old set if in [0..i-1]

→ Reply

Sort + Two Pointers O(nlogn)

9 years ago, # ^ |

Assume your set starts from i. We have sorted in ascending order of money so j>i because j is the lowest index you need to exclude if the set starts from i such that money[j]>=money[i] + d ... you can set money [n+1] = INF ... Include all elements from i to j-1 in current set and to get the sum of friendship factors of such ranges/sets of in O(1), I pre-calculated prefix sums. To get sum of elements from i to j-1, you need to subtract prefix[i-1] from prefix[j-1].

→ Reply

deinier

9 years ago, # ^ |

← Rev. 2 →

→ Reply

9 years ago, # |

Can someone explain D soln ?

→ Reply

LashaBukhnikashvili

9 years ago, # ^ |

I solved it by DP, take a d[n][2^n] array,where d[i][j] means what is the best answer when last dish is i and j represents which dish I tasted before it,(1 means tasted,0 not tasted)

→ Reply

volverine

9 years ago, # ^ |

dp[mask][j] — best answer if we finish eating at j — dish, and ate all dishes in mask. O(n^2 * 2^n)

→ Reply

MahmoudSayed

9 years ago, # ^ |

← Rev. 3 →

-15

constrains of n & m are small. I think it can be solved using recursion trying all possible ways.

UPD: it will pass only by using memoization..

→ Reply

crbonilha

9 years ago, # ^ |

← Rev. 2 →

That would be about N!-(N-M)!, which is too much.

→ Reply

9 years ago, # ^ |

Aren't all possible cases O( P(n,m) ) ? (Which should be too high for recursion)

→ Reply

MahmoudSayed

9 years ago, # ^ |

← Rev. 3 →

I'm sorry for this. I updated it.

and here's my solution: http://codeforces.net/contest/580/submission/13170384

→ Reply

ha1vanka

9 years ago, # ^ |

Well, I think it is almost the same as the Traveling Salesman Problem

You have a graph, where the dishes are the nodes and the eating rules are the edges

dp[y][bit_mask]:

y is the last node you visited (dish you ate)

bit_mask is bit mask in which if the Nth bit is set it means that somewhere along the path you visited node N (ate dish N)

dp[y][bit_mask] = max (dp[x][bit_mask — (1 << y)] + eating_rule[x][y] + a[y])

if there isn't a eating rule between x and y than eating_rule[x][y] should be zero

so your final answer is the best dp[y][bit_mask] where bit_mask contains exactly M ones

you have N * 2 ^ N states and the you need O(N) for each, so total complexity is O (N^2 * 2^N)

→ Reply

xennygrimmato

9 years ago, # ^ |

Used same idea, got AC in Practice. Link to Code

→ Reply

binary_eagle

9 years ago, # |

Went out and could not fully participate in contest. Too bad!!!.

My thinking of how to solve Div2 B.(not sure if its correct)

Sort set S by amount.

Suppose we have <n=k people already to be a company. They are K-1 of them in number.

Consider the Kth person.

Case 1 : He should be in company. This is only possible if this amount is a < S[0].a That is it is smaller than the amount of the smallest person in the group.

Case 2: His amount is bigger.

In this case, we can use binary search to find a range of numbers that conflict with the Kth person, we sum the total factors of this said group.

We have to choose between the whole group and the Kth person. Which ever increases the overall amount.

Please would this have solved the problem???

→ Reply

katalonecfly

9 years ago, # ^ |

I got AC using this approach

→ Reply

binary_eagle

9 years ago, # ^ |

OMG!!!, I can't believe i just threw away my chance of turning blue today. Oh well, i'm happy i got the approach at least. Lets wait for the next round.

Thanks for the reply Expert Katalonecfly.

→ Reply

adnanSharif

9 years ago, # |

Can't wait to see the rating change!!!

→ Reply

dush1729

9 years ago, # ^ |

+23

→ Reply

9 years ago, # ^ |

good picture

→ Reply

tapasjain

9 years ago, # |

were the test case for 2nd question weak because i used upper_bound instead of lower_bound in hurry and i got AC? :P

→ Reply

9 years ago, # ^ |

I used upper_bound in one failed submission. You're lucky :)

→ Reply

tapasjain

9 years ago, # ^ |

I know why it passed coz i upper_bound on make_pair(curr+d,0). If instead of 0 it would have been a greater value it would not have passed. Yes I was lucky, coz i did not see that through.

PS : the test cases weren't weak then i guess.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

-13

The test cases were not weak, but solutions that did not consider test cases similar to yours passed. Overall, the solution is still correct and adding these test cases would've made the problem unnecessarily tricky.

→ Reply

9 years ago, # |

I have this idea for D. Please tell me if you find something wrong in it.

Use bitmask to find numbers with m set bits.
From the k-rule directed tree, form a directed sub-tree which has only the vertices identified in step 1. Add their individual satisfaction values.
Start from leaf nodes. Push them in a queue. Pop only if all children of the vertex have been popped. This way, do a Comparison for every non-leaf vertex to pick the child path that gives maximum satisfaction. So, along with all child-path satisfaction values, you add only 1 extra value for joining vertex v to its max satisfaction child.

Is it correct to start from leaf nodes?

→ Reply

9 years ago, # ^ |

I don't know if it's correct but it's an overkill.

→ Reply

9 years ago, # ^ |

Ok ;_; . I'll look at the editorial then.

→ Reply

9 years ago, # ^ |

It is dp with masks. State is last eaten and bitmask of eaten so far. To solve a state you try to fix the next to be eaten.

→ Reply

joaquingc123

9 years ago, # |

Oh my god, i have disastrous bugs :'( i will cry in the bathroom.

→ Reply

deinier

9 years ago, # |

I assumed that input was (parent, child) on C!!! ... silly mistake.

→ Reply

9 years ago, # |

I agree with everything above and confirm that I will provide my own problems

Just a quote regarding D.

→ Reply

OmaeWaMouShenDeiru

9 years ago, # |

How can we solve problem B if every friend was associated with hia own value of 'd', the value that makes him feel poor.

→ Reply

http://codeforces.net/contest/580/submission/13150523

9 years ago, # ^ |

Sort + fast search algorithm.

→ Reply

deinier

9 years ago, # ^ |

Here!

→ Reply

Archazey

9 years ago, # ^ |

← Rev. 2 →

So if you fix a[i] as being the biggest of sums,you need to add all a[j]<a[i] that a[j]+d[j]>a[i].

This can be done with fenwick tree,at position a[j]+d[j] you add factor[j].

And for i the answer is query per range [a[i]+1,limit]

→ Reply

ThomazL

9 years ago, # ^ |

← Rev. 2 →

Or linear parsing, with two pointers

→ Reply

rumman_sust

9 years ago, # |

+16

Nice problem ( E — Kefa and Watch ). I found a solution using hashing + segment tree, but couldn't solve it in time. BTW is there any solution without using hashing?

→ Reply

jhonber

9 years ago, # |

← Rev. 2 →

+19

kuldeepfouzdar nice trick for Unsuccessful hacking attempts on your solution, in the problem B:

#define int long long

http://codeforces.net/contest/580/submission/13163755

→ Reply

maradonah

9 years ago, # |

Hello all,

I have a question about an unsuccessful hack that I did during the contest. I hacked the following submission as I noticed that the numbers of the sequence are stored in indices of an array starting from 1 to n. The array is of size n and hence I expected that the hack will result in run time error due to the index overflow for a large input where the size of the sequence is 10^5.

Can anybody explain to me why did the hack fail? I expect it might have something to do with the unused array f but I am not sure about it.

→ Reply

9 years ago, # ^ |

C++ doesn't have index overflow run time errors, all that happens is that it accesses memory outside the array and as long as said memory is not used for something else it will pass.

→ Reply

9 years ago, # |

How come 300 div2 participants managed to solve D? In my opinion it was a pretty hard dynamic programming problem.

→ Reply

lazyc97

9 years ago, # ^ |

← Rev. 2 →

+35

Really ? I think that's the basic form of bitmask dynamic programming though

→ Reply