_jte_'s blog

By _jte_, 8 years ago, In Russian,

Немного отойду от традиции и создам немного неоффтопную тему. Наверняка, здесь есть много спортивных программистов,которые интересуются теорией чисел и теорией сложности.

Специально для них (и для всех остальных желающих) хочу предложить следующую задачу:

Пускай есть циклическая группа порядка q. Существуют два алгоритма: первый из них это некий Algo1, который работает следующим образом: , 1 ≤ a, b ≤ q. Сторонним наблюдателям, таким как мы с вами, неизвестны ни a, ни b, ни g, ни q. Просто они формально есть, и мы знаем, что алгоритм работает таким образом.
Второй из них -  это некий Algo2, который работает следующим образом: , 1 ≤ a ≤ q.
Собственно вопрос:  необходимо доказать их эквивалентность в смысле сложности ( ну или говоря другими словами, показать полиномиальную сводимость друг к другу).

UPD. Для некого упрощения задачи, будем считать следующее - данная группа    задает некоторую подгруппу мультипликативной группы поля , причем ее порядок q  пусть будет пока нечетным.
Под эквивалетностью работы понимается следующее:
, многочлены, такие что .

Read more »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By _jte_, 8 years ago, translation, In English,

Hi all, 


Today we would like to invite you to take part in round #86. Round is prepared by Andrew Malevich (aka Kenny_HORROR) and me, Taras Brzezinsky. We are students of Belarusian State University. We would like to thank  MikeMirzayanov ,  it4.kp , RAD , Gerald и Fefer_Ivan for helping and advice in preparing round and  Delinur for translation.

While participating, you will get known with boy Peter and remember some of his school days to help him to solve some problems

The points for the problems in Div 1 & 2 will be: 500-1000-1500-2000-2500.

New service "Virtual contest" will be unavailable during the round due to possible instability.

Good luck to everyone!

UPD

The contest is finished, ratings are updated. 
Congrats to winners:
DIV1:
2) KADR
3) yaro
5) Egor

DIV2: 
4) lxn

Editorial is currently available, the whole problem set analysis will be added in few hours.

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By _jte_, 8 years ago, In English,

While trying to solve some tasks from previous round, I've noticed that system testing queue is formed of a big amount of submissions that are still waiting for the system verdict. This happens for the second time in last 3 days. Is it related to some technical works from administration or this is just a bug? 

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By _jte_, 8 years ago, In Russian,

В блоге http://codeforces.ru/blog/entry/2250 еще пару часов назад были мои соображения по поводу решения предложенной задачи. В данный момент все комментарии исчезли, но значения числа комментариев остались прежними. В чем причина данного факта?

Read more »

Tags bug
 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it