craus's blog

Training — VII Samara Regional Intercollegiate Contest
By craus, 10 years ago, translation, In English

Hi all!

On saturday, June 21 at 11 o'clock there will be the training by problems of VII Samara Regional Intercollegiate Contest. Let's play it!

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

Comments Comments (33)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

1 hour before the contest Contest is over, you can start virtual participation

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how to solve G and E? Thanks.

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

    G: Let's find a closest point to the given three(that the max distance is the smallest) This can be done by 2 ternary searches : one by X-coordinate and the second by Y-coordinate

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

      Actually it's a center of the circumscribed circle (if the triangle is not obtuse), or the center of the longest side (if the triangle is obtuse).

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

    G: If an answer exists, it can be a point for which 2 of 3 inequalities are actually equalities, so it's the 3rd vertex of an iscosceles triangle with base (or or , you can try all 3). Consider : let , then — we decide that P is supposed to be at (height of ) from the center of the base and that it lies on that height. Finding a perpendicular vector in 2D is easy, so we can calculate the coordinates of . Then, it suffices to check if it's close enough to the 3rd vertex of our triangle.

    E: The time (from 0) until the 1st superpositions without star j is , because star i is directly above us exactly at all integer multiples of li. We just need to find these LCMs, for each one (call it L) check if it isn't too large, and find the smallest k such that kL ≥ M and (if lj|L, then it's impossible, otherwise if k doesn't work, then k + 1 certainly does), and check if the answer isn't too large again. Since LCM is associative, we can calculate the LCM of all elements in an array except the j-th as LCM(LCM of all li: i < j, LCM of all li: i > j), and these 2 can be pre-calculated as prefix and suffix sums... well, LCMs.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well, your solution of E is easier, than mine. In my solution I used segment tree to calculate LCMs...

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hi .. can any one help me to solve (K) i think about it a lot :(

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

    Notice that all you need is an increasing subsequence of ai (and similarly of bi), constructed by taking the first element, then the first one greater than the first, etc. always the first greater one, since if aj ≤ ai for j > i, then if aj could do anything, then ai would do that earlier. You can store each subsequence in a map of (ai, i).

    This way, you can find the first joke that would make either person laugh (or that there's none), just by taking lower_bound(). Then it's just about checking which one goes first.

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

      since if aj ≤ ai for j > i, then if aj could do anything, then ai would do that earlier. You can store each subsequence in a map of (ai, i).

      sorry it make me confused

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

        Then try to think about it, think about the problem in general and compare, it's a better way to learn than everything being spelled out (also, I'm lazy :D).

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

          I'm lazy

          i have a strong feeling that u invented the name lazy propagation :D

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

            In Slovakia, it's more known as "lazy-loading" :D

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

        i really try very hard with it :( i stored only increasing value with their index and used lower_bound and upper_bound but still WA :(

        please help :(

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

          Try this case:

          2
42 42
47 42
1
1 1
          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Constantine

            it's wrong :(

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

            i'm sorry the answer is "Draw"

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

            i think my problem after i found the lower_bound in checking the values

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

            that's my code http://ideone.com/ZKNmry

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

              And it fails the first sample. From it, you can already see that what you need here is upper_bound(), not lower_bound().

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

                Finally :D :D thanks so much :D my fault was i stored the last common increasing value in map, in use the lower bound

                → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with K. Evaluator give me information that my code give wrong result on 6th test case. http://pastebin.com/6aCQ2v2W

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

    6 test is a random test with n = m = 100, try to stress your solution locally

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ok, but have my code any logic to pass the test examples? have i good idea?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Just try to calculate maximum on prefixes and for each query use binary search to find the least position of a necessary spell.

        Sorry for my bad english, i hope you will understand me properly :)

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Sort all the points, then check whether all the points are "zoomed" from the original one compared to the first point, just check the gradient and distance.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem D to me?

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

    I solved it with shortest path, need to read the statement carefully.

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

      Please explain me the first test case and what does at most v moves mean here

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to understand why is wrong my solution for problem K?

I read the last posts about problem K but I can't figure out my mistake.

thanks.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended solution for 100460J - Осколки прошлого?

During contest I solved it using failure function on a string to check periodicity combined with a method to test whether cycle length divides some value. However, other people seem to have written much smaller and simpler solutions.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    Imagine you're going X rooms to the right. While going to the right you can remember what is the state for each room you went through. Now after going X rooms right, switch the states of the candles in the last room and go X rooms left. If cycle is longer than X then you will observe all X rooms in the state as you left them while going to the right. Otherwise you will find the difference and you will be able to calculate the cycle length.

    Now to make number of steps no more than 10·N you can start with small X and if you didn't find the cycle with such X make it two times bigger and try again.

    My submission: 6994198

    PS: Though I have no idea whether it is an intended (if there is any at all) solution or not, just shared an idea which seems to be simple to implement.

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

      Ahhhh. Damn.

      I was performing a similar check to find cycle except for some reason I had this idea fixed in my head that when I'll flip candle in last room I will only verify in this room i.e. I wont check if any change happened in the last X rooms, instead I checked only in the last room. This meant I had a test which could tell me if cycle length divided X or not. So I couldn't perform lots of arbitrary checks. I could only perform checks when I was reasonably sure of cycle length. This led to the entire failure function of string approach.

      → Reply