hloya_ygrt's blog

By hloya_ygrt, history, 7 years ago, translation, In English

811A - Vladik and Courtesy

Hint
Tutorial

811B - Vladik and Complicated Book

Hint
Tutorial

Challenge. Can you solve the problem with n, m ≤ 106?

811C - Vladik and Memorable Trip

Hint 1
Hint 2
Tutorial

Challenge. Can you solve the problem with n, a[i] ≤ 105? Try to use the fact, that .

811D - Vladik and Favorite Game

Hint 1
Hint 2
Tutorial

Challenge. Assume this problem: let's change all dangerous cells on walls, i.e such cells, in which it is just impossible to enter. Now you have to generate such string from moves 'L', 'R', 'U', 'D', that without dependance on possible button breakage of pairs 'L'/'R' and 'U'/'D', as in original problem, will visit finish cell. Of course, it is not necessary to stop at finish cell, you just have to visit it at least once.

811E - Vladik and Entertaining Flags

Hint
Tutorial
  • Vote: I like it
  • +82
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Challenge. In problem A can U solve if a , b <= 10 ^ 18 ?

hint
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Can be done in

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

      The hacking test is

      443672224612562498 443672223946475251

      Answer: Vladik (you can easily check this with a slow solution).

      Doubles often fail by precision, it's not recommended to use this. Casting everything to long double or avoiding doubles would help.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -24 Vote: I do not like it

        My answer is correct even for that "hacking test", it is below this comment.

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

          Ok... How about this test?

          286539999388964720 286539998853670410

          Answer is also Vladik.

          You solution prints Valera (I tried custom invocation).

          By the way, the generator is

          Generator

          Try to stress test your solution with this generator and see your code also fails by precision.

»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Problem A is O(1). Here is my answer.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +47 Vote: I do not like it

    sqrt function is O(1) ? how is that possible?

    What is order of sqrt in c++?

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

May you please find a mistake behind a logic of my approach for problem C : 27416588

»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

In probelm E,the tutorial is too short to understand,could anybody give more details about how it be solved? Thx :)

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    Let's say we have two segments A and B with endpoints [LA, RA] and [LB, RB] and LB = RA + 1. Let's also suppose we have three informations for each one of these segments: 1) how many connected components are there in it; 2) in which component every one of the n elements of the column Li is; 3) in which component every one of the n elements of the column Ri is.

    Now, we may want to know these three informations for the segment C, which has endpoints [LC = LA, RC = RB]; i.e., C is the merge of the segments A and B. If we are able to do this merge correctly, then we can build a segment tree such that each node stores the three said informations for its range and thus get the correct information for any given range via the query function.

    The segment C will have compA + compB - unionsAB connected components, where compi stands for how many components are there in segment i and unionsij for the number of unions made when merging segments i and j. For each line i of the n lines, we gotta union the components of the columns RA and LB if grid[i][RA] = grid[i][LB] and update LC and RC if some change occurred in the components of the elements in these columns.

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

      Very nicely explained, thanks! I can see how to implement this solution using Segment Trees. The editorial, however, mentions Interval Trees, which I've never worked with before. Are these interchangeable words for the same data structure?

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

        I don't know what a Interval Tree is, but this page says that it is a data structure similar to Segment Tree, so probably they are not the same.

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

      Quite clear,thanks for you help! :)

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

      When merging intervals A and B, wouldn't it be necessary to use DSU/union-find data structure? I think you would need a DSU per node in the segment tree. But then you would face the problem of merging DSU's, both for building the segment tree and for answering queries, which will yield TLE considering that there are q = 10^5 queries to answer. How can you solve that?

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

        Take a look at this code. We can just naively merge two nodes in O(n2). Maybe a DSU approach would be even faster. I'm kinda lazy to do the maths right now but it should pass...

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

Explanations in the editorial are shorter than the corresponding problem statements

»
7 years ago, # |
Rev. 3   Vote: I like it -23 Vote: I do not like it

Another way to solve A:

We know that, Sum of first n odd numbers = n*n and sum of first n even numbers = n*(n+1).

Notice that Vladik always gives odd number of candies and Valera always gives odd number of candies.

If Vladik can gift n times, then n*n should be at least a, so, n = floor(sqrt(a)) . Notice that Vladik can't give right amount, if Valera can give gift at least same number of times, i.e. n times.

Now, to gift n times with even numbers, Valera needs n*(n+1) candies. If Valera has at least n*(n+1) candies, then he can gift n times, and then Vladik is first who can't give right amount of gifts.

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

Problem B for n, m ≤ 106 can be solved with AVL, there are another way for solve it?

»
7 years ago, # |
  Vote: I like it -20 Vote: I do not like it

The time of problem B is O(n·m)???

For this problem n, m ≤ 104 so if n = m = 104 then the time would be , that runs on 2 seconds???

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

    Rule of thumb :- On every major platform O(108) runs in about 1 sec. Except on Codechef, where sometimes it gets TLEd

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

you can solve problem A in O(1)

by using this formula Sn = n/2 *(2*a+(n-1)*d)

n number of terms , a = the first element of series "1 for Vladik and 2 for Valera" , d= increment = 2

so the formula for count the number of term for

Vladik = n/2 * (2*1+(n-1)*2) = n(1+n-1) = n^2 = a so na = sqrt(a)

Valera = n/2 * (2*2+(n-1)*2) = n(2+n-1) = n^2+n = b so n^2+n -b =0 and solve it by quadratic equation nb = ( -1 + sqrt(1 + b*4) ) / 2

if (na <= nb) "Vladik"

else "Valera"

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

For the challenge of D part . I have an idea with string of size atmost 4*n*m.

The idea is first just generate the string from start to final assuming all buttons are correct.Lets call s1.

Now assume (L/R) is reversed and simulate s1 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (L/R) . Lets call this S.

Now concatenate s2=s1+S.

Now assume (U/D) is reversed and simulate s2 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (U/D) . Lets call this S.

Now concatenate s3=s2+S.

Now assume (L/R) & (U/D) is reversed and simulate s3 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (L/R) && (U/D) . Lets call this S.

Now concatenate s4=s3+S.

Now it must be visible that s4 passes through final for any possible breakings.

Can someone find a flaw in this??

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

How to solve the challenge problem for problem C

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

Is it possible to solve E using SQRT-decomposition? I mean something like this (but I missed that spots can be splitted, so it is wrong anyway).

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

    I think it's a bit too slow, O(N*M^(1.5)) is about 1e8, while the compiler could barely optimize the complex code.

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

      3*10^8 to be accurate. I think it can suits in 2 seconds.

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

What is the meaning of this line , can anybody explain?

Assume, that there was such train carriage, that finished at position i. Then iterate it's start from right to left, also maintaining maximal ls, minimal fr and xor of distinct codes cur. If current range [j, i] is ok for forming the train carriage, update dpi with value dpj - 1 + cur.

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

So how to solve C for n, a[i] ≤ 10^5 ?

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

A lot of people (including myself) found the explanation for problem C hard to understand, so I thought I'd explain my solution.

Solution
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

When n ≤ 104 I always assume that O(n2) shouldn't work. I'm surprised!

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

Would someone mind help me look at my code for Problem E? I suppose my code have a time complexity of O(N*(M+Q)*logM) with each merge action as O(N), but I suspect that I messed up part of the implementation thus causing TLE (is the bfs search too expensive for merging?).

http://codeforces.net/contest/811/submission/27392571

Thanks in advance.

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

    I see that your solution is extremely non-optimized. Problem is not in bfs, but in vectors inside struct node. You shouldn't store all the edges this way, you can generate them on the run (checking if there is an edge when trying to bfs). For example, your code works 7 seconds in polygon, while this code works in 3 seconds (didn't pass in 2 sec too) (I just made edges in nodes global). This happens because dynamic memory allocation is too slow.

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

Challenge Div2C
Let dp[i] denote answer when we have created segments till 'i'.

We can construct a segment tree which can answer the following for a range [l, r] -
1. Maximum of last occurrences of the elements in the range [l, r] -> Q(l, r).last
2. Minimum of first occurrences of the elements in the range [l, r] -> Q(l, r).first
3. XOR of the elements whose last occurrences lie in [l, r] -> Q(l, r).ans

For a valid segment, Q(l, r).first = l & Q(l, r).last = r. So we are checking at those indices only where Q(l, r).last = r. And if Q(l, r).first != l, then we need to change 'l' to atleast Q(l, r).first and then again check the condition.

dp[i] = dp[i-1]
If Q(l, r).first = l && Q(l, r).last = r
    dp[i] = max(dp[i], dp[l-1] + Q(l, r).ans)

If Q(l, r).first < l && Q(l, r).last = r
    While l < Q(l, r).first && Q(l, r).last = r
        l = Q(l, r).first 
    If QUERY(l, r).first = l && QUERY(l, r).last = r
        dp[i] = dp[l-1] + Q(l, r).ans

We can save the optimal index for 'l', which will bring the overall complexity to O(nlogn).

Solution

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

Problem C dfs solution

http://codeforces.net/contest/811/submission/27572002

Description:

  1. Put all LR segments in a tree where each segment's parent is either whole list with root = MAXN or smallest segment that fully contains it.
  2. Mark all segments that contain some other elements other than their children with w[i] = 1, their value cannot be xor, only sum of its children
  3. Run dfs from root, and based on value of w[u] return either sum of all children segments results or if w[u] == 0 maximum between sum and xor.
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My O(n) solution for problem C... Since I'm a beginner in dp (and English So I just implement my own thoughts.. and then I get the code blow.. http://codeforces.net/contest/811/submission/29330084

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

Problem D is so bad.