Блог пользователя dalex

Автор dalex, 2 месяца назад, По-русски,

Привет.

11 марта в Самарском университете состоялась ежегодная олимпиада по программированию, и мы снова выкладываем ее в тренировки Codeforces. Тренировка пройдет в воскресенье, 18 марта, в 11:00 MSK.

Этот контест уже третий год проводится личным. Поэтому просим всех тоже участвовать лично. Наиболее интересно должно быть фиолетовым и синим участникам.

Ну и как обычно,

 
 
 
 
  • Проголосовать: нравится  
  • +88
  • Проголосовать: не нравится  

»
2 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Can I register with my team? Or only individual contestants?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    You can, but people on the onsite contest played individually.

»
2 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Will there be an editorial after the contest. It becomes really hard to get solutions for all the problems from the comments for beginners like me.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I enjoyed the contest, the problems were really interesting. Can I see the case I'm failing at on problem M?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone share his code for C.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Code

    I'm not sure how clear it is but I can explain anything if it's unclear.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you please explain how your code works. This is my Code. The Idea is same as yours I guess but its giving wrong answer on Test 11.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        I start by sorting the ranges by their end points. Then as I'm processing the end points, ill greedily build my set.

        Basically, if by the time I get to the end of some range and there's no number in my set (that's the ceiling() call) that belongs in it's range, then I'll add that range's endpoint to the set.

        This is always optimal because I'm going in increasing order of endpoints so every time I add a number to my set, it's as large as possible so it's most likely to fit in the other ranges (who all have end points greater than the current one).

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Why I sort the ranges by their start points then I got wrong answer ? But sort the ranges by their end points will get AC ?

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Any hint for problem H or L???

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Problem H:

    BFS off of every monster tile and only go a maximum of d distance away. Any tile that was touched by a monster's BFS is now no longer usable. Now BFS from your starting point and do regular shortest path in a grid but making sure to ignore cells touched by the monsters.

    Problem L:

    For every position i in the string, find the next position of every letter in the alphabet. Now keep some kind of queue and find the next position of whatever letter is queried (or pop the back of your queue). If the next position of the queried letter doesn't exist, the answer is no otherwise it's yes.

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Задачи в ваших контестах очень интересные и разнообразные! Продолжайте в том же духе!

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

What's output of problem E for this test case: abaca aabac

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the test 48 on F?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    During the contest this test helps me:

    4
    3 2 3 4
    1 4
    1 4
    0
    

    Answer is NO

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hints on how to approach I? My approach can't seem to get past test 12.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I used this approach:

    Define a procedure findRoot(vertices, leafs, depth) for search a tree root among vertices, inside it we need to find two leafs from a different subtrees (relative to root). It can be managed in O(size(vertices)), then you can easily find a root (it is a vertex, that dist(leaf1, v) = dist(leaf2, v) = depth). Then you need to run findRoot recursively from left/right subtree.

    So, each findRoot procedure takes 2 * size(vertices) queries (2 * nlogn in total) and additional queries at start to find leafs.

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      That makes a lot of sense. Thank you!

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Hi, I can't figure it out how do you manage to classify vertex according to left and right subtree for the recursive call. Can you explain that part? Because you pass vertices and leafs parameters that, I guess, represent vertices and leafs of the current subtree.

      Thanks

      • »
        »
        »
        »
        4 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You have two leafs from different subtrees, so lets call them left & right. So to classify arbitrary vertex we need to compare dist(left, vertext) and dist(right, vertex) — if dist from vertex to left vertex smaller then vertex in a left subtree and vice versa.

    • »
      »
      »
      4 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you show me the code? I try many many ways but i still can't figure it out.

      Thanks.

      • »
        »
        »
        »
        4 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's very easy to include interactor in the solution and test it locally. All tests for this problem are just trees with random-shuffled vertex indices (there are no any special cases). So it doesn't seem you "tried many many ways".

        • »
          »
          »
          »
          »
          4 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          That's because I make too many queries then I get a wrong answer,but i have no idea how to reduce the query though I know my ways can restore the tree.

          • »
            »
            »
            »
            »
            »
            4 недели назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Spoiler
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's test 22 on H ?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Test 22 generator
»
2 месяца назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

The game .C.O.N.T.E.S.T: Unexpected Behaviour from Problem K "Video Reviews" does not exist. But recently our gamedev team Veslo Games released the game .T.E.S.T: Expected Behaviour (from creator of Codeforces Simulator!) to the Steam Early Access. If you like puzzles, consider checking this out!

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is there a algorithm about problem M?or it's just a simulation?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Spoiler, M
»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can any body help me for problem C ?? I can not find the algorithm. And Why (2 _ 1 5 ) is a wrong answer on test_case 1 for problem C.

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could anybody help me with the problom I, I can't pass the test 5

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am stuck on problem H 8-th test . Can I see the case I'm failing ?

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Существует ли разбор контеста?

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone provide any hints for problem K ,video reviews? thanks.

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Main hint: binary search

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thanks for replying.binary search i figured out but was not able to come up with a predicate.thanks.

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Suppose we have X, and we need to check if X is enough to get m reviews. You need to process the bloggers from left to right. There are two options:

        • blogger is already interested in the game — just increase reviews count
        • blogger isn't interested in the game — you need to convince him (if already convienced count < X) and increase reviews count.

        It can be easily proven that greedy algorithm works.

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone knows what is the case 50 for problem F?

Thanks

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the test case 50 in problem F? I got stucked there :(

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    F, test 48
    F, test 50
    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, I don't know why my aproach was wrong. At the end I changed my strategy and get AC.

      Do you have any hint for problem D? I belive that a maxflow algorithm could said if it is possible or not, but I can't construct the solution

      • »
        »
        »
        »
        4 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Certificate in D
»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the test case 52 in problem F? I got stucked there.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The same as test 48 (see my comment above), but with different random seed

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the approach for 'L — Queries on a String'? My current solution exceeds the memory limit at test 7.