Edvard's blog

Educational Codeforces Round 5
By Edvard, history, 9 years ago, translation, In English

Hi, Codeforces!

Happy New Year! Holidays and 2015 year have passed and year 2016 is ahead. I wish you good luck in programming competitions and achieving all of your goals this year.

Educational Codeforces Round 5 will take place on 11 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.

<A year has passed, but paragraph remains unchanged.>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

</A year has passed, but paragraph remains unchanged.>

Thanks a lot to Grigory Reznikow vintage_Vlad_Makeev who prepared a good problem (the problem F in ER 5). You can send to me some ideas of problems or maybe already prepared problems that you can't use in rounds or official competitions.

As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov for helping to invent the problems. Also thanks in advance to Maria Belova Delinur who will check English statements.

I think the problems is not difficult (except maybe for problem F). I hope you will enjoy the problems and solve all of them!

Good luck and have fun!

UPD 1: Coding phase is finished. You can hack other solutions for 24 hours.

UPD 2: The editorial is ready.

UPD 3: During the phase of hacks we found the following: the same solutions on Python2 and Python3 works differently on different large tests. For example, some of Python3 solutions works very slow on tests with only zeros, but Python2 works very slow on tests with nines. Some of solutions works in around one second so we decided to increase the time limit for the problem A to 2 seconds. All the solutions will be rejudged soon on the complete testset.

UPD 4: The round is over. All solutions will be rejudged soon on the complete testset (includes the hacks).

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

Comments Comments (60)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Nice problem E, thanks

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +19 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot. I used a for loop to do two things simultaneously. That was a bug.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 5   Vote: I like it +12 Vote: I do not like it

      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 :'(

      → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Can we have the editorials pls? :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -29 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    BigInteger and Python2 with input() get TL.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This round was supposed to be educative. So I guess it is okay to use already published but educative problems from where we can learn things. :)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Why should someone Enjoy when a problem is rejudged?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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+

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the idea behind E?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +6 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution for Problem C? http://mirror.codeforces.com/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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've posted generator with command line above.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi Edvard,

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Here is the simple generator on Java 7.

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that makes sense, I had no idea they had optimized the compiler so much here

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    as far as i know, u just have to write a program that prints the test case in the output stream and make sure to give a newline at the end

    → Reply
»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

UPD: hacked Thanks

→ Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Is it bug or feature?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Russian version of the site says that it's feature. Didn't managed to find analogous information in English one.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Wow!

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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)
→ Reply