Will there be an editorial for Div2 and Div1 problems ?

hahaha!

*every hour

both in Russian and in English

Yes, it will. In Russian it is stated clearly.

It'll be announced after the contest begins. :D

Amazing! Thank you.

What is seed? My position in sorted list of competitors ordered by their rating?

Your submission : http://codeforces.net/contest/782/submission/25256168, Should have Failed on : Weak systest

4
DII D
DII C
ABB A
ABC A

Please remove your code, it is covering page, just keep submission link please.

I had the same problem. After 5 unsuccessful submissions, I put cout.precision(7); at the beginning of the code and it passed the pretests.

Don't we need ternary search?

No. A unimodal function can't be solved with binary search. You need ternary search.

Binary search the answer.

Binary search a suitable x and find t, take the minimum of all iterations.

Binarysearch

eps = 0.00000001;
L = 0; R = 100000007;

while( R-L > eps){
  m = (L+R)/2;

  if(canmeet(m) R = m;
  else L = m;
}

res = (L+R)/2;





canmeet(long double meettime) {

   each person can go to the left to x[i]-v[i]*meettime , and to the right to x[i]+v[i]*meettime

   you have to check if the intersection of all segments [ x[i]-v[i]*meettime , x[i]+v[i]*meettime ] is not empty

}

I passed pretests using ternary search. I'm not sure it is a correct solution, though.

I make it 10.

Suppose now we are searching (l,r). Denote t=(r-l)/10, we divide (l,r) into 10 smaller sections(l, l+t), (l+t, l+t*2) ......(l+t*9, r), then compute the result of l+t, l+t*2, l+t*3 .....l+t*9. Suppose l+t*k is the minimum, the optimal answer must be in (l+t*(k-1), l+t*(k+1)).(10 sections -->2 sections）

B -- This can be modelled as a maximum bipartite matching, with all teams sharing the first option having all their first options removed. This is a standard algorithm -- See Hopcroft-Karp for an efficient algorithm.

B is just tedious implementation, I don't see graphs here.

D is matrix multiplication, I don't see graphs here.

It is test 20.

u r not alone my friend. prestest 3 never cleared for me.

Too. Can't even imagine, where I am wrong. Also, I haven't got any changes in my rating. Is it ok?

You was right

I used binary search.

Using bitset.

I was thinking O(N^3 * log (10^18) / 64), where 64 comes from using OR operator to do something like union of sets. But I didn't have time to code it. Besides, I'm curious to know whether there is something faster than O(N^3 * log (1e18)) too.

Edit: seems like I was beaten to the response.

maximum vertex degree + 1

It was just a simple one-pass dfs. For each node, you assign it all values to its children which are not equal to itself and its parent.

Of course it work, but when you check if there is at least 1 vector with size 1 we have to use the second option, we have to continue searching until all vector of size 1 can use first option

Put in an array the nodes following the visiting order of a dfs on the graph. Then, for each contiguous block of ceil(2n / k) nodes in the array, assign a robot. If a robot gets no node, just assign any node to it. This works because the dfs spanning tree has exactly n - 1 edges and you visit each of them 2 times (going down and up); hence, 2(n - 1) + 1 nodes will be visited.

consider a dfs tree

If you don't post this comment, I won't know the starting position is fixed forever though I pass it...

System tests are becoming weaker recently, especially in Div 1.

Bad job problemsetters :(

Omg, I can't believe people are creating anti-unordered_map tests when hacking, but nobody create tests against such thing and people get away with it xd.

I had exact same problem, can somebody explain what getting WA4 means in terms of solution incorrectness?

Your codes are not same and have diffs here :

if ((int) colors.size() == neighbours) { break; } "==" instead of ">=" that when there will be a huge vertices with degree of 1 and ans be huge do You will get TLE.

Exact same situation :(

Exactly different situation :(

By Technocup onsite results I took C first

Problem C — Spend 1 hours and a half, can't come up with a solution

Problem B — Took me 1 minute to come up with a solution.(Because Binary/Ternary Search is my favorite topic)

Moral of today's contest: read all problem's statement in first come first solve manner.

me too and it is really making me angry -_-

Div.2 B

I understood solution from my friends code, maybe it can help you.

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>

#define MAXN 100010
#define INF 0
#define PI 3.14159265359
#define pairr pair<double, double>
#define pairrr pair<double, pairr>
#define f first
#define s second
#define pb push_back
#define ll long long
#define MOD 301907
#define IO ios_base::sync_with_stdio(false); cin.tie();
#define PQT pairrr
#define PQL priority_queue<PQT, vector<PQT>, less<PQT> >
#define PQG priority_queue<PQT, vector<PQT>, greater<PQT> >

using namespace std;

int n,i;
double l,r,m1,m2,x[60010],v[60010];

double f(double m)
{
    double res=0;;
    for (i=0;i<n;i++)
    {
        res=max(res,(abs(x[i]-m))/v[i]);
    }
    return res;
}

int main()
{
//    freopen("input.txt","r",stdin);
    cin>>n;
    for (i=0;i<n;i++) cin>>x[i];
    for (i=0;i<n;i++) cin>>v[i];
    l=1;
    r=1000000000;
    while (r-l>0.000001)
    {
        m1=l+(r-l)/3;
        m2=r-(r-l)/3;
        if (f(m1)>f(m2)) l=m1;
        else r=m2;
    }
    cout.setf(ios::fixed);
    cout<<setprecision(10)<<f(l)<<endl;
    return 0;
}

here is my solution 25259459

I use ternary search for finding a meeting place

I did this: Binary search on the answer.

For each value t, you can examine if all of the friends can meet somewhere within t seconds.

First, examine what is the minimum x_i, such that x_i = pos_i + speed_i * t. Then, min(x_i) is the best place to meet if we have t seconds of time. Try to examine if everyone positioned after min(x_i) can reach min(x_i) after t seconds. If yes, it is possible to meet within t seconds; it is not otherwise.

Stupid greedy implementation. Try to name the team using the first choice. If you can't, try to name the team using the second choice and rename those that conflict with the new name. If you can't rename those, it means that it is impossible.

Maintain a DSU and place all the teams having same team name [first three characters] in a same component and also maintain the size of each component. Now, if there are two teams u , v (u != v) such that both the teams belong to the same component and the short names formed by using second option for both u and v are equal, then the answer is NO. Now, name all the teams in a component having size > 1 by using second option. Teams having only 1 node in its component has two options, either use first option or second, if both the strings are already used then again the answer is NO, else use either of them which isn't used yet.

PS- This solution is wrong, test data were weak enough to let this solution pass.

Test where it can fail :

ABC DDD

ABD DOG

Maximum Bipartite Matching shall be used to assign the shortnames to the teams having only 1 node in its component.