COCI Round 7 Season 14/15

10 лет назад, # |

← Rev. 2 →

+75

I guess you like prime numbers, don't you? :P

I mean the rounds that you announce.

Good luck to everyone!

→ Ответить

10 лет назад, # ^ |

It seems so. Good thing it's the last round otherwise there would be 3 more unannounced rounds!

→ Ответить

10 лет назад, # |

← Rev. 2 →

+11

Let's discuss the problems now. What is the idea behind the 5-th task? I used the O(N^2) in case N<=7000. Otherwise, I do this 2^20 times:

1) Take a random L: K<=L<=N

2) Take a random F: F+L-1<=N

3) T=F+L-1

4) Take the average for the interval [F,T] and compare it to the answer...

Update: WTF?! It got full score :D

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

I write it using answers binary search,in O(n*log^2 n) ,but it failed,may be it's may mistake in code not in idea (((

→ Ответить

Xellos

10 лет назад, # ^ |

+13

Binary-search the answer, rewrite $\text{[math]}$ as $\text{[math]}$ and use prefix sums + 2 pointers on A[i] - a to check if a is a possible answer.

→ Ответить

10 лет назад, # ^ |

haha I got in correct solution 28,and he got in random solution 140 WTF -_-

→ Ответить

10 лет назад, # ^ |

There is a justice — I failed A and D :D

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

-15

hate COCI-s system!!! viva CodeForce!

→ Ответить

10 лет назад, # ^ |

+14

I was the author of this problem and I apologize, I tried to make test data to break as many bad solutions as possible but it didn't even occur to me that such random solution would find good answers.

Intended solution was, as Xellos already said, binary search the answer P, subtract P from all elements and check if there exists non-negative sum subsequence of length at least K.

→ Ответить

10 лет назад, # ^ |

+13

Thanks, ikatanic, Xellos and LashaBukhnikashvili for the explanation :)

PS: It didn't even occur to me too that it would pass all tests, I expected only 42 points :D

→ Ответить

keyvankhademi

10 лет назад, # ^ |

sorry but did you announce that your problem is a common problem of binary search? link

→ Ответить

10 лет назад, # ^ |

I haven't tried googling it, it surely isn't standard problem for HONI competitors. HONI is intended for Croatian high school trainings and no one got full score on it. As for COCI (which is open-to-everyone HONI mirror) I thought it would be totally fine (maybe it should have been worth less points) because neither I nor other problem setters have seen this (or similar) problem before.

→ Ответить

kllp

10 лет назад, # ^ |

Also something like convex hull trick and ternary search works.

→ Ответить

kingofnumbers

10 лет назад, # ^ |

Could you explain this solution with details?

→ Ответить

kllp

10 лет назад, # ^ |

← Rev. 2 →

We map every array element to some coordinates like in the following code:

int x = 0;
int y = 0;
vector<pair<int, int> > v;
v.push_back({0, 0});
for(int i = 0; i < n; ++i) {
    ++x;
    y += a[i];
    v.push_back({x, y});
}

Now the average can be seen as the slope between two points. Then we iterate through the vector v and maintain a set of points that form the convex hull of the points that we have visited.

Now consider that we have the (K-1)th (the length of the subsequence must be at least K as stated in the problem) non-visited array element (or the corresponding point). We know that the consecutive subsequence that starts from there must start from some of the already visited array elements (or point). It can be seen that we cannot get the best average (or slope) by selecting some point that does not lay in the convex hull. Therefore we can use ternary search to find the best average (or slope).

It seems that there is also somewhat similar solution but which uses two pointers and therefore is O(n), but I don't know it in details.

EDIT: I hope I'm now a bit easier to undestand...

→ Ответить

kingofnumbers

10 лет назад, # ^ |

+13

Nice solution , thank you!

the tip that I learnt from this is that when ever the problem ask you to maximize a function that contain a fraction consider a convex hull solution.

→ Ответить

xennygrimmato

10 лет назад, # ^ |

What is the convex hull trick?

→ Ответить

kllp

10 лет назад, # ^ |

See these: http://wcipeg.com/wiki/Convex_hull_trick http://codeforces.me/blog/entry/8219

I'm not sure if my solution can be called a convex hull trick, but at least there is some similarity.

→ Ответить

VladaMG98

10 лет назад, # ^ |

Damn, I managed to write 10^6 with 5 zeroes as upper bound of my binary search, damn :P

→ Ответить

rmn

10 лет назад, # |

How to solve C?

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

My idea is to consider all permutations of the rows. I mean:

row1

row2

row3

and then

row1

row3

row2

and so on...

Now, let's build a graph for each permutation. From element in row i and column j there is an edge to (i,j+1) with weight a[i][j+1] and to (i+1,j+1) with weight a[i+1][j+1]. Of course, if there are no such positions we will not put edges.

For each permutation run Dijkstra from (1,1). The answer for the current permutation will be in (3,N). At the end, the answer is the minimum of the answers for each permutation.

Code: http://ideone.com/CMXKqJ

→ Ответить

mark03

10 лет назад, # ^ |

Looking at the official solution the problem setter only usude the first permutation (row 1,2 And 3). You know why?

→ Ответить

10 лет назад, # ^ |

I have absolutely no idea why, my idea seems to be exactly the same but with all 6 permutations. Can someone explain it, please?

→ Ответить

kingofnumbers

10 лет назад, # ^ |

+11

simply the official solution code is not correct!

I tried it on the sample test cases

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

It's because that was HONI version of the task (permutation was specified in the task). COCI solutions are up now so you should check them out.

EDIT: Sorry, actually HONI solution was accidentaly uploaded to COCI, it will be fixed soon.

→ Ответить