8VC Venture Cup 2017 — Final Round and Codeforces Round #393

8 years ago, # |

+54

That's funny, my dad and Joe Lonsdale are really close friends, I get to meet Joe all the time. :)

→ Reply

8 years ago, # |

+90

Before Joe Lonsdale started 8VC, he worked with my dad in the company: formation8. Sadly, they split up! My dad started a company that has "formation" in it, and Joe started a company that has, "8" in it! So cool!

→ Reply

C137

8 years ago, # ^ |

-72

Joe Lonsdale company make codeforces rounds, your dad's company don't, perhaps that's why they split up :V

→ Reply

8 years ago, # ^ |

+22

They used to be in an investing company together. They were like best friends. They were the founders of the company, they worked together.

→ Reply

keyvankhademi

8 years ago, # ^ |

+11

fair division!

→ Reply

chaosagent

8 years ago, # |

+10

How do I register if I qualified locally but am not in the top 200?

Also, I go to the same high school Joe went to ;)

→ Reply

Odin-

8 years ago, # |

← Rev. 2 →

-54

Div 2 edition will be rated? UPD1: It is rated, it was unofficial at first thats why I asked.

→ Reply

KieranHorgan

8 years ago, # ^ |

Yes, it will.

→ Reply

EdwardSnowden

8 years ago, # |

+205

"Local Winner — Dinner with Joe Lonsdale"

This Silicon Valley entrepreneurs think they are the big shit. Someday, I'm going to organize my own programming competition and I will invite the winner to meet me in a tea party in Crimea.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

-49

I agree, I'd like to do the same lol. :)

→ Reply

Sharon

8 years ago, # ^ |

Snowden offended Barack Obama as well. He's got big balls.

→ Reply

saketh

8 years ago, # |

I see the option to register for the Final Round, but I didn't place top 200 in the elimination round. Is it normal?

→ Reply

Mr_Emrul

8 years ago, # ^ |

-18

yap!

→ Reply

kliu31415

8 years ago, # ^ |

There are some people who are currently registered for the final round but did not place in the top 200 in the elimination round, so I'm guessing the option appears for everybody.

The CF admins probably just assumed everyone would register for the correct round. I'm not quite sure how the incorrect registrations will be dealt with, so you should just register for the Div 1 version.

→ Reply

8 years ago, # ^ |

Could you give me examples? We have some exclusions because of local finalists.

→ Reply

chaosagent

8 years ago, # ^ |

I'm a local finalist but I still get the "you can't register" message.

→ Reply

8 years ago, # ^ |

Please try again. Anyway no reason to worry, for sure you'll be registered correctly.

→ Reply

UncleGrandpa

8 years ago, # ^ |

kyleliu is an example. His rank in the elim round was 852

→ Reply

kyleliu

8 years ago, # ^ |

+41

I'm also a local finalist

→ Reply

kliu31415

8 years ago, # ^ |

In the list of recently registered people I found a few users who did not list their locations as from the USA (I'm assuming local finalist means from the Silicon Valley area), but it's possible they have moved. Here are 2 examples: ctzsm dojiboy9

→ Reply

ctzsm

8 years ago, # ^ |

I am here at Addepar.

→ Reply

Emrul

8 years ago, # ^ |

When I clicked on register button , it's showed me that I am not eligible. So that's not a problem at all.

→ Reply

TShT

8 years ago, # |

-61

Rating will Dowa?

→ Reply

md.ashif313

8 years ago, # |

-11

Hope another exciting contest, interesting problem set :)

→ Reply

KieranHorgan

8 years ago, # |

-9

Contest postponed by 10 minutes?

→ Reply

8 years ago, # ^ |

+49

Sorry, it is because of onsite event.

→ Reply

har_vi

8 years ago, # ^ |

← Rev. 2 →

-91

damn everyone wants upvote!!

→ Reply

KieranHorgan

8 years ago, # ^ |

+36

No, some people just want to stay informed on what's happening with the contest

→ Reply

-is-this-fft-

8 years ago, # ^ |

+45

Ah yes, imaginary internet points. They truly are what make the world go round.

→ Reply

AGHORii

8 years ago, # |

-12

Delayed !!

→ Reply

Dey

8 years ago, # |

-12

Why delay?

→ Reply

Ashishgup

8 years ago, # |

Damn, contest delayed by 10 minutes.

→ Reply

kamishogun

8 years ago, # |

← Rev. 3 →

-55

Please ignore this comment.

→ Reply

imh1j4l

8 years ago, # |

-40

tourist GK hope u will 1st today , best of luck . zscoder u are just awesome zi song

→ Reply

amsen

8 years ago, # ^ |

+10

hoping is for us. he is first normaly

→ Reply

VastoLorde95

8 years ago, # |

+52

R.I.P. English

→ Reply

ChickenInKitchen

8 years ago, # |

+47

am i the only one failing to understand problem c statement ?

→ Reply

Ashishgup

8 years ago, # ^ |

+14

I've read it multiple times and I still don't understand what the questions wants :(

→ Reply

ChickenInKitchen

8 years ago, # ^ |

the only way is to submit wrong and wrong til it gets pretest passed !

→ Reply

Vicennial

8 years ago, # ^ |

The question could have definitely be worded better. Everyone who doesn't how barbecue is made is going to have a tough time to understand it.

→ Reply

P_Nyagolov

8 years ago, # |

+44

Will you upload English statements?

→ Reply

father_of_dragon

8 years ago, # |

+71

Unable to understand Div 2 C. Never cooked barbecue. :/

→ Reply

never_giveup

8 years ago, # |

Awful contest, problem B in russian was not full, so i couldn't solve it. Hope it will not repeat.

→ Reply

up-and-down

8 years ago, # ^ |

-19

I think it wasn't too difficult to understand the statement. Also samples can help.

→ Reply

videogamez

8 years ago, # ^ |

Same shit

→ Reply

shiro

8 years ago, # |

Awesome contest, hope that i will pass system tests.

→ Reply

8 years ago, # ^ |

What was your logic for C?

→ Reply

linkret

8 years ago, # ^ |

+14

Imagine it's a graph. You need to make it into a single cycle, and have an odd number of bs. If you have x > 1 cycles, you need exactly x operations to transform them into just 1 cycle, and then 1 more operation if the sum of all bi's is even.

→ Reply

8 years ago, # ^ |

My bad I visualized it in terms of components.

→ Reply

8 years ago, # ^ |

Why is the number of 1's should be even? Why is this bad b[4] = {0, 1, 0, 1}?

→ Reply

Vicennial

8 years ago, # ^ |

Basically, after traversing the cycle, we need to up at the same node in the opposite direction. Only then it can visit all n positions in both directions.
Even number of 1s will always lead to same direction after traversal.

→ Reply

send_nodes

8 years ago, # ^ |

If you start from a node, and walk exactly N times, you should end up in same node because ending graph should be one big cycle. Then, it follows that you can't have visited a node more than once. If you start at node X, and when you again visit it after N times, the sum of b[i] encountered is 0 mod 2, your state hasnt changed, meaning you're going to repeat the exact same cooking(no reversing really occurs).

→ Reply

YourRatzon

8 years ago, # ^ |

Even number of ones means that by the time each skewer makes a full round and returns to its original spot, it will have been flipped an even number of times, meaning it will be in the same position as it started, which is not good since we want it to be in the flipped position

→ Reply

rahulkhairwar

8 years ago, # ^ |

Imagine a cycle with any number of nodes n.

Now, if you start at a node say x, then you will travel in this order :

x -> y -> .... -> x

So, once you start at x, if the total number of inversions of the skewer is even, then you will end up at x with the same direction of the skewer because any change made in the direction will be reversed also. So, even if you traverse this cycle multiple times, you will reach each node with the same direction.

But, if there are odd number of 1's, then after 1 traversal of the cycle, you will reach x with the opposite direction of the skewer as to what you started with. Now, with another traversal of the graph all nodes have had both the directions.

→ Reply

_index

8 years ago, # ^ |

The graph is combination of cycles, you need to make graph a single cycle. And if there is even number of 1's you should change something.

→ Reply

8 years ago, # ^ |

I counted the number of cycles in permutation and then calculated the number of changes we need to make in order to combine all of these cycles into a single cycle.
If all of the numbers in b were zeros I added 1 to the answer.

This approach is failing at test 8. Either my logic is completely wrong or I made a mistake in my implementation.

→ Reply

barun511

8 years ago, # ^ |

← Rev. 2 →

Your approach will fail for the following case.

3
2 3 1
1 1 0

Correct answer is 1, not 0.

→ Reply

shiro

8 years ago, # ^ |

Oh no, tl on 80 test.

→ Reply

JiK

8 years ago, # |

+54

Will Div 1 and Final Round results be combined for the rating calculations or are those calculated separately?

→ Reply

shakil.ahamed

8 years ago, # ^ |

-13

This won't. There would be a combined contest for div1 and div2 if that was the case.

→ Reply

DragonFist

8 years ago, # |

The Contest was good, spend a lot of time on B but still unable to come up with a solution...

→ Reply

8 years ago, # ^ |

+11

Binary Search on answer.

→ Reply

hacker_de_sentimente

8 years ago, # ^ |

what was the right limit? (the left limit was 1, sure)

→ Reply

8 years ago, # ^ |

I used M i.e number of pillows given as right limit.

→ Reply

tocolor

8 years ago, # ^ |

code I used Binary search. but it didn't succeed.. Can you please see my code (what is wrong)

→ Reply

8 years ago, # ^ |

Paste it somewhere else i can't see from here

→ Reply

tocolor

8 years ago, # ^ |

-8

here

→ Reply

8 years ago, # ^ |

Your check function logic is not right. Here is link to my accepted code : here

→ Reply

tocolor

8 years ago, # ^ |

Thank you :)

→ Reply

suraj_ch77

8 years ago, # ^ |

Can you explain your logic for div 2b ?

→ Reply

barun511

8 years ago, # ^ |

← Rev. 2 →

First give everybody a pillow. Then binary search from 1 to m to see if you can give the kth position some r pillows. You can easily calculate how many pillows required in O(1) [just give the (k-1)th and the (k+1)th hobbit r-1 pillows, the (k-2)th and the (k+2)th hobbit r-2 pillows and so on..this can be calculated with the knowledge that sum of all elements from 1 to n = n*(n+1)/2 in O(1)].

→ Reply

noelnadal

8 years ago, # ^ |

Binary Search was not necessary. You could brute-force by computing the number of pillows that you need for the answer to be at least 1, 2, 3... until p, where p = max(n-k+1, k), and then you could divide the number of remaining pillows (if there are some remaining) by n and add the result to p to get the answer.

→ Reply

Vicennial

8 years ago, # ^ |

I did it the same way. Any idea what the complexity would be?

→ Reply

Aemon

8 years ago, # ^ |

Roughly O(sqrt(M))

→ Reply

allenite

8 years ago, # |

good contest

→ Reply

King

8 years ago, # |

+129

Me when I read div2C

→ Reply

bvd

8 years ago, # ^ |

I need some SAT Reading skills to understand this problem :))))

→ Reply

Fcdkbear

8 years ago, # |

How to solve D div1?

→ Reply

Akinorew

8 years ago, # ^ |

-10

Hint* Dynamic programming + binary search

→ Reply

Fcdkbear

8 years ago, # ^ |

+25

I guess I need some extra hints :)

Also are you sure you aren't talking about Div1 B?

→ Reply

Akinorew

8 years ago, # ^ |

So sorry, missread

→ Reply

TimonKnigge

8 years ago, # ^ |

Try solving the problem "Find the number of distinct subsequences of some string S (of any length)". You can use similar ideas to solve D.

→ Reply

send_nodes

8 years ago, # ^ |

Div 1

→ Reply

kingofnumbers

8 years ago, # |

← Rev. 2 →

+10

is there anyone who passed div1 D with 26*n^2 solution instead of n^2 ? because if there is then #%#%@#$@#@

→ Reply

Laakeri

8 years ago, # ^ |

+13

Yes, it runs in 1300ms. Use int instead of long long and do if (dp[i][ii]==0) continue;

→ Reply

gvaibhav21

8 years ago, # ^ |

+26

Strangely, this gave TLE with C++11 and passed in 1263ms with C++14. Never knew C++14 had so much better optimizations.

C++11

C++14

→ Reply

-Wave-

8 years ago, # ^ |

Never would have thought there is such a big difference in speed between int and long long.

→ Reply

jcvb

8 years ago, # ^ |

Mine failed

→ Reply

Vercingetorix

8 years ago, # ^ |

← Rev. 2 →

I did, 1900ms.

edit: And yeah, I also spent 30 minutes optimizing it..

→ Reply

8 years ago, # ^ |

I did, but I solved that in 13 mins and then have been optimizing it for 20 mins. I needed to change a bit flow of my algorithm to gain better use of cache and erase my beloved macro "#define int long long" and it passed in 748 ms. Maybe that cache thing was not necessary because deleting that macro sped up my program from 3,5s to 750ms on CF >_>...

→ Reply

desert97

8 years ago, # ^ |

← Rev. 3 →

Did almost everyone else do O(σ N²)? I just wouldn't imagine this passing along with modulo operations. I did waste some time figuring out how to reduce to O(N²). I did like D as a problem though.

→ Reply

jerry

8 years ago, # ^ |

← Rev. 2 →

You can do the dp in O(N²) by using a prefix sum table.

→ Reply

ania

8 years ago, # ^ |

+10

I did, with no optimizations at all. It passes in 1840ms.

→ Reply

Gassa

8 years ago, # ^ |

← Rev. 2 →

+20

Got it passed in 1.5 seconds.

The code running O(n²) times was the following (3.5 seconds locally on a random test):

code 1

				int cur = f[!b][pos];
				foreach (let; 0..26) {
					int dest = next[pos][let];
					f[b][dest] += cur;
					if (f[b][dest] >= mod) f[b][dest] -= mod;
				}

First, branching gets in the way of instruction-level parallelism. So, get rid of branching by switching f to int64 (it was int32) and taking the remainder in an O(n²) outer loop (down to 3.05 seconds):

code 2

				auto cur = f[!b][pos];
				foreach (let; 0..26) {
					f[b][next[pos][let]] += cur;
				}

This was still not enough: my compiler is dmd which sometimes produces suboptimal code. Locally, this is already fast with gdc or ldc, but they are not present on Codeforces.

So, the next thing was to streamline accesses to the transition table (1.55 seconds):

code 3

				auto cur = f[!b][pos];
				auto ptr = next[pos].ptr;
				foreach (let; 0..26) {
					f[b][*(ptr + let)] += cur;
				}

This looked fast already. But I added manual loop unrolling, just to be sure it happens (1.3 seconds):

code 4

				auto cur = f[!b][pos];
				auto ptr = next[pos].ptr;
				f[b][*(ptr +  0)] += cur;
				f[b][*(ptr +  1)] += cur;
				f[b][*(ptr +  2)] += cur;
				f[b][*(ptr +  3)] += cur;
				f[b][*(ptr +  4)] += cur;
				f[b][*(ptr +  5)] += cur;
				f[b][*(ptr +  6)] += cur;
				f[b][*(ptr +  7)] += cur;
				f[b][*(ptr +  8)] += cur;
				f[b][*(ptr +  9)] += cur;
				f[b][*(ptr + 10)] += cur;
				f[b][*(ptr + 11)] += cur;
				f[b][*(ptr + 12)] += cur;
				f[b][*(ptr + 13)] += cur;
				f[b][*(ptr + 14)] += cur;
				f[b][*(ptr + 15)] += cur;
				f[b][*(ptr + 16)] += cur;
				f[b][*(ptr + 17)] += cur;
				f[b][*(ptr + 18)] += cur;
				f[b][*(ptr + 19)] += cur;
				f[b][*(ptr + 20)] += cur;
				f[b][*(ptr + 21)] += cur;
				f[b][*(ptr + 22)] += cur;
				f[b][*(ptr + 23)] += cur;
				f[b][*(ptr + 24)] += cur;
				f[b][*(ptr + 25)] += cur;

Overall, the optimization effort took 5.5 minutes between the two submissions (one, two). Actually solving the problem took way longer for me.

→ Reply

LoveYayoi

8 years ago, # |

How to solve Probelem E? Is that sth like keep the value of sum for each suffix,-1 for pop and +1 for push, and query where the last sum which is exact 1 is?

→ Reply

unused

8 years ago, # ^ |

← Rev. 2 →

+19

I used segment tree with lazy propagation (range add update & max query). Add -1 to [0, pos] if pop, 1 to [0, pos] if push and do binary search to find the rightmost positive number. O(n lg^2 n)

→ Reply

kraskevich

8 years ago, # ^ |

We can also get rid of binary search by can starting from the root and going to the right child if it's maximum is positive. It's O(N log N) this way.

→ Reply

animeshf

8 years ago, # ^ |

Um, I'm confused, Why do you need lazy propagation for this?

→ Reply

animeshf

8 years ago, # ^ |

kraskevich We commented at the same time :P

→ Reply

linkret

8 years ago, # ^ |

To update a range in O(log n).

→ Reply

LoveYayoi

8 years ago, # ^ |

..... I came up with this idea and then forbade it.... that's too stupid

→ Reply

Tiny

8 years ago, # |

+11

struggled to debug div1 B for 40 min because of misreading 1440 as 1140 T T

→ Reply

I_love_Malika

8 years ago, # ^ |

Same here. I had WA 6 and was looking for a bug, but only looked at the 1440 place after your comment :(

→ Reply

W4yneb0t

8 years ago, # |

+145

Problem F: wow, such idea, very insight.

→ Reply

8 years ago, # ^ |

+48

Can't agree more. Who thought it is a good idea to put it on a contest? On ACM it wouldn't be that bad because we will have more time and I will have mnbvmar in team, but as a most valuable problem during a 2 hour CF round it sucks hard.

→ Reply

Coder

8 years ago, # ^ |

+41

It is good when people complain only about problem F

At least problems A, B, C and D weren't bad which is not the case for many other contests

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+20

EDIT: I refer to problem E here :D.

Not sure whether this comment was sarcastic or not, but if you really want to than I also think that bignums is a lot of fun, especially when TL is very strict (I didn't solve that problem, but heard that from friends), so that you can't use Python.

→ Reply

eatmore

8 years ago, # ^ |

+13

I solved F without using any bignums.

→ Reply

gultai4ukr

8 years ago, # ^ |

-32

I think W4yneb0t's comment is sarcastic.

→ Reply

8 years ago, # ^ |

+110

→ Reply

gultai4ukr

8 years ago, # ^ |

-10

Sorry, I do not understand your previous comment context correctly.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+61

(Want to get my -100 comment)

I'm the author. What is the problem? Swistakk is also welcomed.

bignums is a lot of fun

Really? It is a problem about bignums?

→ Reply

W4yneb0t

8 years ago, # ^ |

+18

The problem is that arriving at the solution is straightforward and the difficulty lies entirely in coding it. I personally don't find that very fun.

→ Reply

8 years ago, # ^ |

+62

Wow. I was thinking about 2 hours on how to avoid O(n²) for case 1 - 10ⁿ. You are very smart person.

And when I was writing then solution about a half of the time I was sitting with pen and paper.

→ Reply

8 years ago, # ^ |

+17

Lol, I referred to problem E when telling about bignums xD. Should have mentioned it :D.

F is surely not about bignums, but I don't like F because it has very low ratio of "difficulty of getting idea right : difficulty of coding it" and that is more or less what I use to sort problems by how fun they are. We need to parse everything (hooray) and what is left to do is to make some rules producing (length of expression mod P-1, value mod P) for every expression. Only rule which I didn't figure out was those intervals, but I didn't think about it for longer than 15 seconds, but I guess it still can somehow be done without some brilliant ideas.

Btw, I do not predict your comment to get downvotes ;p.

→ Reply

8 years ago, # ^ |

+38

E: Division bigint by int isn't very hard, is it? Also I think that there is something else in this problem (not only bignums) and this something is what the problem about.

F: Well, I added this parsing part to 1) combine some ideas in one problem 2) make it harder to code. But yes, the only hard part is those intervals and yes, it still can somehow be done. Maybe not brilliant but some ideas are needed.

→ Reply

W4yneb0t

8 years ago, # ^ |

+47

F: Then maybe the part about the intervals would make a good problem D or E.

→ Reply

8 years ago, # ^ |

+37

I get your idea that "all this other stuff like parsing and other operations are kinda boring" and I partially agree. But it was hardest problem in a not usual round (finalists should be stronger, right?). So I decide to add some coding part (but you should agree that parsing is relatively easy in this problem).

Maybe it is just unusual to see "parsing" problem in a short individual competition.

→ Reply

8 years ago, # ^ |

+20

"(finalists should be stronger, right?)" — do you expect tourist in round called "something's final" to be stronger than tourist in a usual round ; p?

→ Reply

8 years ago, # ^ |

+38

Good point :)

But rounds are made not only for tourist. Also I've expected much more AC for problem E. I'm sorry that E appeared to be more difficult than I've expected.

→ Reply

8 years ago, # ^ |

+30

E: Surely, E is pretty OK, this problem is by far not straightforward (however it is easier if you are not a retard like me and read that sum of b's is <=3e5). And dividing bignum by int is indeed lot easier than typical division, I thought that much more involved operations will be needed which led me to disliking this problem prematurely. Probably that problem without bigints wouldn't make much sense, so their existence here is very well justified.

F: OK, if you say it took you 2 hours to tackle the case 1 - 10ⁿ then I guess it is not easy, so it significantly increases ratio I mentioned :p. However I wouldn't call parsing "combining some ideas in one problem", that's very nice expression for that ;p.

→ Reply

8 years ago, # |

← Rev. 2 →

For DIV2 -C , I am counting the number of cycles and if they are != 1,I am adding it to the answer. I dont know how to handle the second array consisting of 0's and 1's. Any hint?

→ Reply

8 years ago, # ^ |

if the bitwise xor of all b_i is 0 then you should add 1 to the answer

→ Reply

8 years ago, # ^ |

I did that but got WA.http://codeforces.me/contest/760/submission/24051551

→ Reply

8 years ago, # ^ |

I am not allowed to see your submission, upload it somewhere else

→ Reply

http://pastebin.com/YhbCFETN

8 years ago, # ^ |

→ Reply

8 years ago, # ^ |

← Rev. 2 →

I got my mistake. In line 43, it should be i<=n.

→ Reply

8 years ago, # ^ |

too sad...

→ Reply

OmarKhaled_

8 years ago, # ^ |

Parity

→ Reply

RazvanD

8 years ago, # ^ |

If my idea is correct, you need to have an odd number of 1's in the second array

→ Reply

kshitij_jain

8 years ago, # ^ |

If the sum of b[i]'s is even, 1 more operation is needed.

→ Reply

Dekacc

8 years ago, # ^ |

Just count the sum of ones, and if the sum is even, add 1 to the answer (you need to flip 1 bit), if the sum is odd it's ok.

The sum of the flips has to be odd because once you make 1 cycle, if the flips are odd, the next cycle every piece will be flipped, but if the sum is even, they will pass every cycle with same orientation.

→ Reply

radoslav11

8 years ago, # |

-10

How to solve Div1 D?

→ Reply

Coder

8 years ago, # ^ |

Similar to counting number of different subsequences

Here you need subsequences with distinct adjacent symbols and for each k you should count how many such subsequence you can have with length k

→ Reply

radoslav11

8 years ago, # ^ |

Well I got that we can transform the problem to counting different subsequences, but I do not understand why do we need to find this number for every length. Can you explain in a bit more details.

→ Reply

I_Love_Tina

8 years ago, # |

← Rev. 2 →

+15

Understanding A-B div 1 took me the whole contest a even now i can't even understand the samples.

→ Reply

geranazavr555

8 years ago, # |

Nice taskset, but could anyone explain how to solve Div2E?

→ Reply

Dey

8 years ago, # |

Can anyone explain, how to solve Div2_C?

→ Reply

8 years ago, # ^ |

Count the number of cylces in the graph, if the number of cycles > 1, then add that number to the changes.

Furthermore, if the number of 1's in the second array is even, add 1 more to your changes.

→ Reply

WorldWarIV

8 years ago, # ^ |

← Rev. 2 →

How does that works for this test :

2 3 4 7 6 1 6

0 1 0 0 0 0 0

→ Reply

8 years ago, # ^ |

The case would be invalid since array p needs to be a permutation.

→ Reply

WorldWarIV

8 years ago, # ^ |

Holy Shit I didn't saw that fucking permutation thing :(

→ Reply

8 years ago, # ^ |

I feel you lmao, reading is hard sometimes.

→ Reply

SarvagyaAgarwal

8 years ago, # ^ |

didn't see*

→ Reply

8 years ago, # ^ |

Your p_i values don't include 5, so this isn't a valid input.

→ Reply

contest_dhuye_pani_khai

8 years ago, # ^ |

I understood the cycle part during contest... however didn't get the part about even number of 1's ... please explain why even number of 1 won't work

→ Reply

8 years ago, # ^ |

If you have an even number of 1's, by the time a skewer gets back to its original position, it will be in the same orientation as it was, however if there are an odd number of 1's, it will get to it's starting position in the reverse orientation.

Idk how good that explanation was, tell me if you need me to come up with an example.

→ Reply

8 years ago, # ^ |

Your explanation is great, but an example would be even more awesome :)

I still have difficulty visualizing how all this permutation stuff works.

Let's give names to 5 skewers: a, b, c, d, e. Rotated skewer a can be named as A. How will this original configuration change with time?

→ Reply

8 years ago, # ^ |

Imagine the skewer that starts at position 1. If p_i makes one big cycle, then after n steps, this skewer will be back where it started. At this point, we would like the skewer to go through all these positions a second time in the opposite orientation. This only happens if it ends up back in position 1 after being flipped an odd number of times.

→ Reply

Smaug

8 years ago, # |

I think understanding problem C was a harder challenge than solving it. (I made barbecue before but u know, it was horrible ...) Also I think preparing sth like A is not good because sb don't know about English calendar so they can't solve it as fast as other people!

→ Reply

Ahmad

8 years ago, # |

Does anyone have any hack cases for Div. 2 A?

→ Reply

RAMBO_tejasv

8 years ago, # ^ |

I used m=2 and d=2 to hack one solution.There was off by one error in his code

→ Reply

Amiri

8 years ago, # ^ |

try these tests:

input:

7 6

correct output:

6

input:

3 6

correct output:

6

input:

1 5

correct output:

5

input:

4 1

correct output:

5

→ Reply

Omar_Morsi

8 years ago, # |

← Rev. 2 →

The problems' statements weren't easy. I can't understand div2 D till now.

→ Reply

Aryan

8 years ago, # ^ |

I agree Div2 E was really hard to understand

→ Reply

redocyz

8 years ago, # ^ |

I still don't understand Div2 E till now. Anyone care to explain?

→ Reply

Omar_Kojak

8 years ago, # ^ |

And Div 2 C

→ Reply

amsen

8 years ago, # |

before 8VC cups. i would like to change my color.(to yellow(i was too close)).

8VC cups changed my color, but to blue :/.

why !?! ;_;.

→ Reply

deepsterescu

8 years ago, # |

After I clicked on someone's solution on the Hacking panel, the solution turned red/ green. What does that mean? I couldn't find that in any FAQs.

→ Reply

riadwaw

8 years ago, # ^ |

+21

red is solution that you read last.
green are all other solutions you read.

→ Reply

kingofnumbers

8 years ago, # |

+89

A moment of silence for those very few people who failed the system test :D

→ Reply

8 years ago, # ^ |

really sad when we use correct logic but just a silly = sign ruins it all up :|

→ Reply

8 years ago, # |

+12

I had trouble understanding the problem statements (especially Div2 D), but the questions were really fun! Really happy about finding the DP solution for D.

→ Reply

8 years ago, # ^ |

do you mind sharing your approach for D? (div 2)

→ Reply

8 years ago, # ^ |

Sure!

First of all, imagine that the time ranges on the tickets work backwards (ie: buying a 90 minute ticket at time 100 covers all trips from times 11 to 100). Then, for trip t_i, we would like to calculate the minimum cost c_i. There are three options:

Buy a ticket for one trip. This costs c_i - 1 + 20.
Buy a ticket for 90 minutes. Use a binary search to find the earliest trip t_m that would be covered by this ticket. This costs c_m + 50.
Buy a ticket for 1440 minutes. Again, find the earliest trip that happened in the past 1440 minutes. This costs c_m + 120.

Total time is $\text{[math]}$ because of the binary search at each step.

→ Reply

savinovalex

8 years ago, # ^ |

Another way is to do exactly what statement says.

	vi a(n);

	for (int & t : a) cin >> t;
	vi his(n, 0);

	his[0] = 20;
	cout << 20 << endl;

	for (int i = 1; i < n; ++i) {
		his[i] = 20;

		int paid1 = 0;
		for (int j = i - 1; j >= 0 && a[j] + 90 - 1 >= a[i]; --j) paid1 += his[j];

		if (paid1 + his[i] > 50) {
			his[i] = max(50 - paid1, 0);
		}

		int paid2 = 0;
		for (int j = i - 1; j >= 0 && a[j] + 1440 - 1 >= a[i]; --j) paid2 += his[j];

		if (paid2 + his[i] > 120) {
			his[i] = max(120 - paid2, 0);
		}

		cout << his[i] << endl;
	}

No DP, no binary search. 144kk operations worst case = 500 ms.

→ Reply

8 years ago, # ^ |

Maybe I'm misunderstanding your code, but this looks like DP to me — you're using the previous outputs (his[j]) to calculate the latest output (his[i]). Nice that there's no need for a binary search, though.

→ Reply

8 years ago, # ^ |

thanks both of you, I understood the question now. I was trying greedy so couldn't get sample case 2 correct.

→ Reply

savinovalex

8 years ago, # ^ |

Well formally this is DP. But, come on, sum[i - 1] - sum[j] would be real DP :)

→ Reply

yassin_

8 years ago, # ^ |

That is definitely DP, and instead of binary search, you just do linear search, so wouldn't work for slightly tighter constraints :)

→ Reply

8 years ago, # ^ |

Now it will send you into space :)

→ Reply

Radewoosh

8 years ago, # |

+86

Nice time limit in E.

→ Reply

8 years ago, # ^ |

My solution works about 350 ms. Have you ever heard about numbers in base 10⁹?

→ Reply

Radewoosh

8 years ago, # ^ |

-7

Once or twice. Look at times of AC's, they're kinda close to limit. But I know, that it's fair, one limit for everyone and things like this...

→ Reply

Errichto

8 years ago, # ^ |

+15

TL of 1s is fine if the intended solution is 350s but bigger difference would be better (why not?), unless there exists a solution in slightly worse complexity that you wanted to fail. Also, I would say that the ratio TL/intendedSolutionTime should be bigger in problems with small time limit, because simple things take more percent of time there (e.g. reading or iterating over 1e6 values). Though, now I think that I don't consider such things/aspects myself when I'm choosing TL :D

→ Reply

8 years ago, # ^ |

-10

Don't get your point. Suppose that reading takes time X. So we are probably interested in ratio $\text{[math]}$ (because X is independent of solution). $\text{[math]}$ . The lesser TL is, the greater $\text{[math]}$ will be.

Also, I've consciously chosen TL to fail solutions like Radewoosh's one.

→ Reply

Errichto

8 years ago, # ^ |

Your calculations are correct but I meant something else. You may assume that reading is constant but sometimes there are many ways to do something simple — so simple that participants don't care about it. For example, pushing numbers from the input to a vector (it's slower that writing to an already allocated array/vector) or using set instead of vector & sort & unique to count different values. So I meant a non-constant X that matters more for small TL. Also, I would expect bigger language differences for times close to 0 — I wouldn't set TL 0.1 if the intended solution is 0.03.

Also, I've consciously chosen TL to fail solutions like Radewoosh's one.

Ok, it explains an unusually small TL. I don't think choosing a good base for calculations was important in this problem but I won't argue about that (your decision was fine IMO).

→ Reply

8 years ago, # ^ |

1 second isn't an unusually small TL for me.

→ Reply

8 years ago, # ^ |

+33

Codeforces exceeded time limit when going through all the zeroes in hardcoded constants in your code.

→ Reply

Yury_Bandarchuk

8 years ago, # |

+37

Upsolving!!!

→ Reply

har_vi

8 years ago, # ^ |

waiting for problems to added in practise.

→ Reply

8 years ago, # |

+11

Is there a time limit after which you can see other's solutions ?

→ Reply

appro

8 years ago, # |

Can anyone suggest how to solve Div2 B?

→ Reply

8 years ago, # ^ |

binary search the answer. allocate the answer to k. allocate k-1 to adjacent guys etc etc.. if not able allocate, search for lesser answer.

→ Reply

Aryan

8 years ago, # ^ |

try to use BinarySearch :)

→ Reply

NotProo

8 years ago, # |

Will these problems be added to archive, and when?

→ Reply

contest_dhuye_pani_khai

8 years ago, # |

So I was trying to access the problem for practice and suddenly this happened. Some kind of bug or hidden feature? o.O

→ Reply

HueMaster

8 years ago, # ^ |

+14

This happend with me too, wtf

→ Reply

contest_dhuye_pani_khai

8 years ago, # ^ |

You went to my account? o.O

→ Reply

8 years ago, # |

Div-2 D is written so badly . I am still not able to understand it. Can any one help?

→ Reply

8 years ago, # ^ |

discussed here! already

→ Reply

8 years ago, # ^ |

← Rev. 2 →

The analogy of trip was badly written I believe. The trips are instantaneous are point in time so to say. So if trips happen at 1 30 50 minutes. its better to take a 90 minute ticket/pass than 3 individual tickets.

so I was doing.. min( dp(i-1)+20, dp(last trip 90min ago) + 50, dp(last trip 1440 ago + 120) ) etc.. Finished coding 5 mins after contest end :(

→ Reply

8 years ago, # ^ |

Yeah, I thought this was a little misleading.

I understood the question as:

You only pay for a bus ticket when you board a bus, and the length of the trips don't matter
The t_i values are the times when you board a bus
The 90 minute ticket lets you pay once and board an unlimited number of buses for 90 minutes

→ Reply

8 years ago, # ^ |

If only the problem could say these words, I would have been better rated today :P

→ Reply

Fekete

8 years ago, # |

+68

Waiting for rating update...

→ Reply

emoji

8 years ago, # ^ |

Only few people have their ratings updated till now like tourist. Does the process of updating take too much time??

→ Reply

dush1729

8 years ago, # ^ |

← Rev. 2 →

Rating of Final Round participants is updated, not other two.

→ Reply

emoji

8 years ago, # ^ |

i think there is a problem with the site right now.i see the updated rating of tourist when i open a profile and the previous rating when i open the contest section on profile.

→ Reply

8 years ago, # ^ |

+11

They are looking for cheaters before computing rating. There are definitely no cheaters on the onsite event, so they have immediately calculated rating for them.

→ Reply

RockyB

8 years ago, # |

When will be editorial?

→ Reply

Martial

8 years ago, # ^ |

← Rev. 2 →

The editorial is here.

→ Reply

dantrag

8 years ago, # |

← Rev. 2 →

+111

Thank you, C++, for being so tolerant to typos...

if (sums[left >= time]) -- passed pretests(!), WA 21
if (sums[left] >= time) -- AC

→ Reply

_VanGogh_

8 years ago, # |

Why the hell codeforces hides comments with too many negative votes? They are more interesting for me :D

→ Reply

hacker_de_sentimente

8 years ago, # ^ |

Exactly like the problems, the interesting ones are harder to get.

→ Reply

8 years ago, # |

+17

Congratulations to winners!

The onsite participants only standings page is available by the link http://codeforces.me/contest/756/standings?list=2c7ac9b338b4906db6d101641a3b06b4.

→ Reply

Petruchcho

8 years ago, # |

+15

Codeforces rating system is kinda odd. If I had participated in div 1 round I would got a good increment (like +50), but with final round I get only +4. If there is no mistakes then the only conclusion I can make is not to participate in small-amount-of-participants rounds in future.

→ Reply