aajjbb's blog

Brazil ACM-ICPC Sub Regional 2014/2015
By aajjbb, 10 years ago, In English

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

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

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

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

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

what can I do sometimes?

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

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

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

What time will the contest start?

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

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

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

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.

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

    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

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

      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.

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

        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.

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

          :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.

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

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

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

        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.

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

          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

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

            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.

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

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

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

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

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

    Try everything! Translate the olives to have the first starting at 0. Let's say the size of the pizza is X=C/N. Fix the start of the first slice at point -X and check if the solution is correct, then try with -X+1, -X+2, ... until 0, where things are repeated again and you stop (the first slice is now the second one..). You will try C/N times and check if the N olives fit, this yields a runtime of O(C/N*N) = O(C).

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

    Also, if it helps, the tricky test case is when you have 2 olives right next to each other in the beginning.

    Let's say, you have 3 slices on a pizza with size 12 and olives on 1, 2, 8. This is possible. (This was the type of test case that many people that asked me about it after the contest was failing to solve).

    → Reply