Обсуждение @ 1741. Монстр общения @ Timus Online Judge

Matei Chirvasa Help with DP solution // Задача 1741. Монстр общения 26 мар 2022 22:15

Fyodor Menshikov wa3 [1] // Задача 1741. Монстр общения 2 ноя 2009 21:44

Gleb Hints // Задача 1741. Монстр общения 17 май 2018 19:34

Rocky.B Heeeh) Wa8 // Задача 1741. Монстр общения 17 дек 2016 20:13

Blackops Using Short path algo seems feasible [1] // Задача 1741. Монстр общения 10 сен 2016 10:49

Accelarator Why WA#12? // Задача 1741. Монстр общения 4 дек 2015 18:52

FvckHer W9 [1] // Задача 1741. Монстр общения 13 окт 2011 18:52

r1d1 WA#10 [3] // Задача 1741. Монстр общения 1 ноя 2009 16:42

YSYMYTH Could ADMIN show the TEST#8? [1] // Задача 1741. Монстр общения 19 дек 2011 10:47

kot WA#8 [1] // Задача 1741. Монстр общения 3 ноя 2009 04:03

evjava Why WA1? [1] // Задача 1741. Монстр общения 18 ноя 2009 00:11

Leonid (SLenik) Andrievskiy For WA#3 and Some hints how to solve the problem with O(n * log(n)) [3] // Задача 1741. Монстр общения 23 июл 2011 01:44

NickSergeev[MSU MindCraft] Бред! [5] // Задача 1741. Монстр общения 1 ноя 2009 15:05

Alexander Samal Why WA#8? [7] // Задача 1741. Монстр общения 2 ноя 2009 00:50

unlucky [Vologda SPU] Weak tests [20] // Задача 1741. Монстр общения 3 ноя 2009 15:34

Мy very crazy program passed 19 Tests and get TLE 20. I may be wrong, but I think, that the first 19 tests are weak. My program can't passed so many tests with bug in algorithm.
My be it is needed to check this tests and emulate EVERY possible and impossible situations.

Chmel_Tolstiy Re: Weak tests [19] // Задача 1741. Монстр общения 3 ноя 2009 15:50

Your solution didn't pass so tests are OK. Tests are weak if your wrong solution passes all of them.

unlucky [Vologda SPU] Re: Weak tests [18] // Задача 1741. Монстр общения 3 ноя 2009 17:24

I wrote bad solution and get AC at 19!!! tests.
I use DP and DFS.
It is very strange, that this bad solition passed so many tests...

Sevenk Re: Weak tests [17] // Задача 1741. Монстр общения 3 ноя 2009 19:09

Maybe the first 19 tests are some small tests that some programs go wrong at it.

unlucky [Vologda SPU] Re: Weak tests [16] // Задача 1741. Монстр общения 3 ноя 2009 20:35

It is very strange...

svr Re: Weak tests [15] // Задача 1741. Монстр общения 3 ноя 2009 21:23

1741 is median of contest.
Halph of problems are harder hailpf are simpler.
I am myself made 1741 from 1 submission.
But there is 1735:modelling optimal packing different subsets sum problem for which great Erdesh was able to give 500$

unlucky [Vologda SPU] Re: Weak tests [14] // Задача 1741. Монстр общения 3 ноя 2009 21:37

Finally AC by DP.
I had a good sleep 8)

Sandro (USU) Re: Weak tests [13] // Задача 1741. Монстр общения 3 ноя 2009 23:39

Why do you think that 19 is "many"? Some problems on Timus Online Judge have more than 200 tests. :)

unlucky [Vologda SPU] Re: Weak tests [12] // Задача 1741. Монстр общения 4 ноя 2009 02:05

Problem not in amount, but in qualitative.
My wrong solution must not passed so many and get TLE, because it must get WA early :)
That's all. Topic closed.

Alex Tolstov (Vologda STU) Re: Weak tests [11] // Задача 1741. Монстр общения 4 ноя 2009 14:52

You must get AC for this problem with the first attempt. It's very easy problem. =) You should not think about "weak" tests in this case)

unlucky [Vologda SPU] Re: Weak tests [10] // Задача 1741. Монстр общения 5 ноя 2009 23:29

Fyodor Menshikov created test, where my AC program failure =)

Samsonov Alex [USU] Re: Weak tests [7] // Задача 1741. Монстр общения 5 ноя 2009 23:49

We always encourage you to send good tests to us :)

unlucky [Vologda SPU] Re: Weak tests [6] // Задача 1741. Монстр общения 6 ноя 2009 17:52

Yep =)
Some times I create "not bad" heuristic solution.
I know, that it is not good, but some times only my coatch (not Timus) can create failure test after he sees the code :)

Crash_access_violation Re: Weak tests [5] // Задача 1741. Монстр общения 15 ноя 2009 14:36

Please said me I'm right?

cracked on cracked, pirated
licensed on licensed, cracked
pirated on licensed, cracked, pirated

thanks!

unlucky [Vologda SPU] Re: Weak tests [4] // Задача 1741. Монстр общения 16 ноя 2009 12:34

Program can't be cracked.
Update can be cracked.
If update is Licensed or Cracked,then program became Licensed.
If update is Cracked or Pirated,then program became Pirated.

Crash_access_violation Re: Weak tests [3] // Задача 1741. Монстр общения 17 ноя 2009 02:59

I correct my code, but I also got wa#8.
What is wrong in my idea?
1) sort by xi;
2) linear algo to find D[n][pirated] and D[n][licensed]
3) when write(min(D[n][pirated], D[n][licensed]))

or please give me some useful tests.

thanks!

Edited by author 17.11.2009 02:59

unlucky [Vologda SPU] Re: Weak tests [1] // Задача 1741. Монстр общения 17 ноя 2009 15:26

Crash_access_violation писал(a) 17 ноября 2009 02:59

I correct my code, but I also got wa#8.
What is wrong in my idea?
1) sort by xi;
2) linear algo to find D[n][pirated] and D[n][licensed]
3) when write(min(D[n][pirated], D[n][licensed]))

or please give me some useful tests.

thanks!

Edited by author 17.11.2009 02:59

My solution use DFS. I try to get answer not for last program, but for first. We have one "start point" and many "end points". Use recursion to get min cost of updating to every version of program.
Other only via email(only Russian)

Edited by author 17.11.2009 15:28

Alex Tolstov (Vologda STU) Re: Weak tests // Задача 1741. Монстр общения 18 ноя 2009 13:16

Oleg, use phrase "min cost" more carefully. =) Usually it means min cost max flow problem :))

Alex Tolstov (Vologda STU) Re: Weak tests // Задача 1741. Монстр общения 18 ноя 2009 13:18

how to solve problems from this contest:
http://vkontakte.ru/topic-6732013_21978466

Sandro (USU) Re: Weak tests [1] // Задача 1741. Монстр общения 22 ноя 2009 22:20

Test by Fyodor Menshikov was added to the test set.

unlucky [Vologda SPU] Re: Weak tests // Задача 1741. Монстр общения 23 ноя 2009 01:43

Sandro (USU) писал(a) 22 ноября 2009 22:20

Test by Fyodor Menshikov was added to the test set.

Yep =)
I'v got 2 WA, but last result is AC.
I think, only I got WA.
It's easy to break program, looking at it code =)

Edited by author 23.11.2009 18:40

liuexp CRACKED [9] // Задача 1741. Монстр общения 1 ноя 2009 16:03

1.can a cracked one installed on alicensed one?
2.can a licensed one installed ona cracked one if it has never been pirated before?

r1d1 Re: CRACKED [8] // Задача 1741. Монстр общения 1 ноя 2009 17:10

1.YES
2.YES

liuexp Re: CRACKED [7] // Задача 1741. Монстр общения 1 ноя 2009 19:05

But my shortest path algorithm still failed....
I first encode the vertice of pirated into 3*i
and the vertice of cracked into 3*i+1,
and the vertice of licensed into 3*i+2,
then construct the graph according to the input, and after that I use a DFS() to take away the edge that comes with a licensed one and is after a pirated one.
Finally I run the SPFA(), is there anything wrong?

I constructed several simple datas to test the DFS() AND SPFA(), it works all right.

r1d1 Re: CRACKED [5] // Задача 1741. Монстр общения 1 ноя 2009 19:49

hm... I use DP and all work

2rf [Perm School #9] Re: CRACKED [4] // Задача 1741. Монстр общения 1 ноя 2009 23:47

What is your DP solution? Obviously, we have weighted graph in this problem and we want to know shortest path from one vertex to another. So, it's Dijkstra algorithm, but I'm not sure if you can call it DP... Did you use some special algo?

Lebedev_Nicolay[Ivanovo SPU] Re: CRACKED [3] // Задача 1741. Монстр общения 2 ноя 2009 00:18

We need to find shortest path in DAG! So we need not Dijkstra, we need other algo. This algo very same with DP.

2rf [Perm School #9] Re: CRACKED [2] // Задача 1741. Монстр общения 2 ноя 2009 00:41

Oops, didn't see xi<yi in statement =) Anyway, I used Dijkstra and got AC.

Lebedev_Nicolay[Ivanovo SPU] Re: CRACKED [1] // Задача 1741. Монстр общения 2 ноя 2009 00:52

How did you use Dijkstra (N = 10000)?
Did you use heap or priority queue?

2rf [Perm School #9] Re: CRACKED // Задача 1741. Монстр общения 2 ноя 2009 01:39

O(N^2). It worked even though N=20000 actually(having cracked and licensed vertex for each version). Time was ~0.7 sec.

2rf [Perm School #9] Re: CRACKED // Задача 1741. Монстр общения 1 ноя 2009 21:52

liuexp писал(a) 1 ноября 2009 19:05

I first encode the vertice of pirated into 3*i
and the vertice of cracked into 3*i+1,
and the vertice of licensed into 3*i+2,

?? You can have only licensed or pirated vertices; not cracked!

And, btw, singular for "vertices" is "vertex" not "vertice".

Edited by author 01.11.2009 22:23

liuexp would it exceed int32? [1] // Задача 1741. Монстр общения 1 ноя 2009 15:35

Обсуждение задачи 1741. Монстр общения