Recent actions

tkhkhkhkhkhkhkkhkh :|

-19

Is it not rated!

+20

Okay, CF on a hat-trick.

Created or updated the text

They have a bigger place for the next event. This Media-TIC building is very cool just google some pictures.

27978133 in this on 14th test case this problem shown problem : 417A

0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 Output NO Answer NO Checker Log wrong output format Output file not found: "output.fd0138e687.txt"

Can anyone suggest Solution

Isn't the space a bit too cramped? Hygiene might be a concern here. I hope they have more space for the next event, as there might be more people joining.

Also, what would be the differences between activities for students and coaches? For example, I can be either one although I am no longer eligible for ACM-ICPC.

I've contacted Harbour Space university, and they told me that yes, already graduated students can participate.

P.S. I wonder why this question was down-voted so much...

I think when we pushdown lazy tag it will expand more nodes so not just 64 nodes per update ,I guess

It's not a problem to make a couple of somewhat hard testcases of 1 test and place it right after samples...

Does everyone really hate it that much?

Because everyone hates multitest? You don't feel progress while fixing bugs and yet still getting WA2.

Great point! Why didn't we even consider it previously? Thanks, next round will definitely include multitest in problems B or C then.

+29

Use multitests

+5

Would you please update the Python2 version for the judging system?

This submission is said to be runtime error for python 2.7.3 while it works perfectly on my macbook with python 2.7.11.

http://codeforces.com/contest/817/submission/27881187

I'm not sure. As far as I can guess from usual rounds, ~30 tests for task with ~20 submits per minute is about the limit (considering submissions for all problems, not only this one).

Though it's hard to determine submissions rate before the contest. Adding more tests is always risky.

I suppose that we can try pushing this limit a bit by rearranging tests. I don't think that A can have more tests than it currently does but for B it's possible, I think. We will try to increase this number in next round.

Server load is definitely a concern. Do you know how bad it is in practice? May be we can afford more tests from B onward?

Can anyone explain me D&C solution for D? Because solution with stacks looks awful. I was thinking D&C on contest but couldnt solve it. Edit: got it. This solution helped me: http://codeforces.com/contest/817/submission/27832753

+23

Well, most of the hacks are made on easier problems. We can't add too many tests for them as it can lead to big server load. I won't deny that we don't try that hard to make tests as strong as possible but it isn't easy to cover all the cases with 10-15 tests.

There is just about couple of dozens successful hacks for D-F. I suppose that is fine, isn't it?

+2

Which problem was the tricky one?

+23

There is just too few tests for such tricky problems. Authors often use Educational Rounds as an excuse to be a bit lazy.

As usual :D

214 successful hacks!! Great!

I am so stupid. Thanks!

if(x != y and x != z) should be if (x != y and y != z)

I have used long long but still someone has hacked mine. code

Damn it! I have gone rusty.

Your logic works, but the result of k1 choose 3 doesn't fit in an int type, you should use long long int.

overflow.(btw, you declared n as long long and answer as int lol)

For B. Makes And The Product I don't know why my logic won't work

27820072

Basically I am counting the frequencies of smallest 3 distinct elements. For example 1 1 1 2 2 3 3 3 3

So the frequency is 1 -> 3, 2-> 2, 3->4 Call them k1,k2,k3 for smallest numbers a1,a2,a3

If k1>=3, it means the constituents of my minimum product all come from a1...So it is k1 choose 3

else if k1==2, then i just choose one of a2, which gives k2 ways.

else if k1==1 and k2>=2, then number of ways is k2 choose 2

else if k1==1 and k2==1, then i have to choose one a3, k3 choose 1 way of doing that.

+14

They are :c We really try to balance out problemsets but everytime it ends up with lots of ds problems.

I guess that it is actually fine in context of ERs because education in competitive programming is mostly about learning algos and data structures. Still somehow I am not pleased with the quality of contests...

It seems like that several past educational rounds are full of data structure problems XD

but also number of moves in x and y-axis can't be given by (x2 — x1) / x, (y2 — y1) / y because in 0 0 0 6 and x=2,y=3,no of moves in x axis is not(0-0)/2 .

Plus you need to check ((x2 — x1) / x + (y2 — y1) / y ) % 2 == 0 because there are no rules that move only x or y.

-8

Why my MEX queries does not work? Here's my code:

Solution

Can anyone provide the expected prior knowledge or maybe a range of the CF rating for the participants for each of the Divs? (Mainly interested in Div A myself)

Maybe the ones who attended last year's could also give us an insight or maybe a list of the topics covered :)

I am not getting problem A ,I mean why does not (x2-x1)%x==0 and (y2-y1)%y==0 work?Please explain.

+3

This was another great educational round from your part, I liked the problems a lot, keep up the good work.

okay, thanks!

+30

What about this one?

The editorial is published.

Created or updated the text

That's weird. I didn't try this hack because it worked less than <1.5 seconds using custom invocation (and even a little bit less locally with actual input reading/printing the answer).

I just took K = 50000.

That's exactly what I did.

Code

Cool. What's the idea of your test case? I tried to do something like adding different numbers K times and than making N — K queries (choosing K to maximize the run time), but it didn't work.

What test did you use? I thought about adding 50000 numbers than query 50000 times.

+65

Hacked.

Thanks!

Constraints in the problem E are so good that an O(Q^2) solution gets AC (it's not that the tests are weak: I can't make it run for more than ~1.5 seconds).

Was it intended?

+9

Read this tutorial to learn how to solve similar problems involving XOR using trie.

In this problem, maintain a trie in which numbers are inserted/removed in the decreasing order of bits in their binary representation. Now, for the query part, just traverse along the path specified by P and consider all cases in which you can get XOR < L.
eg. if next bit of P is 0 and next bit of L is 1, you can add all the numbers along the 0-edge to the answer and then move along the 1-edge (because for all numbers inserted in subtree of 0-edge, their XOR with P will be < L).

You can see all the cases in my code. Code

brute force is enough for C. Dont worry!!

The basic idea is for each i find Nmx[i] — the number of subarrays that will have a[i] number as maximum. Then do final_answer += Nmx[i] * a[i]. Similarly find Nmn[i] — number of subarrays in which a[i] will be the minimum number, and do final_answer -= Nmn[i] * a[i].

Nmx can be found in O(N) time. To find Nmx[i], you have to find Rmx[i] and Lmx[i] such that a[i] is maximum among all numbers in the segment [Lmx[i], Rmx[i]]. Rmx and Lmx arrays can be obtained with a forward sweep and a reverse sweep of the original array.

Similarly find Nmn array.

+12

For each element, let the number of subarrays in which it is the min be cnt_min[i] and the number of subarrays in which it is the max be cnt_max[i]. Answer is sum of arr[i]*(cnt_max[i]-cnt_min[i]).

To find cnt_max[i], for each index i, find the closest indices to its left and right such that value there is > arr[i]. This can be done in cumulative O(n) time using stack. Similar for cnt_min[i].
Take care of duplicate values.

Code

+5

here you go.

How to solve E? I could feel the use of tries but I couldn't come up with a good idea.

Yeah I got AC for now with something that looks like nlog^2n

How to solve D with O(N) complexity?

All numbers from s+9*18+1 to n are really big. So you can check numbers from s to s+9*18 and add max(0, n — s+9*18)

Can't wait until tomorrow to see the verdict. Please try to hack my C. I haven't used binary search or dp. code

Why i cant double click on submissions to hack it???

Nice :) thanks

Maybe, At least NlogN solution can pass pretest

I got AC with NlogN.

Click

+10

can we get AC with a NlogN solution in problem D ?

In C

n=10 s=9 ans=1 n=11 s=9 ans=2 . . n=19 s=9 ans=10 .. .. .. .. n=100 s=99 ans=1 . n=101 s=99 ans=2 .. .. so on

Sparse Segment Tree gives MLE on test 15 :( But shouldn't that pass the ML? It creates ~ 64 nodes per update. Each node has one long long and one short.

+5

I think we can compress the value of L and R and then build a segment tree with the new value (1 — 200000) and then use lazy-constructed segment tree as you said.

+2
+5

It can be proved that if a > b then a — sum_of_digits(a) >= b — sum_of_digits(b) so we can do binary search to find the smallest n that n — sum_of_digits(n) >= s

How solve D? :'v

+16

the answer is always l[i] or r[i] + 1 for some i , so just coordinate compress these points and then use normal segtree.

+7

the sum of the digits can't be large, so there's not many numbers x such that the check x - digitsum(x) >  = s is interesting. Check them all and add the rest in O(1), I checked only the interval [s..min(s+200,n)].

Any idea for D? I thought something on basis of RMQ and adding one element at a time to the array. But it is TLE easily.

C was a binary search :)

+3

How to solve F and C?

+3

I think problem F could be solved using segment tree if the interval was smaller... Can it be solved using a lazy-constructed segment tree? (we create nodes as we need them)

Thanks! :)

Large amount of hacks on A and B is coming...

+8

Are pretests too weak? I am submitting crap and they all are getting "accepted" as of now.

+13

too

+10

too

+3

same here

+12

too

+54

Me too! Don't worry. Round will be unrated. xD

-8

Mine also >-<

+1

What is Judgement Failed?

+16

too

+16

too

+17

too

+22

too

+8

Of course. The round won't be delayed but the solutions will be failed to judge.

+22

Judgement failed, too >:'(

+64

Judgement failed??

+26

Hey, it's a tradition for usual rounds but not for ERs! Previous 5 rounds started at the time they were scheduled.

Though I really don't like current condition of servers too.

The contest will surely delay, it is tradition.

-12

servers are getting really slow. Hope the contest won't be delayed

Hi! Looks awesome! Is there a point to attending such an event to get better at competitive programming in general? For example to participate in Google Code Jam or FB Hackercup?

What is the expected level of knowledge required?

Yep!

-6

It says in the blog, and I quote: "The round will be unrated for all users and will be held on extented ACM ICPC rules."

-59

Today is Champions Trophy Semifinal INDIA vs BANGLADESH ....Timing issue