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

Автор aajjbb, 10 лет назад, По-английски

Hey.

Brazil's first phase of ICPC 2014/2015 Regional will happen this next Saturday (09/13/2014). The contest will happen in the same time in the UVA system.

Link

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

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

how do you register in that contest?, or it does not need registration?

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

what can I do sometimes?

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

    You can ask questions that actually make sense, for example. Because this one doesn't.

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

What time will the contest start?

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

The UVa contest will not be held at the exact same time as the real contest.

The real contest starts at 17:00 UTC and the UVa contest starts at 19:00 UTC as stated on UVa homepage. Here is the timeanddate link (provided by UVa).

http://www.timeanddate.com/worldclock/fixedtime.html?iso=2014-09-13T19:00:00

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

Can someone explain how to solve problem E and G?

E — Ecology: I tried to generate all possible combinations using M elements but I got WA.

G — Letters: I tried using BFS, Dijkstra getting WA, DFS with some prunning and got TLE.

thanks.

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

    G — using bitmask+bfs:

    You have only ten letters, for all of them, you can either use it only lowercase or only uppercase. You can use a bitmask to represent this, each bit 0 = using lower, 1 = using upper.

    Iterate all possible bitmasks, then for each one try to do a BFS following that rule.

    This is O((2^L)*N), but since L=10 and N=100^2 it's ok. (edit: N=100^2, not 100)

    -- E:

    We could not solve it during contest time and we were thinking about the same approach. Try this test case on your solution, maybe this is what fails (our approach was failing cases similar to this):

    4 10
    1 1 1 1 1
    1 2 2 2 1
    1 2 1 2 2
    2 2 2 2 1
    

    Answer should be 20

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

      ten letters?

      as far as I remember you have 26 lower case + 26 upper case letters, 2^52 to iterate over all subsets is too much.

      I tried using BFS + bitmask to represent the set of used letters.

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

        From the official statement: "each square has one of the first 10 ASCII letters, abcdefghijABCDEFGHIJ" (http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4662 for reference).

        You don't need 2^(2*L) states as you're saying, though. What you are thinking is probably one bit for representing the lowercase version and one for the upper (0 you are using it, 1 you're not).

        But you can actually use one bit for each letter. 0 = you are using it lowercase, 1 = you are using it uppercase, iterating all possible masks is 2^L in this case.

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

          :O

          G: I misunderstood, It may be because problems was in spanish (I didn't like this), I was trying to solve the problem for 26 letters instead of 10

          E: I didn't evaluated a case like you provide me, I know my error now.

          Thanks.

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

      hello respect to problem G , why is O((2^L)*N) ?? should not be O((2^L)*N*N) . since BFS = O(N*N)

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

        It's not, BFS is O(N) in the worst case. (It's actually O(V+E), V being the number of vertices and E the number of edges).

        Just think about it like that: since you mark the nodes as visited (and don't visit them again after that), the worst thing that can happen is when you have to visit every node and edge. But still, you do that only once for each of them, so the algorithm is of linear complexity.

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

          hello, but N = n*n and E = 4*n*n , n = 100 (size of grid) so,is a O((2^L)*N) N = 100*100

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

            Yep, mixed the N = number of nodes with the N from the problem in my explanations. Thanks for pointing that, I've edited my answer to avoid confusion.

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

              ok. thank you . I have already fixed the error in my code :)!

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

How to solve Grandpa Pepe's Pizza problem? any ideas?