dalex's blog

By dalex, 4 years ago, translation, In English,

Hello everyone,

Some days ago we had an annual programming contest in Samara, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, 17 April, at 11:00 MSK. Site clist.by says that there are no intersections with something important that day.

Previously, it was a team contest, but this year we decided to make it personal. So we ask everyone to participate solo. This is how the results will be the most adequate.

And as usual,

 
 
 
 
  • Vote: I like it
  • +238
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great :D

I really like the previous Samara contests :)

»
4 years ago, # |
  Vote: I like it -38 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    No, it's Codeforces not Facebook. Tagging your friends won't appear for them in notifications.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But what if it did actually work?

      I mean instead of messaging five different people on CF about the same contest, wouldn't it be nice and convenient if we could just tag them and they receive notification or something?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        I don't think that tourist will like it , as he's going to be fully spammed.

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

          Not if only the people in friend list of tourist are allowed to tag him ;)

          A person should get notified only if his/her friend tags him/her.

          PS — BTW I had no idea you replied to my comment till I revisited this page just now. :P May be a person should get notified if someone replies to his/her comment?

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

            You will get notified through your email. I think it would be more convenient to get notified here rather than in email.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

how to solve E?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it
    solution
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      Alternate Approach
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Here is my game, on which the Bisection problem from this contest was based.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone show, how to solve "L"-Chess Match.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    We want to understand are there any permutations A of a and B of b such that the number of positions i with A[i] > B[i] is more than n / 2.

    Let's find the worst case(when the number k of such positions is the greatest possible) . It is easy to see in this case some of the k least numbers of b are less than some k numbers of a. So let's find k greedily step by step. Every step needs to find the least number x in b, and the least number y in a which satisfies a condition y > x. So k = the number of times when you can find such y

    For doing this you may use set or simple sorting
    Just do this algorithm with (a, b) and (b, a) and print the answer

    Your text to link here...

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

    I compared the n/2 + 1 smallest elements of A with the same number of the largest elements of B, element-wise (0th with 0th, 1st with 1st, etc.).

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Could anyone tell me how to solve pro H and pro J? Thanks in advance.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Solution J
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Is that an arbitrary cycle?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Yes. Code

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, it's really amazing :D. Thank you so much :D.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What should be the output of this test case?? and why

          4 5

          #####

          ...#.

          ...#2

          1..#.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's incorrect test. From statement: "From every free cell it's possible to reach every other free cell by moving only through the cells sharing a side."

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Solution H

    Spoiler
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it
      In addition to problem H
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    H. Let's have a look at some K. Let's create array c[] with c[i] = 1 if a[i] <= k <= b[i]. Then the answer for a query with group's size = K is the K-th index i with c[i] = 1 or -1 if there is no K ones in array. For more fast processing the queries(finding k-th positions/updating the cell) we can build a segment tree over the array c

    Now let's iterate over K from 1 to n. Before answering for a query K we must change c[i] to 1 for every position with a[i] == K (in segment tree, of course). After answering for a query K we also must change c[i] to 0 for every position i with b[i] == K. As you can see, implementation these operations keeps real array c in some moment K in our segment tree.

    Maybe code is the best explanation

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Another solution H.

    Spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also another

    solution for H
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me how to solve problem F ?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it
    Solution
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you :D

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
      Alternative solution
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Function for square of distance between points at the time 't' is a*t^2 + b*t + c. I don't think, that it is harder to find minimum of that function: max(0, -b/2a) — than understand and implement your solution correctly and without problems with precision.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          He meant this one: 17360287

          But the solution by mkirsche (comment) is the most reliable. There are problems where numerical solutions don't work.

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

Can anyone give me some tests for problem F, please? Following operations I did..

  1. Point p1 = new Point(x1, y1), q1 = new Point(x1+vX1, y1+vY1);
    Point p2 = new Point(x2, y2), q2 = new Point(x2+vX2, y2+vY2);
    
  2. After that I got two segments... Then I found minimum distance between two segments like this:

if(doIntersect(p1,q1,p2,q2)){
			System.out.printf("%.15f",0.0);
		}else{
			double d1=Double.MAX_VALUE,d2=Double.MAX_VALUE,d3=Double.MAX_VALUE,d4=Double.MAX_VALUE;
			if(isActue(p1,p2,q1) && isActue(q1, p2, p1)){
				double a =p1.y-q1.y, b = q1.x-p1.x, c = p1.x*q1.y-q1.x*p1.y;
				d1=((double)abs(a*p2.x+b*p2.y+c))/(sqrt(a*a+b*b));
			}else{
				d1 = min(distance(p2,p1),distance(p2,q1));
			}
			if(isActue(p1,q2,q1) && isActue(q1, q2, p1)){
				double a =p1.y-q1.y, b = q1.x-p1.x, c = p1.x*q1.y-q1.x*p1.y;
				d2=((double)abs(a*q2.x+b*q2.y+c))/(sqrt(a*a+b*b));
			}else{
				d2 = min(distance(q2,p1),distance(q2,q1));
			}
			if(isActue(p2,p1,q2) && isActue(q2, p1, p2)){
				double a =p2.y-q2.y, b = q2.x-p2.x, c = p2.x*q2.y-q2.x*p2.y;
				d3=((double)abs(a*p1.x+b*p1.y+c))/(sqrt(a*a+b*b));
			}else{
				d3 = min(distance(p1,p2),distance(p1,q2));
			}
			if(isActue(p2,q1,q2) && isActue(q2, q1, p2)){
				double a =p2.y-q2.y, b = q2.x-p2.x, c = p2.x*q2.y-q2.x*p2.y;
				d4=((double)abs(a*q1.x+b*q1.y+c))/(sqrt(a*a+b*b));
			}else{
				d4 = min(distance(q1,p2),distance(q1,q2));
			}
			System.out.printf("%.15f",min(d1, min(d2, min(d3, d4))));
		}
  1. Thanks..
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve I and M ?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it
    Solution for M
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem A-Treasure Island??

Got Wrong Answer in Case No-9. I use dp and dfs.

My code is here-17709718

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

    You can replace '?' with '.' or '#'. But you replace '?' only with '.'

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My idea is-

      1. If all land land position is connected and can be reached from any land position then others '?' mark can be replaced with either '.' or '#'.

      2. If all land position is not connected then we can replace '?' mark to '.' so that all land mark become connected.

      If we need every '?' mark to change in '.' mark to connect all land mark then we have a valid solution and If there remain some extra '?' mark that can be replaced with either '#' or '.' so this situation is ambiguous.

      And if we can't make all land mark connected after using all '?' mark then this situation is impossible.

      I am not sure my idea is correct or not. Please Give me some hints/idea or source code.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can run bfs\dfs from all '.' and mark all reachable '?'. If '.' are not connected then answer is "Impossible" else check for all marked '?': if you replace this '?' with '#' and all '.' are connected then answer is "Ambiguous" (you can replace this '?' with '.' or '#' so that '.' are connected).

        my source

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know how to solve Problem-A? Get wrong answer at test 14,I used DFS. My code is here-17886458

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

17886458 Problem A Treasure Island I get wrong answer at test 14 I used dfs

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be solved by processing cities, ordered by descending their populations.

    You can use map for storing already processed cities by their coordinates.On each step you simply look and compare two cities by their distances to city, processing on this step: nearest from left and nearest from right.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve I?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem I?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Solution of problem I
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank a lot, I was able to solve now.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one tell me how to solve problem b?