den2204's blog

By den2204, history, 9 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +69
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it -111 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it -31 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    For D,

    Let us solve this question assuming that the king is at the centre of the board at (500, 500). (If it is not at the centre, then we need around at max 499 steps to reach it as it could have been at the corner.)

    Once you are at the centre, consider the four newly created divisions (or quadrants) of the board. Choose the 3 divisions which do not have the minimum number of rooks. By doing this you ensure that the combination of these 3 divisions has atleast 666 * 3/4 >= 499 rooks otherwise you have not chosen the top 3 divisions correctly (basic pigeon hole principle).

    From now, just move the king away from the section with the minimum rooks ( < 499 in any case) along the diagonal (this ensures that rows and cols are handled together).

    Keep doing this till the corner. You are bound to get a check by a rook as no. of steps required to reach corner from the centre is 499 and from php we know that there are atleast 499 rooks there.

    Eg. 1. king at 999,999

    1. move king to 500,500

    2. let quadrant IV have minimum rooks (167). So quads I, II, III have 499 rooks combined.

    3. while going towards 0,0 (top left point inside quad II), we will end up checking from rows 500 to 1 and cols 500 to 1 simultaneously while going towards the top left diagonal.

    4. since no. of steps to reach the diagonal is at max 499 and we know that there are 499 rooks in these 3 quads, we will get a check(mate) for sure.

    NOTE: I may be off with the numbers by 1 or 2..but i hope you get the point. All of this will occur in less than 1000 steps

    A good question it sure is.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      There is one corner case you need to handle, which is if rooks are on the king's diagonals. You will need to go the nearest row and col together to eliminate the rook as you cannot eat it. I'll fix and share a code with good comments soon

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello den2204 2nd example :

5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3

gives us k = 3 ;

so our top order will be (2-->1) (4--->3) , so while removing edges with weights <=k , we actually disconnects the graph . And how will you decide the priority between 2 and 3 or 2 and 4 .

in the above example 1-->3 has wt. 3 , so how to check this in above topolozical order ?

»
9 months ago, # |
  Vote: I like it +56 Vote: I do not like it

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

Code: https://codeforces.com/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.com/contest/1100/submission/48362464

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you shortly explain your solution for F?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      It's very similar to the standard Gaussian elimination with xors. The difference is that when adding new element to the structure, if we already have an element with the same highest bit, then we keep one with the highest index in the array and continue the process with the other.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually you can serve queries online if you precompute and store the linear basis for each position.

»
9 months ago, # |
Rev. 8   Vote: I like it +48 Vote: I do not like it

Good Explanation for C Captu2re

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 Untitled-1

#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));
}

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Abdo_kamr see this

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Nice explanation. One could also note that the polygon formed by connecting the centers of adjacent outer circles is a regular n-gon inscribed in a circle of radius R + r.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      thank's bro . great observation

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But , how would you deduce the value of 'r' (or the radius of the outer circle) from that sir ???. I couldn't get your point

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        From basic geometry we know that side length of a regular n-gon with circumradius R' is . In our case we observe that the side length of our polygon is 2r (r is unknown) and that the circumradius is R + r. Therefore, we get that and solve for r.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          That's really awesome sir !!! Thanks a lot !

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Another approach is to note that if you cut the triangle in your diagram in half (bisect the angle a) you have a right angle triangle where the hypotenuse is the line connecting the centres of the big circle and little circle. This gives .

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you very much! This helped me a lot.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    why (r+r)^b ? it's (r+r)^2 and how you get second equation ? i think it will be (2*r)^2 = 2 * (R+r)^2 *(1-cos(a))

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry , it's ^2 not b I has a mistake while typing in the second equation try to take (R + r)^2 as a common factor and you will get (2r)^2 = (R + r)^2 * (1 — cos(a))

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        let say x=(R+r)^2 then: x+x-2*x * cos(a) take x as common factor will be x*(1+1+2*cos(a)) then: x*(2+2*cos(a)) take 2 as common factor from(2+2*cos(a)) it will be x * 2 * (1-cos(a) )

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for more let R=2 , r=3 , cos(a)=1/2=0.5; the res for first one will be 25 + 25 — 2 * 5 * 5 * 0.5=25 but in you second one will be 25 * 0.5=12.5

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry , I has reviewed my solution . see the new update of the photo :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think there is one more easy way to do it.. draw the perpendicular from the common point of both outer circle(seen from fig) or equivalently can say bisector of angle a and it will pass through center of the inner circle and after this you can apply simple sin(ang)=r/(r+R) where r=radius of small circle ,R radius of outer circle and ang will be PI/N it all can be easily proved so no worry.. i did it same way during contest and it will work.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why angle is PI/n?.Please explain. Where PI 3.14159

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no , PI here equal 180 not 3.14

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why it can't solve just clearing 'R' in the 6th step? Without apply the trigonometric identity...

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know it's been a while since this contest but this solution for 1100C how does this result in the radius of the outer circle?

    scanf("%lf%lf",&n,&r);
    db sn=sin(3.1415926535897/n);
    
    printf("%.10lf\n", sn * r / (1 - sn) );
    

    Specifically the final equation -> (sn * r) / (1 — sn). I understand that the first statement calculates the angle of the inner circle. Could someone explain or send me a link to some theory in how this results to the outer circle radius?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    while(kx!=500&&ky!=500)
    

    Should be || instead &&.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had same problem and used your solution and got AC but can't understand why || works and && doesn't. can you explain?

»
9 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Just head straight to (999, 1) and you'll win.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    You can move from (500, 500) to (1, 999). It will take you 499 steps while the opponent would have to move 666 rooks

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

T(n) = O(n)log2C + T(n / 2) + T(n / 2)
  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    There are two parts. The first part is answering the queries, and the second part is divide-and-conquer itself. We should see them as seperate parts.

    For the first part, each query costs log2(C), which is the time of combining the left basis and the right basis, so answering the total q queries will cost

    For the second part, calculating the left basis list and the right basis list both costs , so the recurrence will be . Then

    So totally the complexity will be something like .

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The part about the queries don't confuse me. Ignoring the O(logC) components.

      You mentioned that the recurrence is:

      with the solution T(n) = O(nlogn)

      But they have reported the time complexity as O(n).

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I am trying to understand you.

        What do you mean by But they have reported the time complexity as O(n). ?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, thanks for being so patient.

          In the last line of the editorial they have written:

          Complexity is O((n + q)log2C) or O(nlog2C + q).

          This has an O(n) term, but no O(nlog(n)) term, and that is what I meant by

          But they have reported the time complexity as O(n).`

          I feel that they should have a O(nlogn) term in the complexity.

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Yes. I think so too.

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              den2204 could you take a look at this?

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                More strictly, complexity of first solution is , because we can add vector to hull in time proportional to the size of the basis — .

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it
»
9 months ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Seriously dude, it is test case 1. Don't expect other people to help you debug when you haven't put in the effort.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why first solution fails and second one passes for E?

First solution
Second solution
  • »
    »
    9 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    The order(deg) of every vertex need to be different!

    There can be CIRCLE in the edges connected those vertexs with same order.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't really get it

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        consider input below,

        3 3
        1 2 10
        2 3 10
        3 1 10
        
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks :)

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For such a case, how do you figure out which link to reverse? Obviously you cannot give answer as 1 2 3 for vertices (graph is adjacency list implementation)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Besides, how to post part of the submission?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Click paper with blue <> sign and click block, then paste your code

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1100/submission/48427349

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please anyone explain e with the help of an example.It helps me to understand better. thankyou

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to implement E? Any suggestions? Thanks in advance

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need to delete/copy edges every iteration of your binary search. You can simply ignore them when you check for cycles.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      48453854 Thanks, but I could only move forward till test case 12. Again stuck at TLE. Could you please have a look? Thanks again.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        There are a few things you can improve. Try: removing usage of a HashSet hs (not sure why you need it at all); shuffle array before sorting; you don't need to find a solution in every iteration of your binary search: simply use isCycle in your search and once you found k, you can find which edges to reverse.

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So basically what have you have done wrong is that you are telling the indices of every road whose weight was lower. You only have to print the ones that in fact did get reversed.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it, thanks. in fact did get reversed

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how to find out the edges which gets reversed after finding out the min number of controllers required ?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But in the question it is specified that we need not to minimize number of roads. So printing all the roads whose weight is less than K should also be true?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me in problem B. I also wrote code in O(m), but I am getting TLE. Please suggest improments. http://codeforces.com/contest/1100/submission/48488959

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain what is going on in the solutions for problem A :

Sol 1 : https://codeforces.com/contest/1100/submission/48370129

How is the statement C += a[i], p[i % k] += a[i]; related to the problem?

Sol 2 : https://codeforces.com/contest/1100/submission/48337828

What is if ( (i - b + k) % k) doing? Isn't the tabs to be closed are supposed to be of the form b + i * k?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    a set of number which is linearly independent in xor? that is,you can make a linear hull using some numbers, and using the numbers in the linear hull, you can get every number which you can get with the original numbers by xor

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to sort the remaining graph topologically, then figure out which edges to flip.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Iam upsolving problem E (Andrew and Taxi) , I tried removing all edges if ci for edge ei <= mid, while I am binary searching on given ci values (took unique values and sorted them) , as mentioned in editorial I have not done topological sorting to give direction to edges <= mid in the direction of topological sorting, I have just removed all of them because it has been told that I don't have to minimize k which is number of roads to be removed, intuition being removing should not produce cycles and you are allowed to remove as many edges with condition on controllers being minimum

for some reason I am getting error on third test case my code and result of third test case are at : https://ide.geeksforgeeks.org/owLCdYj5ax

for 3rd test case it says given graph has cycles, while I removed all the edges removed by jury answer and more

Jury's answer

7 19

4 6 7 10 11 12 17 19 22 23 25 28 30 32 33 35 36 42 45

My answer :

7 35

3 4 5 6 7 8 10 11 12 14 15 16 17 18 19 20 22 23 24 25 27 28 29 30 31 32 33 34 35 36 39 42 43 44 45

Obiously I must have missed something or misunderstand some detial in the question, will be greatful if someone can point out what could be the reason for the error

https://codeforces.com/contest/1100/submission/48576931

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/

hope it will be helpful when someone wont understand problem E. sorry for my bad english

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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).

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?]