Auto comment: topic has been translated by den2204 (original revision, translated revision, compare)

this wouldn't have been needed if you gave us actually useful good problems.

why so short solution for D , please elabprate what u r saying den2204

F can be solved in O((n + q)logC).

Code: https://codeforces.me/contest/1100/submission/48345032

System tests for D are too weak. My submission that moves king to the center and then allways moves it to the same corner passed system test.

Code: https://codeforces.me/contest/1100/submission/48362464

Good Explanation for C

the Radius of the innar circle = R and radius of the outer circle = r by connect the center point of the innar circle with two center points of the other consective small circles , the angle (a) = 360 / n and the traingle is Isosceles triangle from the cousine law we will reach

#include "bits/stdc++.h"
using namespace std;
const long double PI = acos(-1);
int main()
{
  int n , R;
  cin>>n>>R;
  cout<<fixed<<setprecision(7)<<sin(PI / n) / (1 &mdash; sin(PI / n));
}

http://codeforces.me/contest/1100/submission/48402367

why D is falling? I just can not understand, plz help

I think, author's solution for D is wrong. For example, put the king to the center, put 333 rooks to positions 1 1, 2 2, 3 3,... 333 333, and other 333 rooks to positions 999 999, 998 998, 997 997,... In such case the king has no chance to win.

I tried to find additional restrictions in the task, excluding such an example, but don't see it. Am I wrong?

UPD: Thank you, guys, you are right

D question was very good! Very good effort on your first contest as author.

Could somebody explain the time complexity of the hull method in F please?

I am seeing a O((nlog(n) + q)log²C) time complexity, with the recurrence

An International Grandmater(djq_cpp,He is only 13!!!!) told me there are answer code for problem F on the Internet.I copy the code and get accepted(I didn't take part in the contest.).So F is a problem appeared before.That's really bad!!!Submittion 48412606

Problem D 091 there: http://olympiads.win.tue.nl/imo/soviet/RusMath.html

Если следовать описанному алгоритму для D, можно нарваться на то, что король побьет ладью. Подозреваю претесты тоже эту ситуацию не хендлят

(https://codeforces.me/contest/1100/submission/48425126)

Why first solution fails and second one passes for E?

while(!q.empty()){
    int s=q.front();
    q.pop();

    for(auto t:v[s]){
        in[t]--;
        if(!in[t]){
            deg[t]=deg[s]+1;
            q.push(t);
        }
    }
}

vector<int>sol;
for(int i=1;i<=m;i++){
    if(e[i].w<=k){
        if(deg[e[i].from]>deg[e[i].to])sol.push_back(i);
    }
}

int cnt=0;
while(!q.empty()){
    int s=q.front();
    q.pop();
    deg[s]=++cnt; //difference is here

    for(auto t:v[s]){
        in[t]--;
        if(!in[t]){
            q.push(t);
        }
    }
}

vector<int>sol;
for(int i=1;i<=m;i++){
    if(e[i].w<=k){
        if(deg[e[i].from]>deg[e[i].to])sol.push_back(i);
    }
}

In ques E,i am getting wrong answer on test case 7 but am not able to identify the problem in my code.Can somebody help me with it please?

link : https://codeforces.me/contest/1100/submission/48427349

Can anyone explain B plz. If possible give your code too xD

If I return 1 at the end of interaction I will get Runtime Error. Had many RE because of that!

How to implement E? Any suggestions? Thanks in advance

48427795 Could anyone help me with prob E. My solution is an implementation of the tutorial, however I get a TLE for test case 10. Many thanks in advance.

For E, can someone explain what i'm doing wrong.

1. I binary search on K(max edge wt to be removed) as given in the editorial. Find appropriate K.
2. To construct graph remove all edges having wt <= K.

code For 3rd tc, K is correct but it contains cycle if i remove edges by above rule.

I did this because here it says reversing an edge is same as removing in directed graph.

Can someone please explain or link me to what is being done with the hulls , and what are hulls ? Is it related to the convex hull or something related to do? Thanks

In problem E, after finding the min value of k using binary search how to determine which edges to be reversed. For example-

3 3
1 2 10
2 3 10
3 1 10

This will give me the k = 10 but how to determine which edge to remove.I was thinking of removing all the edges with val<=k. But the above test case will pose the problem , that the graph will become disconnected.Help please.

why the solution 2 for F is O(nlog²C + q)? I think it should be O((n + q)logC) or did I misunderstand it? here is my solution

I have another way to solve B.

If we list the positions of every difficulty in n lines such as :

1: 3 11
2: 1 4 5 6 8 9
3: 2 7 10
(the first example)

we can easily find that a round will be held when p - th problem is put into the pool, where p is the maximal number in each column. (In the example above, they're 3 and 11.) So we can denote cnt[i] as the number of problems in difficulty i and f[i] as the maximal number in i-th column and then do f[++cnt[a[i]]] = i. Because the position i is increasing, f[j] is the maximal number. Print 1 if any f[j] (j ≤ min(cnt[k])) equals to i, otherwise print 0. The complexity is also O(m).

Update: I understood the problem incorrectly. I thought that the king must stay checked after a rook moves. Not sure why. So my example is an instantaneous win for the king.

[It seems to me that the proposed solution to D is incorrect. Consider 5x5 board with 3 rooks and the king located like this (X for a blank):

RXXXX
XXXRX
XXKXX
XXXXX
XXXXR

Here we have 3 rooks and the king needs (sort of) 2 steps to reach the corner. However, considering that we can't take the rook at the first step — it is impossible to win. If we go right-up or up-right it is easy to see that all rooks can escape.

Now you can create a configuration on 999x999 board where 500 rooks are placed in 3 quadrants such that this bad case will occur when the king is 2 steps away from the corner (and blocked by the rook). And you can easily place other 497 rooks such they will escape one by one as the king moves diagonally from the field (500, 500).

Did I miss something?]

Explanation for 1100C - NN and the Optical Illusion