Single Round Match 637

→ Обратите внимание

До соревнования
Codeforces Round 986 (Div. 2)
05:25:16
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 986 (Div 2) - Solution Discussion

Shayan

До начала 07:30:16

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Single Round Match 637

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

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

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

srm, single round match, topcoder

chrome
10 лет назад
52

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

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

ErzhaNN

10 лет назад, # |

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

→ Ответить

zeliboba

10 лет назад, # |

+16

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

→ Ответить

Killever

10 лет назад, # ^ |

+26

тоже самое

→ Ответить

Edvard

10 лет назад, # ^ |

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

→ Ответить

ifsmirnov

10 лет назад, # ^ |

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

→ Ответить

NSV

10 лет назад, # ^ |

+11

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

→ Ответить

zeliboba

10 лет назад, # ^ |

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

→ Ответить

beatoriche

10 лет назад, # ^ |

-29

Typical Java

→ Ответить

StoneCold_

10 лет назад, # |

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

10 лет назад, # |

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

→ Ответить

l1n4r

10 лет назад, # |

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

→ Ответить

I_love_tigersugar

10 лет назад, # |

← 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

→ Ответить

Killever

10 лет назад, # ^ |

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

→ Ответить

Mukit09

10 лет назад, # ^ |

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

→ Ответить

Killever

10 лет назад, # ^ |

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

→ Ответить

Madiyar

10 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

CurbStomp

10 лет назад, # |

← Rev. 2 →

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

→ Ответить

xpertcoder

10 лет назад, # ^ |

That worked for me.. Thanks :)

→ Ответить

keyvankhademi

10 лет назад, # |

-8

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

→ Ответить

SlavaSSU

10 лет назад, # |

← Rev. 2 →

div2. 1000 — min-cost-flow?

UPD:: Yes, it is.

→ Ответить

NotImplemented

10 лет назад, # ^ |

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

→ Ответить

Xellos

10 лет назад, # |

+62

500pointer: 335C - More Reclamation :D

→ Ответить

IWillBeRed

10 лет назад, # ^ |

so, round on topcoder will be unrated?))

→ Ответить

NSV

10 лет назад, # ^ |

-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

10 лет назад, # ^ |

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

→ Ответить

NSV

10 лет назад, # ^ |

-8

How? :)

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

→ Ответить

I_love_tigersugar

10 лет назад, # ^ |

+14

But no one passed system tests :(

→ Ответить

Xellos

10 лет назад, # ^ |

-54

Yeah, I wonder wth happened.

→ Ответить

bktl4ever

10 лет назад, # ^ |

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

→ Ответить

hiukim

10 лет назад, # ^ |

-8

wrong tests?

→ Ответить

Madiyar

10 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

pedromnasc

10 лет назад, # ^ |

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

10 лет назад, # ^ |

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

10 лет назад, # ^ |

Thanks! Now i understood :)

→ Ответить

PraveenDhinwa

10 лет назад, # ^ |

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

10 лет назад, # ^ |

+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

10 лет назад, # ^ |

Very nice explanation !! Thank you so much !!

→ Ответить

blazerer

10 лет назад, # |

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

→ Ответить

IWillBeRed

10 лет назад, # |

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

→ Ответить

blazerer

10 лет назад, # ^ |

+11

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

→ Ответить

temak

10 лет назад, # |

← Rev. 4 →

deleted

→ Ответить

deinier

10 лет назад, # |

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

10 лет назад, # ^ |

I haven't any problems with it

→ Ответить

azukun

10 лет назад, # |

← 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

10 лет назад, # ^ |

-33

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

lol.

→ Ответить

xennygrimmato

10 лет назад, # |

Can someone explain their solution for Div2 1000?

→ Ответить

azukun

10 лет назад, # ^ |

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

10 лет назад, # ^ |

-25

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

LOL

→ Ответить

bktl4ever

10 лет назад, # ^ |

-44

Are you LOL (=

→ Ответить

nilmish

10 лет назад, # ^ |

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

→ Ответить

azukun

10 лет назад, # ^ |

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.

→ Ответить

nmsunny

10 лет назад, # ^ |

Got it. Thnx for the explanation :)

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 10.11.2024 13:09:44 (i1).

Десктопная версия, переключиться на мобильную.

При поддержке