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

Автор Edvard, история, 9 лет назад, По-русски

Привет, Codeforces!

Поздравляю вас с наступившим новым годом! Позади остались праздники и 2015-й год, а впереди 2016-й. Желаю вам достижения всех поставленных целей и конечно удачных выступлений на соревнованиях по программированию.

11 января 2015 года в 18:00 MSK состоится пятый учебный раунд Educational Codeforces Round 5 для участников из первого и второго дивизионов.

<Год прошёл два абзаца остались>

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

</Год прошёл два абзаца остались>

Большое спасибо Григорию Резникову vintage_Vlad_Makeev, который предложил и подготовил хорошую задачу (она будет под буквой F). Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

Подготовкой задач как всегда занимался я (Эдвард Давтян). Благодарю MikeMirzayanov мы вместе придумывали задачи (в этот раз по телефону). Также заранее благодарю Машу Белову Delinur, которая скоро вычитает английские тексты условий.

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

Good luck and have fun!

UPD 1: Первая фаза соревнования закончена. Открыта фаза взломов.

UPD 2: Разбор задач на русском языке готов.

UPD 3: На этапе открытых взломов был обнаружен следующий спецэффект: решения на языках Python2 и Python3 имеют значительную разницу во времени выполнения в разных максимальных тестах. Например, решение на Python3 работает очень медленно на тесте из всех нулей, а на Python2 на тесте из всех девяток. Некоторые решения работают чуть больше или чуть меньше секунды, поэтому было принято решение поднять ограничение по времени в задаче А до двух секунд. Вскоре закончится фаза открытых взломов и все решения будут перетестированы.

UPD 4: Соревнование завершено. Вскоре все решения будут перетестированы на полном наборе тестов, включающем в себя взломы.

  • Проголосовать: нравится
  • +213
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Каждый раз проще чем предыдущий :)

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

Due to "some Apple magic" I noticed such a letter in inbox instead of normal one...

The first idea was that CF made The First Holy Round For Hackers, but it's just Educational :D

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Э-эх, пропало волшебство(

»
9 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Yes!New season,new beginning!With our passion unchanged

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

yes!New season,new beginning!With our passion unchanged!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't see any way to withdraw my registration from this round. Is it because the round is unrated?

  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +4 Проголосовать: не нравится

    It's no problem if you register and don't participate.So if you want to withdraw your registration from this round, click on the number of the registered participants for the contest, click on friends and now you can withdraw your registration from this round by click on the X.

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Ждём взломов. :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Though it is not particularly relevant to this round, I wanted to point out a rather tiny glitch with the website. It is cool that we see the local time of the contests in Contests page, and not having to check it on timeanddate. However, the live countdown in the rightmost column of the table named "Current or upcoming contests" is probably still based on Moscow time. It currently shows there is 4.49hrs until the registration is closed, and it appears it will hit 0 at 18.00(Moscow time) which is the starting time of the contest.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Correction: It apparently includes the contest time as well. My bad. You may ignore this comment.

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

we can not search a problem with the caregory name. Like if i search problems with category name dfs, then blog result shows us. is it possible to search problems with category?? This will be very helpful. Thanks

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Edvard (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Nice problem E, thanks

  • »
    »
    9 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +19 Проголосовать: не нравится

    Thanks. I'm sorry for the issue in this problem. My solution had overflow problem and I fixed it.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      I am getting TLE in E in algorithm. Can you help? http://codeforces.me/contest/616/submission/15301347

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        Actually your solution is . Use the following in mul(a, b):

        ll mul(ll a, ll b) {
            a %= mod, b %= mod;
            a *= b;
            a %= mod;
            if (a < 0) a += mod;
            return a;
        }
        

        UPD: I see that it's . My solution uses a lot of mod operations and works in 530ms. So I think 2s TL should be sufficient.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится +12 Проголосовать: не нравится

      when I read problem E I recognized it to be a general case of a which is equal to ... I tried to follow that line and arrived at

      writing it as a convolution equation

      leading to an solution unfortunately in the mist of my triumph I didn't notice that we need to print % 1e9 + 7 or the possibility of overflow until the end of the contest ,poor me :'(

»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Can we have the editorials pls? :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is hacking time after contest with duration about 24 hours, only then we will have editorial

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm working on it. I've about finished the Russian version.

»
9 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

First problem was too easy for those who use Java, Python or have a BigInt class template in C++.
Third problem was a duplicate from USACO contest.
Fifth one's solution appears first when you google "Sigma(n mod i)"
Good thing this round is unrated.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

На Java у многих не проходила первая задача? Просто для интереса пробовал на java, потом забил и сдал на C++

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    При использовании BigInteger решение на Java не должно проходить. Если же всё делать в строках, то никаких проблем нет. У меня было даже два решения на Python2 и Python3, которые работают 30ms.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Problem 616C - The Labyrinth why my solution 15292451 gets WA?!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Looks like A has quite a lot hacks. Will there be some statistics after finishing the hacking phase?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    After coding phase the number of correct solutions is greater than 1700. We will see how many solution will pass all tests tomorrow.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    there's already been close to 400 hacks . Most of them TLE I guess

»
9 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Why should someone Enjoy when a problem is rejudged?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How come the input file for the hacks are only up to some 200+ KB? I tried an array with 5*10^5 integers, and it led to 3MB+

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What is the idea behind E?

  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

    can also be written as a - (a / b) * b (Integer Division)
    now a / b only has distinct values ranging from [1 to and also all values of the form a / i where . Just use this fact. Code

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am confused from where can we conclude about sqrt(a) distinct values?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        a/b is either less than sqrt(a) (if b is greater than sqrt(a), there are O(sqrt(a)) distinct values) or greater than sqrt(a) (if b is less than sqrt(a) but since there are O(sqrt(a)) values for b, the same holds for a/b) which means there are O(sqrt(a))+O(sqrt(a))=O(sqrt(a)) distinct values for a/b :)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

At problem f I used suffix arrays with lcp precalculations,then just a stack and that's all. I still can't figure why I get wa on test 12.Is anybody who had the same problem? Can you help me fix this?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Edvard could i see the full data of test case #11 on problem 616C - The Labyrinth

It gives me WA and the Checker comment says that i wrong in the 1st line which i run this part in my machine and give the correct output!!!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's wrong with my solution for Problem C? http://codeforces.me/contest/616/submission/15297727

Moreover, at test case 11, where it says my code fails- Here, my answer matches with the jury's answer(at least the part which we can see), however, it doesn't match with expected value. Isn't it strange? The expected value does not match with jury's solution.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I've posted generator with command line above.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi Edvard,

      Please How can I write test generator with Java 7 ? Is there a format I should follow ?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You should only print your test to standard output (screen) considering the format of output from the problem statement. See my generator on C++. Of course you can't use testlib.h in Java, but you don't need it.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Here is the simple generator on Java 7.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

saw someone using i<strlen(str) in for loop and ran it in my machine. gets TLE but when I ran it here it runs ok . No idea what's going on :v

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Compiler Optimizations -O2 flag when you execute code here. Maybe you have not enabled it. strlen would be about O(n) complexity everytime you call it.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please what is the format for writing a Test generator for Java 7. The output file will be > 1mb. ?

»
9 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

I don't like a complicated C problem,but a easy d problem. :(

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

UPD: hacked Thanks

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Is it bug or feature?

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Почему показатели количества решивших задачу в меню раунда "задачи" и в его таблице "положение" различаются?

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I find so hard to read code (example http://pastebin.com/AdDQDtWy) with all these defines forn, sz, pb, etc why can't the code be just as is / simple with no defines

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

What am I getting wrong here? I get different output for N = M = 1e13 (it matches up to 1e8 or so)

from math import sqrt

def get_sum(x):
	return int(x*(x+1)/2)
def range_sum(l,r):
	return get_sum(r) &mdash; get_sum(l-1)

if __name__ == '__main__':
	# MOD = 1000000000 + 7
	MOD = 1
	mod = 1000000000 + 7
	MOD = mod
	N = int(input())
	M = int(input())
	# N = 10000000000000 
	# M = 10000000000000

	print(N)
	print(M)

	minMN = min(N, M)
	# lim = int(sqrt(minMN))
	lim = int(sqrt(N))
	# total = (M % MOD )*N % MOD
	total = M*N
	reduce = 0

	for i in range(1, lim):
		if i > minMN:
			break

		a_pair = int(N / i )
		b_pair = int(N / (i+1))

		if b_pair+1 <= minMN:
			this_range = range_sum(b_pair+1, min(a_pair, minMN))
			div = i
			# red = (this_range % MOD * div) % MOD
			red = int(this_range ) * div

			reduce += red
			# reduce %= MOD

		reduce += int(N/i)*i # % MOD
		# reduce %= MOD

	print("Reduce is " + str(reduce))

	lim_pair = int(N/lim)
	for i in range(lim, lim_pair+1):
		if i > minMN:
			break
		reduce += int(N/i) * i
		# reduce %= MOD

	print(total % MOD)
	# total %= MOD
	print("Total is " + str(total))
	print("Getting from " + str(lim) + " to " + str(lim_pair))
	print("Reduce is now " + str(reduce))

	ans = total - reduce
	print( (total % MOD) - (reduce % MOD) )
	print( ((total % MOD) - (reduce % MOD) ) % MOD)

	print(ans)
	print(ans % mod)