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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
how do you register in that contest?, or it does not need registration?
Anyone with an UVA account can take part in the contest.
thanks :)
what can I do sometimes?
You can ask questions that actually make sense, for example. Because this one doesn't.
What time will the contest start?
If it happens at the same time as the real contest, look here for your timezone:
http://www.timeanddate.com/worldclock/fixedtime.html?iso=20140913T14&p1=652&ah=5
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
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.
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):
Answer should be 20
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.
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.
: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.
hello respect to problem G , why is O((2^L)*N) ?? should not be O((2^L)*N*N) . since BFS = O(N*N)
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.
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
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.
ok. thank you . I have already fixed the error in my code :)!
How to solve Grandpa Pepe's Pizza problem? any ideas?
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).
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).
how do you solve Ecology problem?
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4660
.
thanks man
hola , ya resolvistes el problema??
no, lo implementare mas tarde, por que?
intentaba ver si tienes otra solucion diferente
la verdad, es que esa era la que tenia pensada, solo que dudaba implementarla y por eso pregunte