Single Round Match 637

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

Автор chrome, 11 лет назад, По-русски

Сегодня состоится Single Round Match 637 в 19:00 по Московскому времени.

Давайте обсудим задачи после контеста.

srm, single round match, topcoder

chrome
11 лет назад
52

Комментарии (52)

Написать комментарий?

ErzhaNN

11 лет назад, скрыть # |

Спасибо, что ты предупреждаешь когда будет Topcoder.

→ Ответить

zeliboba

11 лет назад, скрыть # |

+16

Кто-нибудь еще сталкивался сегодня с тем, что не получается залогиниться в арену, пишет "Your login request timed out"

→ Ответить

SmartCoder

11 лет назад, скрыть # ^ |

+26

тоже самое

→ Ответить

Edvard

11 лет назад, скрыть # ^ |

И у меня. Причем на arena.topcoder.com то же самое

→ Ответить

ifsmirnov

11 лет назад, скрыть # ^ |

Пару часов назад все было нормально, сейчас тоже не заходит. ContestAppletProd.jnlp перекачал, не помогло.

→ Ответить

NSV

11 лет назад, скрыть # ^ |

+11

У меня ещё кроме "Your login request timed out" появляется "Your JRE does not support AES-128, login not allowed". Обновил JRE, перекачал Applet, обновил профиль на TC, ничего не помогает... :)

→ Ответить

zeliboba

11 лет назад, скрыть # ^ |

Похоже проблему решили, я сейчас смог залогиниться.

→ Ответить

beatoriche

11 лет назад, скрыть # ^ |

-29

Typical Java

→ Ответить

StoneCold_

11 лет назад, скрыть # |

On clicking on connect with all variations ranging from direct to Http tunnel A and B my Topcoder arena displays a message saying "A connection could not be established" . How do I fix it ?

→ Ответить

Totktonada

11 лет назад, скрыть # |

А хоть кому-то вообще удалось залогиниться?

→ Ответить

l1n4r

11 лет назад, скрыть # |

тоже не могу залогиниться... вроде несколько SRM-ов назад была возможность логиниться в арену и отправлять решения через сайт?

→ Ответить

I_love_tigersugar

11 лет назад, скрыть # |

← Rev. 2 →

+20

I can't login to the Applet Arena :( It said "Your JRE does not support AES-128". What should I do? My OS is Ubuntu 14.04

→ Ответить

SmartCoder

11 лет назад, скрыть # ^ |

I also have the same problem hope we get a reply soon

→ Ответить

Mukit09

11 лет назад, скрыть # ^ |

I also faced same problem. Then I cleared the java cache and downloaded the arena again. This has worked for me. :)

→ Ответить

SmartCoder

11 лет назад, скрыть # ^ |

no this is not the reason it was a common problem but fixed now

→ Ответить

Madiyar

11 лет назад, скрыть # ^ |

← Rev. 3 →

Seems like everything is working now. At least for me :). Registered successfully.

→ Ответить

CurbStomp

11 лет назад, скрыть # |

← Rev. 2 →

Configure Java >> View >> Remove Topcoder arena application >> re-download and run arena

→ Ответить

xpertcoder

11 лет назад, скрыть # ^ |

That worked for me.. Thanks :)

→ Ответить

keyvankhademi

11 лет назад, скрыть # |

-8

i can not run java applet of TC in ubuntu can some one help please?

→ Ответить

SlavaSSU

11 лет назад, скрыть # |

← Rev. 2 →

div2. 1000 — min-cost-flow?

UPD:: Yes, it is.

→ Ответить

NotImplemented

11 лет назад, скрыть # ^ |

Just find shortest eight-connected path from left side to right side.

→ Ответить

Xellos

11 лет назад, скрыть # |

+62

500pointer: 335C - More Reclamation :D

→ Ответить

IWillBeRed

11 лет назад, скрыть # ^ |

so, round on topcoder will be unrated?))

→ Ответить

NSV

11 лет назад, скрыть # ^ |

-6

It seems if replace columns ".." by 0, ".#" by 1 and "#." by 2 then it is:
http://acm.sgu.ru/problem.php?contest=0&problem=328

→ Ответить

PraveenDhinwa

11 лет назад, скрыть # ^ |

No, it is not that. In our case 1 and 2 should not be adjacent while in the sgu problem it can happen.

→ Ответить

NSV

11 лет назад, скрыть # ^ |

-8

How? :)

"1 — black, 2 — white"
"It's not allowed to color two adjacent vertices with the same color"

→ Ответить

I_love_tigersugar

11 лет назад, скрыть # ^ |

+14

But no one passed system tests :(

→ Ответить

Xellos

11 лет назад, скрыть # ^ |

-54

Yeah, I wonder wth happened.

→ Ответить

bktl4ever

11 лет назад, скрыть # ^ |

у xellos'a за первый коммент +60 а за второй -46 *_*

→ Ответить

hiukim

11 лет назад, скрыть # ^ |

-8

wrong tests?

→ Ответить

Madiyar

11 лет назад, скрыть # ^ |

← Rev. 3 →

length of board == 1, :(. System test failed.

→ Ответить

pedromnasc

11 лет назад, скрыть # ^ |

Can i use Sprague–Grundy theorem? Isn't it only applicable with normal play convention?? In this case the person who does not have a move wins. Am i wrong?

→ Ответить

--Pavel--

11 лет назад, скрыть # ^ |

Yes, you could use it here.

One can reformulate the game as follows: a move is valid iff it does not block the last left-to-right path. So the player who has not a move lose.

→ Ответить

pedromnasc

11 лет назад, скрыть # ^ |

Thanks! Now i understood :)

→ Ответить

PraveenDhinwa

11 лет назад, скрыть # ^ |

Can anybody please explain me better than O(n^3) solution? I read the editorial of 335C problem which has a O(n^3) approach.

→ Ответить

fruwajacybyk

11 лет назад, скрыть # ^ |

+19

I had an O(n) solution based on Sprague-Grandy Theorem.

We split our rectangle into smaller rectangles as follows: If we have a column with 'x' then we divide rectangle in this column (the edge column is in both left and right rectangle). for example

..x..xx..
x.......x

is splited into

..x — x..x — xx — x..
x.. — .... — .. — ..x

Now. It's easy to see that our game is equivalent to the sum of games on smaller rectangles. There are three types of rectangles.

Type A:

x....
.....

Type B:

x...x
.....

Type C:

x....
....x

One can prove by induction that nimber of A(n) = (n-1), nimber of B(n) = n%2 and nimber of C(n) = 1-n%2. [n is the width of rectangle]. So we just have to xor those numbers and we are done. There is one other case when there is no 'x' on the initial board. But in that case first player wins when n is odd and lose when n is even. (symmetry strategy).

→ Ответить

PraveenDhinwa

11 лет назад, скрыть # ^ |

Very nice explanation !! Thank you so much !!

→ Ответить

blazerer

11 лет назад, скрыть # |

Эммм.. Все 500 упали?

→ Ответить

IWillBeRed

11 лет назад, скрыть # |

а что значит, цвета, которыми написано passed system test?

→ Ответить

blazerer

11 лет назад, скрыть # ^ |

+11

Язык, на котором сдали

→ Ответить

temak

11 лет назад, скрыть # |

← Rev. 4 →

deleted

→ Ответить

deinier

11 лет назад, скрыть # |

I had problems with CodeProcessor plugin during contest. I had to debug by myself. Is there any problem with this plugin or is is a problem with my Java environment?

Instantiation error window says: Could not instantiate the editor CodeProcessor (see the java console for details). Switching to 'Standard' editor instead

→ Ответить

IWillBeRed

11 лет назад, скрыть # ^ |

I haven't any problems with it

→ Ответить

azukun

11 лет назад, скрыть # |

← Rev. 2 →

Div1 250 is a perfect problem to demonstrate .NET LINQ:

public double calc(int[] a, int[] b)
{
    var sa = new SortedSet<int>(a);
    double ans = 0;
    foreach (int bb in b.Where(bb => bb != -1))
    {
        int x = sa.FirstOrDefault(aa => aa > bb);
        if (x == 0)
            x = sa.Min;
        else
            ans++;
        sa.Remove(x);
    }
    if (sa.Count > 0)
        ans += 1.0 * Enumerable.Range(1, a.Length * 2).Except(a).Except(b).Sum(
            bb => sa.Count(aa => aa > bb)) / sa.Count;
    return ans;
}

I don't know Python, but I bet code would be even shorter.

→ Ответить

bktl4ever

11 лет назад, скрыть # ^ |

-33

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

lol.

→ Ответить

xennygrimmato

11 лет назад, скрыть # |

Can someone explain their solution for Div2 1000?

→ Ответить

azukun

11 лет назад, скрыть # ^ |

Snuke wins iff there is an 8-connected path of red cells from first column to the last column.

Build an oriented weighted graph, where each vertex correspond to a region from the board and there is an edge U->V with weight W if regions U and V are adjacent and region V has W cells. Add two more vertices source and target, source has edges to all regions having a cell in the first column with corresponding weight and all regions having a cell in the last column have edge to target with zero weight. Answer is the shortest distance from source to target.

→ Ответить

bktl4ever

11 лет назад, скрыть # ^ |

-25

ффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффффф

LOL

→ Ответить

bktl4ever

11 лет назад, скрыть # ^ |

-44

Are you LOL (=

→ Ответить

nilmish

11 лет назад, скрыть # ^ |

Why the shortest distance will give the optimal answer ? I am not able to understand. Can you please explain ?

→ Ответить

azukun

11 лет назад, скрыть # ^ |

Any simple path in the graph corresponds to a set of 8-connected regions in the grid and length of this path corresponds to the total number of cells in these regions. We want to find a set of connected regions which spans from first column to the last with minimal total number of cells, this is equivalent to finding a shortest distance from source to target in the graph.

→ Ответить