Invitation to SnackDown 2017 Elimination Round & its Replay!

8 years ago, # |

+17

How many problems will there be?

→ Reply

kingofnumbers

8 years ago, # ^ |

+26

The admin preferred not to reveal number of problems.

additional information:

1- the contest will have ACM rules.

2- multiple machines for one team is allowed.

→ Reply

8 years ago, # ^ |

+11

Thank you for information. I suppose, there will be about 9-13 problems (because of duration in 5h, ACM ICPC rules and permition to multiple computers).

→ Reply

8 years ago, # |

← Rev. 2 →

-32

n = 1 case in Add or Multiply problem... I got 10 WA for that!

I solved 2 problems, what do you think, is this good for my color?

→ Reply

Chenghiz

8 years ago, # ^ |

+15

I think thats pretty good, congrats mate. :)

→ Reply

8 years ago, # ^ |

Thanks :)

Just curiously, did you participated, if yes, how many problems you solved? :)

→ Reply

Chenghiz

8 years ago, # ^ |

+36

My team did 5.

→ Reply

8 years ago, # ^ |

Wow, that's really good!

→ Reply

8 years ago, # |

+52

Just curious, were tourist and qwerty787788 participating both or just one of them? or maybe participating while driving? (just curious) :D

→ Reply

gultai4ukr

8 years ago, # ^ |

+13

Both. You can see solutions in Java and C++ for different problems.

→ Reply

8 years ago, # ^ |

+19

seems they were driving or using ipad

→ Reply

Ashishgup

8 years ago, # ^ |

What makes you say that?

→ Reply

sup_bro

8 years ago, # ^ |

+21

tourist and qwerty787788 didn't come first. Thats strange :D

→ Reply

gultai4ukr

8 years ago, # ^ |

+14

I'd not to say so because of many very strong teams, which participated here. Not that mess_compress was weaker than somebody, but it's really hard to win with so strong rivals.

→ Reply

motherofgod88

8 years ago, # ^ |

+10

people said the same before WF 2015 and WF 2013. but they won easily. so it is strange when they dont win.

→ Reply

gultai4ukr

8 years ago, # ^ |

If wasting of 20-30 hours per week for training/upsolving == easily, then yes, they win easily.

And, FYI, there was much more strong teams comparatively with any WF because there was no age (or any other) restrictions.

Finally, these guys (as any other top team) shouldn't play on the full strength, because final round don't require top places.

→ Reply

kalimm

8 years ago, # |

← Rev. 2 →

+14

Replay round in tomorrow, so we can't discuss and no editorials, right?

EDIT: We can look at submissions anyway

→ Reply

8 years ago, # ^ |

+13

But we can see solutions of other people...

→ Reply

8 years ago, # ^ |

You can discuss the problems now. The editorials will be provided after the reply round.

→ Reply

torquecode

8 years ago, # |

+29

How to solve ANCESTOR ?

→ Reply

Morphy

8 years ago, # ^ |

+11

Hints:

Calculate the eulerian tours of both trees
Now the problem is like finding intersections of prefixes

→ Reply

I_Love_Equinox

8 years ago, # ^ |

+46

It's like a euler tour on trees technique. First, So we keep starting and ending time of each node in the first tree. Now, when we are doing dfs on the second tree, so while visiting a particular node say x, we will add 1 to all the nodes who are in the subtree of x in the first tree, i.e add 1 to all the nodes whose starting time > start[x] and ending time ≤ end[x] [Remember start[x] and end[x] are for the x in the dfs of first tree]. We can do this with BIT, and when we're done with dfs of x in second tree, we will reverse the operations i.e. add - 1 to the above stated nodes for x. So, answer for a particular node i will value of 1's added to start[i].

→ Reply

8 years ago, # ^ |

+20

I have a little different approache for the task. We can calculate eulerian tours for both trees, than we will have four different times for each node : (start1, end1), (start2 , end2) — coming and leaving times for both trees. Now let's represent each node as point in the plane with coordinates x=start1 and y = start2. We have n points in total. Also we can represent recetangle with left-bottom point (start1, start2) and right-up point (end1,end2) for all nodes x. All points (nodes) in the recetangle will have x as ancestor in both trees.

Now we need to do inverse task — calcualte amount of recentagles which contains certain point and this is known problem.

→ Reply

Lewin

8 years ago, # |

+203

It looks like this problem: https://www.codechef.com/SNCKEL17/problems/SPCLN is almost an exact copy of this problem: https://www.codechef.com/problems/RIN

→ Reply

pk.

8 years ago, # ^ |

-25

How do we get such information man? Did you solve the question previously? Just Curious.

→ Reply

apoorv024

8 years ago, # ^ |

+36

Yes, it is the exact same question.

The editorial for problem RIN at this link : http://discuss.codechef.com/problems/RIN

has the same test case which is provided as the sample test case in https://www.codechef.com/SNCKEL17/problems/SPCLN.

→ Reply

Kostroma

8 years ago, # ^ |

← Rev. 5 →

+243

Any comments from admins? For me it seems the author of yersterday's problem simply copied it from cgy4ever's problem. And it may have ruined the selection of onsite teams.

UPD Now having noticed the output format "print the average sum rounding to two digits after decimal point" I'm 100% sure that problem copying is the case. Haven't seen such an impudent copying of the problem in official competition before.

→ Reply

8 years ago, # ^ |

+82

Kostroma, Currently we are investigating this possibility. We will soon notify about it.

→ Reply

8 years ago, # ^ |

+49

We have confirmed that the author has deliberately copied the problem. Author's code is exactly same as that of one of the submissions in the problem RIN. Also, author's short editorial/explanation contains images that are taken from the editorial and are edited slightly. The author will be banned from Codechef problem setting. We apologize for the situation. Specifically, I feel very sad in failing to find this before the contest.

We will be taking all the submissions of problem RIN and will be applying plagiarism checking program, and after that, we'll declare the final ranking. We are again sorry for such a situation.

→ Reply

Kostroma

8 years ago, # ^ |

+79

We will be taking all the submissions of problem RIN and will be applying plagiarism checking program

So you are going to ban somebody for copy-pasting solution of the original problem, aren't you? Is it fair? Is it along the codechef rules?

→ Reply

EdwardSnowden

8 years ago, # ^ |

+90

They are going to ban some teams for choosing the right strategy.

→ Reply

afaji321

8 years ago, # ^ |

← Rev. 2 →

+61

If I found the problem was plagiarised during the contest, I wouldn't bother wasting time to recode the solution.

Also from this: https://www.quora.com/Can-I-use-others-code-in-a-CodeChef-contest it seems fine to copy others code, as long as the code was online before the contest

→ Reply

8 years ago, # ^ |

-103

No, we are not going to penalize for copy pasting if the code is authored by you and was submitted to this problem earlier, or you have provided the reference link to the solution code.

→ Reply

zeliboba

8 years ago, # ^ |

← Rev. 2 →

+126

Seems that it is very bad way too. If somebody copied code from old codechef contest (even if it is not his code) it is allowed by rules of codechef, because it is open source code.

→ Reply

ItsLastDay

8 years ago, # ^ |

+35

Codechef code of conduct cannot agree with you:

Taking help or using a third party code is not bad. Passing it off as your own is. If you are taking your code from some other source, it is expected that you give the due attribution to the source in your code. It is kind of mandatory.

→ Reply

8 years ago, # ^ |

+28

You're kind of correct.

→ Reply

malcolm

8 years ago, # ^ |

Any updates about the list of finalists? The contest is just in 20-30 days, finalists need to obtain visa, book flights and so on.

→ Reply

8 years ago, # ^ |

+10

We have already contacted the finalists regarding this.

→ Reply

Motarack

8 years ago, # ^ |

← Rev. 2 →

+23

I think it would be better to remove his name as the author of the problem in the problem's page.

→ Reply

nssprogrammer

8 years ago, # ^ |

-688

Hi , so to me seems like a notorious coincidence. Though I have come across a similar technique in a programming article ( it was in Russian ) way back.

→ Reply

Kostroma

8 years ago, # ^ |

← Rev. 2 →

+210

Don't try to fool us. It has become obvious you just copied this problem.

Btw what's the reason? They pay so much money for problems of elimination?

→ Reply

dotorya

8 years ago, # ^ |

+213

OK,so that article was so great, and it could predict which sample test case you would use in this contest! I googled your sample test case appending "codechef", and I found exact same problem, even with same sample test case. Do you think competitors are idiot? I respect problem setters who prepare good problems and great contest, or at least try to do so. Not a thief who just copies someone's problem and pretend to say "It's my problem!". Good job, you ruined the whole problemset, just by copying one problem!

→ Reply

PrinceOfPersia

8 years ago, # ^ |

+85

It couldn't be more obvious :|

→ Reply

ko_osaga

8 years ago, # ^ |

+153

One of most terrible and shameful moment I've ever seen in competitive programming. CodeChef you guys are awesome

→ Reply

kingofnumbers

8 years ago, # ^ |

+38

Kostroma, dotorya, PrinceOfPersia, ko_osaga

Guys, this desperate comment didn't even deserve that you bother replying it.

anyway, I expect that there will be an announcement about this issue from the admins soon.

→ Reply

8 years ago, # ^ |

+100

This is not so important to me, even I didn't read problem during the round :D

But that is CodeChef mistake too... I can not believe when someone think that coder with rating 1200 can prepare the hardest task on the team div 1 round ! At least you should have tried to google it !

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+66

Yeah told kingofnumbers the same before the start of the round. But he told me that optimistic stuff of that the color is not related to the knowledge and skills, and there are people who are theoretically perfect and it's not proper to accuse him in that way.

→ Reply

Um_nik

8 years ago, # ^ |

+33

He could have came across this problem on his job or in his research work.

→ Reply

8 years ago, # ^ |

-7

Is it original problem then ?

And second thing I didn't say it is impossible at all, I said than you need to check three times before you use the problem.

→ Reply

PrinceOfPersia

8 years ago, # ^ |

+10

You don't need to be a bug to write a hard problems. Anyone can write a HLD problem by thinking about HLD (for example).
Don't judge people by their color. Maybe he just doesn't take them seriously. I know some badasses with low ratings.

→ Reply

8 years ago, # ^ |

I believe creating an original maxflow problem is just on another much higher level than writing an HLD problem.

In any case, just guys who does that in the same rude way must take the consequences.

→ Reply

8 years ago, # ^ |

+13

I already had discussion about judging people by their color. And I will tell agian, I do not have any bad opinion about such coders. I can not say I am not very good programmer too and I hope they will be better than me now !

But if someone has low rating, several bad contests and suggesting you the hardest task on the round, you need to check that thing at least 3 times.

→ Reply

Knight_of_Thirteen

8 years ago, # ^ |

← Rev. 2 →

+104

nssprogrammer I am not a very good coder myself but I must say this, how did you post such a comment after getting caught? I mean, the problem needs good understanding of Min Cut Max Flow, and also, the tag of the original problem is hard! If you are that awesome, that you just recreated a problem exactly in the same way, even generated the exact same test cases, just by "having come across a RUSSIAN article WAY BACK", then I must ask, how come you are still Pupil??? A notorious coincidence, ehh???

→ Reply

cmd

8 years ago, # ^ |

+110

Btw, was confused during the contest with average energy in SPCLN (why not just the total energy), but turns out that in terms of the original problem (RIN) it actually makes much more sense to have the average as an output =)

→ Reply

pk.

8 years ago, # |

Approach for Waiting in Queue, anyone?

→ Reply

fnf47

8 years ago, # ^ |

+43

Submit on Codeforces

→ Reply

geniucos

8 years ago, # ^ |

← Rev. 3 →

+28

Where on codeforces? We've finished our source shortly after the end of the competition (well, not so shortly, maybe 25 minutes) and I'm curious whether it passes or not. However, I don't understand why there were so few AC sources. Our idea involved just a treap and some tricky information stored in it (it wasn't trivial), but still, there were much harder problems (from the point of view of their ideas) solved by more teams. Anyway, the problems were interesting and most of them were really nice. About the problem lewin has pointed out I'm not that happy, but apart from that, the contest was a complete success. Congrats!

→ Reply

cdkrot

8 years ago, # ^ |

In my opinion it was more like implementation problem for people familiar with treap and can do lazy propagation.

Store in treap not b_i, but b_i - i. What job will be completed first? The job with lowest index, such that b_i - i ≤ 0.

If you store in each node minimum of subtree, you can determine such node by recursively going down (recursive function: if there is a possibility to go left and minimum in left is small enough, then go there; otherwise try middle element; if still not go right)

What to do when you found such node? Delete it, add some const to all elements before this node (so that it matches definition b_i - i, add some const to all elements after this node, and rotate the array cyclically.

One more case. If the whole array is greater zero, then you should advance time by few whole rotations. Thing like the minimum divided by size of treap and ceiled up will do the trick.

→ Reply

geniucos

8 years ago, # ^ |

← Rev. 2 →

That's exactly what we did. I think it was the only solution. However, we didn't need any sort of lazy propagation. Just storing minimum of bi — i for a subtree in the treap was enough. It's just that we considered what problems to think about next by looking which one was solved by more people and we let this one at the very end of the competition. When we read it, the solution was obvious but we didn't have time to solve it. I guess that could be a good lesson: not to judge a problem after the numbers of accepted solutions

→ Reply

Kaban-5

8 years ago, # ^ |

+29

Suppose at time moment t the queue contains people with arrival times b₀, b₁, ... b_n - 1. If b₀ ≤ t then first customer in queue will be served now, otherwise if b₁ ≤ t + 1 then first customer will be moved to the end of queue and second will be served now, ..., if b_n - 1 ≤ t + n - 1 and b_i > t + i for all 0 ≤ i ≤ n - 2, then n-th person will be served now and all others will be moved to the end of queue, preserving their order.

If b_i > t + i for all 0 ≤ i ≤ n - 1, then in seconds from t to t + n - 1 inclusive everybody gets moved to the end of queue and situation just repeats at moment t + n.

So, what happens with queue? If $\text{[math]}$ , then everything comes full circle and t is increased by n. Otherwise, we need to find the leftmost position j, such that b_j - j ≤ t, process customer at that position and move everybody before that position to the end of queue (preserving order).

How many full circles will happen (let's call this number k)? If $\text{[math]}$ (if M ≤ t then k = 0), then exactly $\text{[math]}$ full circles will happen. To simulate them, just increase t appropriately.

Now only the case when M ≤ t bothers us and we want to find smallest j such that b_j - j ≤ t quickly. To do this, let's keep queue in implicit treap and in each vertex remember minimum value of b_i - i in its subtree. Idea of remembering something that changes when we do operations on tree sounds kind of dangerous, but actually it is completely ok in this case. When we do merge and split we just need to do an update operation to some vertex (where info is no longer correct, but info for it children is up to date), we need to just decrease minimum in right subtree by 1 + (size of left subtree) and b_i - i for root is just b - (size of left subtree). So this kind of information can be keeped while we do basic merge and split by length operations.

To find smallest j that b_j - j ≤ t, just do tree descend and check whether minimum of b_i - i in subtree is still less than t. After that serve this customer, delete him and move all customers that stand before to the right (by splitting them out from the left and merging them on the right).

→ Reply

rng_58

8 years ago, # ^ |

+33

Do we really need treap?

When we delete a node x, we should add one to the values of b_y - y for all y > x, and set b_x - x to infinity. Can't we do this with a segment tree?

→ Reply

yarrr

8 years ago, # ^ |

← Rev. 3 →

How can you find "first good" node, if order changes after each deletion?

UPD: Oh, I see. If you already have previous element, you already know where new queue begins. So you can just find "first good one" at suffix after previous element first and on prefix after.

→ Reply

TooDumbToWin

8 years ago, # |

+11

I'd be glad if someone could help me hack this code. here

I've first checked if all 4 points are collinear, then if 3 points are collinear. (Solution is trivial in these cases)

After that, I've checked if any of the point lies inside triangle formed by other 3 points. In this case, answer should be "NO".

After that, I've solved the problem for points which do not form parallelogram. (Take two points. Say points are a,b. Other points are c and d. Check if there exists any point e, such that c lies on a-e and d lies on b-e or vice versa)

For parallelograms, extend a-b by some margin, and do as mentioned in case of non-parallelograms.

→ Reply

Nuruhuhuhu

8 years ago, # |

Are Bangladeshi contestants allowed to have t-shirts if their rank is below 301?

→ Reply

darth_coder

8 years ago, # ^ |

https://www.codechef.com/snackdown/2017/prizes Any team within Top 300 will get it

→ Reply

Nuruhuhuhu

8 years ago, # ^ |

Yes, I know. I asked the question because recently HackerRank has declared that they will not give any prize like t-shirts to Bangladeshi contestants even if they are eligible for it. I was thinking if Codechef did the same :( I don't know why HackerRank did so.

→ Reply

arun_prasad

8 years ago, # |

+11

How to solve the first problem ? PLUSMUL?

→ Reply

hrushikesht

8 years ago, # ^ |

← Rev. 3 →

Hints:

Calculate for each element how many times it will contribute in the final answer.
Try to find some kind of reccurance relation which will help in calculating the contribution of each element using the contribution of the next element.

→ Reply

darth_coder

8 years ago, # ^ |

← Rev. 2 →

https://www.codechef.com/snackdown/2017/prizes Any team within Top 300 will get it

→ Reply

ista2000

8 years ago, # ^ |

You replied to the wrong comment bro ;_; I guess you were tryna help out Nuruhuhuhu

→ Reply

darth_coder

8 years ago, # ^ |

Thanks to mention. I couldn't delete the comment . but I copied the comment above. I guess I was sleepy then. :D

→ Reply

8 years ago, # ^ |

← Rev. 2 →

sum[i] = sum[i-1] + dp[i];
dp[i] = ( dp[i-1]-sum[i-2] ) * ar[i] + sum[i-2] + dp[i-1] + ar[i] * pow(2, i-1);
ans = dp[n-1];

complexity : O(n).

→ Reply

adamantium

8 years ago, # ^ |

← Rev. 2 →

Can anyone please explain this recurrence relation ?

→ Reply

8 years ago, # ^ |

+10

dp[i] stores the sum of results of all possible expressions using elements from ar[0] to ar[i].
For next element( ar[i] ) we have to add and multiply it to all our previous expressions.
There are total 2^(i-1) different expression exist at position i-1.
Addition can be done by ( dp[i-1] + ar[i] * pow(2, i-1) ).
For multiplication subtract prefix sum of dp until position i-2 and then add this term after multiplication ( ( dp[i-1]-sum[i-2] ) * ar[i] + sum[i-2] ). By observation.

→ Reply

Tima

8 years ago, # |

+10

How to solve ROBOTDAG?

→ Reply

300iq

8 years ago, # ^ |

+10

Binary search + max flow inside it

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+24

The constraints for this problem are tricky somehow. Especially when you first think of Max Flow. Create n versions of each node. Each node will have an extra copy for every time second. and for each edge u->v add it for all nodes [u][s] -> [v][s+1] where s is a second ranging from 1 to n. I think most people got AC with binary search, but you can throw throw out binary search and add edges to the sink representing each second while going on and after adding each layer call your augmenting path function. I think this runs in K * N * M. But in particular it's kind of impossible to force maxflow algorithms to reach worstcase.

→ Reply

kpw29

8 years ago, # ^ |

You can easily improve your solution to O(N*N*M),what leads to much better runtimes than with KNM. This probably explains why additional binsearch doesn't hurt.

→ Reply

shb123

8 years ago, # ^ |

Can we use Dinic algorithm directly on the graph with N*N nodes? I think it will take the shortest path each time but I got a WA :( Is that correct?

→ Reply

tfg

8 years ago, # ^ |

+10

The shortest path in reality might be a longer augmenting (is that the right word?) path because it might need to use backwards edges to complete it when there's a "faster" path just going forwards.

→ Reply

I_Love_Equinox

8 years ago, # ^ |

+20

We can create a new graph where each node (i, j) represents that we are on node i at time j. Now when we are creating edges , we should create edges from a nodes (u, t) to (v, t + 1) if (u, v) edge exists in our original graph. So, our initial problem is transformed into finding the edge disjoints paths in our new graph which is a standard problem. Now we can binary search on minimized maximum length by creating a graph in which the nodes are stated as above and t is the length we want to check. To check for a particular length, we'll need to check if the total disjoint paths in our new graph ≥ k and change the limits of binary search accordingly.

→ Reply

8 years ago, # ^ |

Actually i didnt understand this ""To check for a particular length, we'll need to check if the total disjoint paths in our new graph ≥ k and change the limits of binary search accordingly.""

To be specific what is the variable we binary search on ?? And do we create new graph or modify it in any way each time we do new binary search iteration ??

→ Reply

tfg

8 years ago, # ^ |

Yes. You create a new graph for each binary search iteration and the variable is the number of layers (time) used on the graph.

→ Reply

8 years ago, # ^ |

ok thanks !!

→ Reply

ilyakor

8 years ago, # |

+52

Prefix XOR: in the problem statement, we're asked to answer queries online rather than offline. But why? The solution is absolutely the same as for the offline version (precompute longest sequence for each position, then answer queries using a segment tree), except that one has to use persistent segment tree instead of segment tree. Is it a test for knowledge of "modern" data structures/googling skills/prewritten code?

→ Reply

halin.george

8 years ago, # ^ |

-10

There is no need in persistent segment tree. We need to store vector in each vertex of segment tree and do binary search.

→ Reply

ilyakor

8 years ago, # ^ |

Wouldn't this be asymptotically worse? I.e. you do log n binary searches on each query.

→ Reply

8 years ago, # ^ |

→ Reply

grahhhpor

8 years ago, # ^ |

+10

Pretty bad meme tbh fam.

→ Reply

8 years ago, # ^ |

+60

sorry i had nice ideas but image editing skills are r3kt

→ Reply

tttayushag10004

8 years ago, # ^ |

-8

I was trying to do the same using merge sort tree but giving tle even with fast input/output. Solution Link: https://www.codechef.com/viewsolution/14081153

Any suggestions for this??

→ Reply

vintage_Vlad_Makeev

8 years ago, # ^ |

← Rev. 2 →

+18

You are building mergesort tree in $\text{[math]}$ time. Probably, good optimization is to build this tree in $\text{[math]}$ time. It can be built with following pseudocode:

build(v, l, r):
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    tree[v] = merge(tree[2 * v], tree[2 * v + 1]);

Where merge function has linear complexity.

→ Reply

tttayushag10004

8 years ago, # ^ |

← Rev. 3 →

-21

→ Reply

tttayushag10004

8 years ago, # ^ |

-21

any reason for downvotes??

→ Reply

8 years ago, # |

Where can i find tests for the problems?

→ Reply

SarvagyaAgarwal

8 years ago, # ^ |

I dont think you can view the tests on codechef.

→ Reply

8 years ago, # ^ |

Do you know something about upsolving?

→ Reply

SarvagyaAgarwal

8 years ago, # ^ |

Yes , are you saying that the test cases are visible in practice problems ?

→ Reply

8 years ago, # ^ |

I don't know) But it is great opportunity to finish my work with the problems)

→ Reply

gXa

8 years ago, # |

← Rev. 2 →

Can Chef and Pairs be solved using ternary search( finding x using ternary search )?

I know we need strictly increasing and later decreasing, but still is there any way to find extrema in function which may not be strictly increasing and then decreasing, but just increasing and then decreasing.

→ Reply

Nuruhuhuhu

8 years ago, # ^ |

+55

no you dumb fuc

→ Reply

kpw29

8 years ago, # |

-10

I really enjoyed problem about black subgraphs. A really cool one. Still, I don't understand why so many teams solved it. It was two leagues harder than the damn "copy paste persistent tree" problem.

→ Reply

Radewoosh

8 years ago, # ^ |

+23

Which problem in your opinion was about "copy paste persistent tree"?

→ Reply

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=726&pid=1004

8 years ago, # ^ |

-9

Just out of curiosity, how often do nontrivial data structures come up in ICPC WF? Can someone give me a rough estimate of the number of (nontrivial) segment tree / treap / other ds problems that have come in WF in the last 9-10 years?

→ Reply

kpw29

8 years ago, # ^ |

The xor one.

→ Reply

Radewoosh

8 years ago, # ^ |

+18

In my opinion, hardest thing was to find for each beginning how long intervals would be good, if you'd start from here. When you already have those n numbers, then yes, you must use persistent tree, but implementing it is standard skill, that most contestants should have. Also I think that problemsetters wanted online algorithm, because D&C approach would kinda break this problem and make it much easier.

→ Reply

dreamoon_love_AA

8 years ago, # ^ |

+21

I believe there are many online judges have the totally same problem.

→ Reply

akulsareen

8 years ago, # ^ |

What was the solution to the black subgraph problem? The fastest solution I could think of involved iterating to the correct subtree size and taking 2-dimensional fft's or something along those lines.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

The solution was an O(n^2) dp. The main observation is as follows. For a subgraph of size s, find the min and the max number of black vertices it can have. Then, answer for all b's from the min to max will be yes, and no otherwise.

Finding min_b[s] and max_b[s] can be done using tree dp of time complexity O(n^2).

→ Reply

riadwaw

8 years ago, # ^ |

← Rev. 2 →

Would you share a proof of the claim, please?

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+18

riadwaw, The important observation is that you can transition from any s sized subgraph to another s sized subgraph by adding a vertex and deleting a vertex, and it will change the number of black nodes by at most 1. So, the set of valid b's for a fix s will be containing consecutive elements in the range min_b[s] to max_b[s].

→ Reply

riadwaw

8 years ago, # ^ |

← Rev. 2 →

+10

Thanks, right. I did the same observation for fixed number of blacks, but for some reason couldn't apply the same idea here

→ Reply

Um_nik

8 years ago, # ^ |

+65

You are talking about probably the easiest problem from this contest, right? I read this problem and 'wait, I spend 40 minutes on geometry while there was obvious DP?!' Still don't understand why so few teams solved it.

Just kidding :) Different people prefer different kinds of problems.

→ Reply

Leonid

8 years ago, # |

← Rev. 3 →

What were the tricks with the "4 points" problem?

We considered the following and ran on randomly generated tests, but still WA.

4 collinear points — choose the furthest points pairwise to form a triangle, and any other given point in the triangle. 3 collinear points — the furthest two points out of 3 forming a triangle, and the fourth point. 4 points forming rectangle (answer is NO). One point inside a tiangle formed by the other 3 points (answer is NO).

Bruteforce permutations of 4 points. Calculate intersection point between 2 lines formed by these points. Choose 2 points in each segment for the triangle and the intersection. Check if the specified conditions were met — namely (a) all points are on the triangle sides; (b) intersection coordinates are within the bounds.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

-23

4 points forming rectangle (answer is NO)

it is not correct answer is "YES" in that case.

→ Reply

Radewoosh

8 years ago, # ^ |

+25

There is answer for a rectangle... and it's kinda easy. The only case without answer is when one point is inside triangle made of 3 other. I had such cases: 3 (or more) collinear points, points forming a parallelogram, other cases. It's easy to consider every of them separately, hardest thing was about "find intersection of two lines".

→ Reply

8 years ago, # ^ |

I will send this message to my teammate, who couldn't get AC for last 2 hours :D

→ Reply

ksun48

8 years ago, # ^ |

+33

Here is another solution for the noncollinear case. We need to check if the points in the convex.

Then, assuming ABCD is a convex quadrilateral we can draw the line through C parallel to BD, and intersect it with AB and AD to get E, F. Then AEF is our desired triangle.

→ Reply

8 years ago, # ^ |

+15

I tried to minimize the number of cases, so here's what I did :

If three of the points are collinear, sort them by increasing order of x-coordinate, then y-coordinate. Let's say the points are P₀, P₁, P₂ in this order. Now, we just take P₀P₃P₂ as our triangle.

Otherwise, build the convex hull of the four points. If the size is at most 3, the answer is NO. Otherwise, we have the points A, B, C, D as the vertices of a convex quadrilateral, in this order. In this case, take the lines AB, AD and the line parallel to BD passing through C as the sides of our triangle. The vertices are just the three intersection points of these lines.

→ Reply

arun_prasad

8 years ago, # |

Can someone please tell me the recurrence relation required to solve the first problem PLUSMUL

→ Reply

8 years ago, # ^ |

Here

→ Reply

abcdef6199

8 years ago, # |

In problem BLACKCOM, how to do that DP ? I have no idea how to do it in O(N^2).

→ Reply

xuanquang1999

8 years ago, # ^ |

← Rev. 2 →

+23

A similar problem to this is problem "Barricades" from Algorithmic Engagement 2007. You can find a solution in the first half of the "Looking for a challenge" book (which you can download here). The book explained why the DP is amortized from O(n³) to O(n²) (which is the same case for this problem).

→ Reply

kyuridenamida

8 years ago, # ^ |

← Rev. 2 →

I guess the estimation of time complexity for your DP is not strict.

Let T(x) be the time complexity of a DP with x nodes. If you write a DP whose time complexity is like T(L+R) = T(L) + T(R) + L*R (Somehow you can convert the tree where some vertex could have three or more children into as a equivalent binary tree), the time complexity is O(N^2) in total (N is the number of nodes) as xuanquang1999 said.

Why? Let's assume T(x) <= x^2, then T(L+R) = T(L) + T(R) + L*R ≦ (L+R)^2 = L^2 + R^2 + 2*L*R. You can find this is obviously true by comparing each term in the left side and the right side.

This fact is a little amazing. I can't understand it intuitively actually.

→ Reply

mnbvmar

8 years ago, # ^ |

+38

Let's introduce the potential function as the number of pairs of vertices in the same connected subtree. At first, the number is equal to 0 (all vertices are in distinct subtrees). In the end, the number is equal to $\text{[math]}$ .

If you connect two trees of size L and R, respectively, you increase the potential by LR, which is proportional to the time of merging the trees. Thus, the total runtime is proportional to $\text{[math]}$ .

→ Reply

I_love_Hoang_Yen

8 years ago, # ^ |

← Rev. 2 →

Straight-forward DP has complexity N^2. You can read cheater2k's very simple explanation here in Vietnamese.

→ Reply

bhishma

8 years ago, # |

How to solve Chef and Pairs.

My approach was that as we are moving the points from left to right the maximum matching will increase and then decrease , but there can also be plateaus . Also I am not sure about the above claim . Can someone share their approach .

→ Reply

8 years ago, # ^ |

That property of increasing and then decreasing doesnt hold !!

→ Reply

8 years ago, # ^ |

+13

Sort the arrays a and b.

The problem is equivalent to finding the maximum matching of arrays a and b such that if m, M are the minimum and maximum value of A - B where (A, B) is a pair in the matching, then M - m ≤ 2y.

My idea is since n and m are small, I can brute force all possible (i, j) so that we pair a_i, b_j and m = a_i - b_j. For each such pair, I can find the maximum number of pairs I can still make without violating m ≤ a - b ≤ m + 2y in O(n) time by greedy.

→ Reply

krybom

8 years ago, # |

← Rev. 2 →

-34

My team solved 4 problems and ranked 251. Nice contest

→ Reply

8 years ago, # |

How to solve MEXDIV ?

→ Reply

8 years ago, # ^ |

+22

My solution : For each position i, find the leftmost position l such that the mex of the subarray [l..i] is at most k. Note that the mex is larger than k iff all numbers from 0 to k inclusive has appeared in this subarray. Note that if [l..i] has mex larger than k, then [l..i+1] must also have mex larger than k, so the sequence of leftmost position is non-decreasing. We can compute this leftmost position for each i with the help of two pointers. Call the leftmost position for position i as L[i].

Once we build the array L, we just have to do a simple dp. dp[i] is the number of ways to divide the first i elements into subarrays satisfying the condition. dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[L[i] - 1], and the latter can be computed in O(1) time if we maintain the prefix sum for dp[i].

Complexity : O(n).

→ Reply

prak_blah

8 years ago, # ^ |

can you please share your code?

→ Reply

8 years ago, # ^ |

Code

→ Reply

amsen

8 years ago, # |

How to submit?

→ Reply

8 years ago, # ^ |

Currently replay round of the contest is taking place ! You can submit there ! Or else after this contest all the problems will be added to practise section. For a problem from contest just remove the contest code from URL to go to practise version of that problem

eg https://www.codechef.com/SNEL17RP/problems/CHEFPRAD -- contest

https://www.codechef.com/problems/CHEFPRAD -- practise

→ Reply

dush1729

8 years ago, # |

+46

Top 3 teams will win cool SnackDown t-shirts.

You are kidding, right? Solutions were made public after contest.

→ Reply

chanukya_p

8 years ago, # ^ |

← Rev. 2 →

+13

Hi, We noticed that we have missed making the solutions of the elimination round private. Now we are already half way through the contest and the damage is done. Keeping into consideration of the series of events and the spirit of the competition, we are calling back the prizes (of the replay round) that were announced earlier. We shall be more diligent in our future events and we sincerely apologize for the inconvenience caused. Thank you for bearing with us.

→ Reply

downvoteplz

8 years ago, # |

+43

Regarding problem CHEFPRAD

I am not sure why no one mentioned this issue yet, but the "expected" solution is O(N * M * (N + M)) per test case. Given there are 10 test cases, this amounts to 3·10⁸ ops, which seemed pretty marginal for 1 second TL to me(given CC servers performance).

I was pretty surprised when my solution with that complexity passed in 0.11 secs(clearly CC servers must be fast and I wasted 1 hour trying to optimise my solution for no reason), but I made some random large test data and it was quite easy to get my solution to get TLE on codechef ide and ideone.com(which is also on sphere engine).

Here is rng_58's team's submission which takes 1.74 secs to run on the test, and team rhaegal's submission which takes 3.36 seconds(!)

I do not blame the contestants for writing slow solutions, but my question is why, if this was expected solution, are the test cases so weak(and TL so tight), and in case it wasn't the expected solution, why do these pass?

→ Reply

SarvagyaAgarwal

8 years ago, # ^ |

We had the same issue , our solution got TLE and we wasted time thinking a better logic. In the end , just changed vectors to arrays(optimized the constant basically) and it passed -.-

→ Reply