|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Smallest possible automaton | Yury_Semenov | 1999. Секретный модуль | 14 фев 2024 16:19 | 1 | My solution produces an automaton with 2n^2 + n states, but what is the smallest possible size? Is it still ~n^2?
Edited by author 14.02.2024 16:19 | | Yes Accepted 0.078s | Shen Yang | 1999. Секретный модуль | 14 фев 2024 16:16 | 10 | worked at least two months.... I think it is a hard problem,harder than some rating>1e4 problems... How did you get the skill to solve such a hard problems?
I know generic patterns to effective skill training
Interested in particular case
Edited by author 08.11.2017 21:17 Just stop solving easy problems,and trying harder one.. I start solving hard problems since year 2010 practicing at http://poj.org solving AC<100 problems and at year 2013 I start solving topcoder Div I 1000pts.. later I found codeforces and start solve fewest AC problems.. There are also some Chinese oj hardest problems is very hard such like http://www.lydsy.com/JudgeOnline/ http://uoj.ac/ Yeah, solving hard is very helpful, I felt it
At some point I noticed that I am just not able to solve some harder problem
Because it takes very much time to solve
So even if trying whole day then cannot solve
Maybe whole week is enough
But very rarely have an opportunity to solve a problem the whole week
Typical have only three hours per day
But it's at cost of sacrificing important things
So I feel like I cannot improve further Yeah, solving hard is very helpful, I felt it
At some point I noticed that I am just not able to solve some harder problem
Because it takes very much time to solve
So even if trying whole day then cannot solve
Maybe whole week is enough
But very rarely have an opportunity to solve a problem the whole week
Typical have only three hours per day
But it's at cost of sacrificing important things
So I feel like I cannot improve further you can choose some easier than hardest problems but harder than medium problems if you don't have enough time to practice On spoj.com I have lot of tasks in my TODO list... Why do you consider it a hard problem? It felt quite straightforward to me Timus has very few constructive problems (at least with difficulty >= 2000), so this problem may seem hard compared to others if constructive problems are not your strong point | | How to test | Yury_Semenov | 1999. Секретный модуль | 14 фев 2024 16:13 | 1 | Bruteforce all short numbers (i. e. length <= 3) and feed them to both input and output automata, then compare. Here are some useful tests:
1
1
1
1 1 1 1 1 1 1 1 1 1
1
3
0 1 0
1 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3
8
3
0 1 0
1 3 2 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 |
|
|
|
