HACKATHON COMING

8 years ago, # |

+40

It will be hard to concentrate on problems.

→ Reply

camypaper

8 years ago, # |

+19

As we know, competitive programming is moemoeSports! I'm looking forward to the CUTE image and clear problem statement!

→ Reply

farizazmip

8 years ago, # |

+37

Well, I think I am the only one that watched the entire series of Kiniro Mosaic just because it will be featured on this contest. God bless moe anime.

→ Reply

nuhu_ius

8 years ago, # |

I hope that problems statement very clear.

→ Reply

nima10khodaveisi

8 years ago, # ^ |

← Rev. 2 →

-7

I don't think so cause of pics and story !

→ Reply

Alhelal_01

8 years ago, # |

Short description will be helpful everybody.

→ Reply

GODOF_Shinobi

8 years ago, # |

Please I hope no 10 min delays.

→ Reply

babin

8 years ago, # |

← Rev. 2 →

+11

How about the "right before the round" scoring distribution ?

UPD: Fixed

→ Reply

C137

8 years ago, # |

Very unusual Scoring for div.2 :D

→ Reply

kingofbugs

8 years ago, # |

-23

i know what to comment to get upvotes!

→ Reply

all_out

8 years ago, # ^ |

-21

take some downvotes too :P

→ Reply

aneesh2312

8 years ago, # |

Hack page not loading..?

→ Reply

lashavi

8 years ago, # |

is there something wrong with codeforces. I have been trying to submit C for 20 minutes but I couldn't submit. Its like there's no response from codeforces site.

→ Reply

MahdiGheidi

8 years ago, # ^ |

Same happened to me but they fixed it

→ Reply

lashavi

8 years ago, # ^ |

Please fix it soon. I am unable submit yet.

→ Reply

Mr.Adnan

8 years ago, # ^ |

Go to your contest dashboard. Ask it to the "Ask a question" section below.

→ Reply

lashavi

8 years ago, # ^ |

thanks man. submitted only 2 minute before contest.

→ Reply

yassin_

8 years ago, # |

← Rev. 3 →

edit: nvm

→ Reply

RMSZ005

8 years ago, # |

-47

The comment removed because of Codeforces rules violation

→ Reply

kabirsahni8

8 years ago, # ^ |

-13

Same here,please reply!

→ Reply

8 years ago, # |

First time opened last problems, because of pics.

→ Reply

8 years ago, # |

+10

How to solve D?

→ Reply

8 years ago, # ^ |

+97

Write brute force solution.
Run brute force on all vectors (0,0,0, ... , 1, ... 0) of length k, to get weight of each individual element.
Recognize the pattern. Even vs. odd n makes a difference, and even vs odd $\text{[math]}$ also does, you're looking for patterns depending on modulo 4.
Verify against bruteforce.
Step (optional): Prove the correctness.
Step: Pray that you didn't miss anything.

→ Reply

Saimon_Saret

8 years ago, # ^ |

I recognized all patterns except n % 4 == 3. Could you please explain it?

→ Reply

Lixoskywalker

8 years ago, # ^ |

+18

If you have n % 4 == 3 and you don't know how to answer it, just apply one step and you have n % 4 == 2 and you know how to solve it.

→ Reply

pimenta

8 years ago, # ^ |

What you mean by apply one step?

→ Reply

tfg

8 years ago, # ^ |

If you could find the patterns for n % 2 then you could transform n % 2 == 1 into n % 2 == 0 by bruteforcing one step.

→ Reply

pimenta

8 years ago, # ^ |

Could you please improve the explanation? Thanks!

→ Reply

tfg

8 years ago, # ^ |

+11

My solution was simple: find the relation for when n is even. If it is odd, make 1 step for it to become even. Note through the drawing below the problem that the operations are still at the same order so you can apply what you found for n % 2 == 0.

If you had the relation for n % 2 == 1 you could start from n % 2 == 0 and apply the step 3 times, now the operation is the same as starting from n % 2 == 1 (it starts adding) and you can use the relation you have. Other than that kind of stuff, you need to note that each number will influence the answer independently and then do some bruteforce solution to find some pattern from inputs like 0 0 1 0 0 0 0, at least I think almost everyone did that.

This is straight from my code, it might be helpful to you (it's in portuguese and comb is a binomial coeficient):

// par -> j par = comb(n / 2 — 1, j / 2) // par -> j impar se n / 2 % 2 == 0 é negativo, se não é positivo // par -> j impar comb(n / 2 — 1, j / 2)

// impar -> transforma no par e resolve

→ Reply

8 years ago, # ^ |

+15

For odd indices the coefficients are $\text{[math]}$ .

Even indices are $\text{[math]}$ .

Maybe you can find one formula for both.

→ Reply

marcospaulo

8 years ago, # ^ |

← Rev. 9 →

+36

When you miss the case n=1 and you don't believe on correctness of your pattern

→ Reply

mnaeraxr

8 years ago, # ^ |

If you manage to recongize one pattern it is enough, since you can build the other in a brute way from the recognized pattern.

→ Reply

qkxwsm

8 years ago, # |

+37

How to solve Div1B :(

→ Reply

previc

8 years ago, # ^ |

I think to use binomial coefficients. (Pascal's triangle)

→ Reply

MiteshAgrawal

8 years ago, # |

Is Div1 — B solvable using matrix exponentiation? would also be interested to know other methods. TIA

→ Reply

8 years ago, # ^ |

← Rev. 2 →

What will be the transition function? The transition function will change depending on the level we're at. eg: from level 10 to 5 has a different transition function than 12 -> 6.

In short, according to my understanding, we can't. To use mat-exp we need a consistent transition function, that doesn't depend on level.

→ Reply

vsp4

8 years ago, # ^ |

← Rev. 2 →

+13

I passed pretests by finding pattern of the coefficients (Huh). There were 4 cases, (parity of n, parity of (n/2))

→ Reply

8 years ago, # ^ |

Wow! nice. I was looking for a similar pattern but didn't think it would depend on parity of n/2.

→ Reply

Single_Ready_To_Mingle

8 years ago, # |

Hack for Div 2 C ?

→ Reply

hell_hacker

8 years ago, # |

← Rev. 2 →

Hack for Div2 C?

→ Reply

noelnadal

8 years ago, # ^ |

← Rev. 4 →

+13

Typically, when n > m.

→ Reply

hell_hacker

8 years ago, # ^ |

Thanks My output was 5 and then all rows :/

→ Reply

Mr.Awesome

8 years ago, # ^ |

The answer is 5 row 1 row 2 row 3 row 4 row 5 right?

→ Reply

Len

8 years ago, # ^ |

No, answer is 3 because problem asks for minimal number of moves(I saw it only now).

→ Reply

Qumeric

8 years ago, # ^ |

Omg I missed it too. And most people in my room...

→ Reply

Mr.Awesome

8 years ago, # ^ |

I forgot about the min even though I checked both row and columns :'(

→ Reply

Mistra

8 years ago, # ^ |

I made the same mistake first but realized it just before the contest ended while testing my own solutions. Managed to resubmit just in time :D

→ Reply

mickeyandkaka

8 years ago, # ^ |

using the minimum number of moves

→ Reply

Mustang98

8 years ago, # ^ |

No: 3 col 1 col 2 col 3

→ Reply

8 years ago, # ^ |

+21

Is it the right answer?
3
col 1
col 2
col 3

→ Reply

noelnadal

8 years ago, # ^ |

Yes.

→ Reply

TShT

8 years ago, # ^ |

fuck :(

→ Reply

newCEA

8 years ago, # ^ |

← Rev. 2 →

I can not believe this... I knew this exception but accidentally typed n instead of m...

if(n<m) for(int i=0;i<**n**;i++) for(int p=0;p<dm;p++) printf("row %d\n",i+1);

else for(int j=0;j<**n**;j++) for(int p=0;p<dm;p++) printf("col %d\n",j+1);

→ Reply

8 years ago, # ^ |

← Rev. 3 →

Sometimes you need to start from columns not from rows... Consider a table:

010 010 010 010 010 010

My solution because of this was hacked... Bye bye rating :D

→ Reply

bhishma

8 years ago, # |

Div 2 C is from an old Cook-Off

→ Reply

8 years ago, # ^ |

You had an opportunity to solve it in 5 minutes =)

→ Reply

bhishma

8 years ago, # ^ |

I was making sure , that I dont mess up anything.

→ Reply

vivace1

8 years ago, # ^ |

Its easier than that . Here one matrix is always all zeroes . In the question you mentioned in your link, the other matrix is different and you need to make both matrices equal . Div 2C is an easier version of that .

→ Reply

8 years ago, # ^ |

Hmm, but can't we apply the same technique on both matrices and compare the residue matrix after all operations? If the residue is same, then they are same.

→ Reply

Ashishgup

8 years ago, # |

+18

That feeling when you screw up your rating because of one "if" condition in Div1 A :(

→ Reply

I_Love_Watermelon

8 years ago, # |

+24

The Art of the Covfefe

lmao

→ Reply

infomaniac

8 years ago, # |

div 2B please ?

→ Reply

rawr

8 years ago, # ^ |

← Rev. 2 →

I solved it with Segment Tree + BIT. For each given n range, update the range with segment tree. Then for each i from 1 to 200000, point query with segment tree checking whether it is >= k. If it is, then update point i in BIT with +1

Later, for each query, just do a range query with BIT.

P.S. I think it's pretty much overkill. Maybe others have much simpler idea.

→ Reply

dush1729

8 years ago, # ^ |

No need to use BIT/segment tree when all queries are after update.

Code

→ Reply

Mr.Adnan

8 years ago, # ^ |

Do you know partial sum?

for i [ 1, n ] arr[a]++; arr[b+1]--

then find the cum. sum in the arr[].

and then also do the cum sum in the array to find if the arr[i] is >= k.

then just ans is for query l to r cum[r]- cum[l-1]

→ Reply

vijayiota77

8 years ago, # ^ |

Something like this link

→ Reply

roberto_firmino

8 years ago, # |

← Rev. 2 →

Is there the case of the type :

2 1 1 1

(div 2 C)

in the pretests ?

→ Reply

StillFantasy

8 years ago, # ^ |

I don't think so. This is one of the hacking test.

→ Reply

newts

8 years ago, # |

HACKATHON COMING

→ Reply

xuanquang1999

8 years ago, # |

+24

How to solve D? Is it involved inclusion-exclusion principle?

→ Reply

8 years ago, # |

← Rev. 2 →

Div2B is very similar to this problem — http://www.spoj.com/problems/UPDATEIT/

→ Reply

8 years ago, # ^ |

I think they are pretty different.

→ Reply

vivace1

8 years ago, # ^ |

I used the exact strategy mentioned in the link above . I have done the above mentioned one.

→ Reply

deva2802

8 years ago, # |

Was D variation of pascal triangle or something? can anyone tell what was wrong with my code

→ Reply

Lixoskywalker

8 years ago, # ^ |

try this testcase: 1 1

→ Reply

deva2802

8 years ago, # ^ |

Ohh Crap! Thanks though :)

→ Reply

geniucos

8 years ago, # |

Can someone tell me what particular cases may occur in div1D? I've spent 30 minutes trying to find a bug and didn't find anything...WA on pretest 4. Has it happened to anyone else, too? If so, how did you fix it?

→ Reply

Vasiljko

8 years ago, # |

Solved C 3 minutes after ending...

→ Reply

KieranHorgan

8 years ago, # ^ |

Solved C 20 seconds after endings...

→ Reply

DmitryYutkin

8 years ago, # |

How to solve div2 B? -_-

→ Reply

Mr.Adnan

8 years ago, # ^ |

Do you know partial sum?

for i [ 1, n ] arr[a]++; arr[b+1]--

then find the cum. sum in the arr[].

and then also do the cum sum in the array to find if the arr[i] is >= k.

then just ans is for query l to r cum[r]- cum[l-1]

→ Reply

8 years ago, # ^ |

-10

Solved it with segment tree.

→ Reply

pimenta

8 years ago, # ^ |

Overkill

→ Reply

8 years ago, # ^ |

but i did it http://codeforces.net/contest/816/submission/27857211

→ Reply

gunner_1696

8 years ago, # ^ |

B would have been interesting if each query had its own 'k'. That would have been a good question on merge sort tree .

→ Reply

gabrielsimoes

8 years ago, # ^ |

No need for merge sort tree if queries come after updates.

→ Reply

gagannagpal68

8 years ago, # ^ |

Then, i would have gone for segment tree and a node will be a sorted vector of elements lying in segment. Now for query, just binary search to find. Query would be O( log(n) **2)

How is merge sort tree approach different from that ?

→ Reply

8 years ago, # ^ |

Let's say we calculate 2 arrays:

int l_cnt[200200];
int r_cnt[200200];

l_cnt[t] — how many intervals start with temperature t?
r_cnt[t] — how many intervals end with temperature t?

Then we can figure out in O(1) the number of intervals covering some given temperature t in the following way:

int covering_intervals = n - l_cnt[t + 1] - r_cnt[t - 1];

→ Reply

8 years ago, # ^ |

think about sum A[1...r] then you need to add 1 to [l, r]. 1<=l<=r<=a. think about sum A[1...r-1] then you need to add 1 to [l, r]. 1<=l<=r<=a. think about sum A[1...r-2] then you need to add 1 to [l, r]. 1<=l<=r<=a. You store array D[1...n] Add 1 to D[l], subtract 1 from D[r+1]. And them D[i]=D[i-1]+D[i]. Here you have a prefix array Check if D[b]-D[a-1]>=k.

→ Reply

taxi_driver

8 years ago, # ^ |

With Binary Search code

→ Reply

severussnape0x

8 years ago, # ^ |

Can you explain why your code works ?

→ Reply

taxi_driver

8 years ago, # ^ |

← Rev. 4 →

For each temprature check in how many ranges it lies within the range (with binary search explained below)
For all those tempratures whose value is >=k we use prefix array dp[i] = dp[i-1]+1(if its is more than k) else dp[i] =dp[i-1]

3.now every query can be answered in O(1) time .

Total complexity is O(nlogn)

Now to check in how many ranges a tempratue values lie within you can use upper_bound and lower_bound function from stl calculate the lower_bound from the right array as it will return no. of values in right array more than that value , after that we need to subtract those values from the above values whose left index is more than the required temprature so we use upper_bound function , and the difference between the two is our answer , now if it is >=k than we should include it else not.

obviously , we need to sort left and right arrays

→ Reply

kunal_khatri

8 years ago, # |

My C is failing System Test today :(

→ Reply

sky_light

8 years ago, # |

Canany one give me a clue for problem B? I think solution is binary search but I can't code :(

→ Reply

8 years ago, # ^ |

Use prefix array

→ Reply

8 years ago, # |

How to solve Div2 C?

→ Reply

Triracle

8 years ago, # |

Of course, a coupon cannot be used without buying the corresponding good Anyone forgot this case like me ? :'(

→ Reply

Aviously

8 years ago, # ^ |

+21

No, because then you can just use all the coupons :P

→ Reply

Triracle

8 years ago, # ^ |

← Rev. 2 →

No i don't think so what about this case :

4 4

2 1

2 1 1

10 9 1

2 1 3

We can not use all the coupons

→ Reply

satyaki3794

8 years ago, # ^ |

If you can use a coupon but not buy the good, Then you can just use all the coupons but buy only the lowest (C-D) items as long as you can. In other words, equivalent to the problem, you have an array of values (equal to C-D), find the max no of items you can buy with sum <= B.

→ Reply

vntshh

8 years ago, # |

← Rev. 2 →

Div 2 C was an 99% copy of this problem. MRTNSFRM

Just wrote what was in the editorial.

Edit: Did not notice bhishma's comment.

→ Reply

8 years ago, # |

What was complexity of your solution for C? Mine was brute force that works in 0(500 * n * m)

→ Reply

8 years ago, # ^ |

You can do it in $\text{[math]}$ if you just find minimum in row/column and substract it. Since max answer is roughly max(n, m) * 500, it is faster. However, your complexity should be totally fine.

→ Reply

vivace1

8 years ago, # ^ |

← Rev. 2 →

I did exactly what you mentioned . Hope i pass system tests . This is my first time that first 3 passed pretests.. Update : I got TLE in 3rd :/

→ Reply

nimxor

8 years ago, # ^ |

← Rev. 2 →

Also you can use DP+priority Queue to do it in (n*m). Link to my code here

→ Reply

8 years ago, # ^ |

Thanks

→ Reply

8 years ago, # |

+34

Spent a lot of time on C, found a DP approach, proved the correctness, proved the time complexity is less than $\text{[math]}$ , submitted 15 minutes before end of contest and got WA on pretest 3.

Panicked.

Re-read the statement to find out that D_i is the discount and not the price after discount.

Phew. Hope it holds.

→ Reply

shubhamgoyal__

8 years ago, # ^ |

+31

I am guessing it is similar to the question "Barricades" from "Looking for a challenge" book.

→ Reply

dj3500

8 years ago, # |

+48

I'm guessing div1-E was inspired by Bathroom Stalls from this year's GCJ Qualification Round?

→ Reply

Hikari9

8 years ago, # ^ |

So that's why it looked familiar!! The new 10^18 bounds though...

→ Reply

mnaeraxr

8 years ago, # |

+15

Problem E is similar to Problem C from this year Qualifications Round in Google Code Jam, but this problem was more challenging.

→ Reply

OneClickAC

8 years ago, # |

Can anybody please tell me, if there is a segment tree + lazy propagation approach for Div2 B ??

→ Reply

8 years ago, # ^ |

← Rev. 2 →

Yes, it can be done in that way too but it can be solved easily using prefix array. Look at this code — 27855143

→ Reply

8 years ago, # ^ |

You can just find all temperatures that suit and answer on queries using binary search

→ Reply

NourAlhadi

8 years ago, # ^ |

Make an array of pairs with size 200000.

let the first element of the pair as start of some of the given ranges and the second as the end.

now iterate over all values from 1 to 200000 cumulating sum like the following:

sum += a[i].first , sum -= a[i].second. but before subtracting the end check if the sum on index i is greater than or equal to K then on another array mark i as true or just 1.

now build a segment tree (regular segment tree of sum) on the array of marks. and answer regular sum query on it.

sorry for detailed explanation :D code

→ Reply

_VanGogh_

8 years ago, # |

+21

What a fucking problem D (Div.2) that was garbage :/

→ Reply

HanaElhami

8 years ago, # ^ |

Shit > problem D

→ Reply

Abdelfatah_Elsisi

8 years ago, # ^ |

if your king paid that billions for improving mathematical books instead of trump you wouldn't have said that :)

→ Reply

dcordb

8 years ago, # |

← Rev. 2 →

What is the time complexity of this solution for Div2 E/Div1 C?? Is this O(n²) or O(n³). I think it is the latter, what do you think?

→ Reply

MofK

8 years ago, # ^ |

+18

It is actually O(n^2) because for each u, the total number of iterations is the number of pairs(x, y) such that lca(x, y) = u. That sums up to number of all pairs (x,y) in the tree.

The sad thing is that I thought O(n^2 * log(n)) was fine so I sorted each node's descendants to calculate f[u][i][0] instead of running another DP :(

→ Reply

dcordb

8 years ago, # ^ |

+19

Yeah that's sad indeed I thought that this solution will be slow so I didnt program that and instead I was trying to optimize it.

Shit. :(

→ Reply

satyaki3794

8 years ago, # ^ |

You can learn about this trick using this problem Barricades whose solution is described here (just download the preview).

→ Reply

.tx

8 years ago, # |

← Rev. 2 →

+13

815E - Karen and Neighborhood is a simplified version of task 3 (OGLEDALA) from Croatian olympiad in informatics 2015 March 28th

→ Reply

admarkov

8 years ago, # |

← Rev. 2 →

+26

+12:-2

→ Reply

poegva

8 years ago, # |

Div2C/Div1A — https://www.codechef.com/problems/MTRNSFRM

Div1E — https://code.google.com/codejam/contest/3264486/dashboard#s=p2 (very similar)

As I know, Div2E/Div1C also appeared in some past contest.

It loks like author is very good at copying problems)

→ Reply

ioitcprac

8 years ago, # ^ |

+29

→ Reply

redocyz

8 years ago, # ^ |

What's wrong with div1 E being similar. Can't the author be inspired by the problem? Most people here did the GCJ but did not solve this anyway.

→ Reply

Don_1234

8 years ago, # ^ |

+16

DIV2A- http://codeforces.net/problemset/problem/108/A

→ Reply

toilanvd_KAIST

8 years ago, # ^ |

Div1C is similar to Codechef Snackdown 2017 Elimination Round problem BLACKCOM (just some weeks ago).

→ Reply

kingofnumbers

8 years ago, # ^ |

only because both problems are "dp on tree" then you consider them similar? in my opinion they are quite different

→ Reply

toilanvd_KAIST

8 years ago, # ^ |

Problemsets are quite different. I mean the solutions of optimizing O(n^3) to O(n^2) are similar.

→ Reply

mmaxio

8 years ago, # |

+11

160+ tests in problem A X_X

→ Reply

Kostroma

8 years ago, # ^ |

398 tests in problem E O_o Maybe it's E just because of that? :D

→ Reply

vsp4

8 years ago, # |

+170

My last 2 minutes: I somehow had unused functions (but compiled) that were dependent on my local template :|

→ Reply

Hikari9

8 years ago, # ^ |

+13

That's the closest clutch I have ever seen! Great job at saving your rating haha

→ Reply

Oreo_85

8 years ago, # |

+25

Sorry, Karen I couldn't help you in Task: C,D,E :(

→ Reply

E869120

8 years ago, # |

-10

My contest submission status:

The Time and the Memory value is increasing, and I can even make two trapezoids!
That's interesting! :D

→ Reply

raja1999

8 years ago, # |

+10

Very slow system testing :p

→ Reply

raiden_11

8 years ago, # ^ |

That's because Div2 C has over 175 testcases!

→ Reply

raja1999

8 years ago, # ^ |

Ohhkk

→ Reply

8 years ago, # |

← Rev. 2 →

+10

E peeled of easy binary searches in main and ifs for k=1,2

That's ... unexpected ;p

(this function tells "how many people will be placed on interval (l, r) if l and r are already occupied and people will not move in if distance is smaller than dis or it is equal to dis and their position is > bd)

→ Reply

Kostroma

8 years ago, # ^ |

+20

Taking someone's problem and making it just a bit harder is definitely not the best way to create programming problems.

→ Reply

matthew99

8 years ago, # |

← Rev. 2 →

+74

Well... were I more skillful, I'd have solved C easily.

Were I more tactical, I'd have skipped C quickly and would have solved D sooner and probably solved E.

I can't believe I can't solve a task that 100+ ppl can solve. If this happens in IOI, I can put my head through a wall.

→ Reply

8 years ago, # ^ |

+20

That's already well known trick mentioned many times on CF that such dp runs in O(n^2) and not in O(n^3) and solving it in O(n^3) is pretty straightforward

→ Reply

matthew99

8 years ago, # ^ |

Well...I always solve this kind of tasks using dp on dfs sequences, which somehow don't work(at least I think) on this task.

→ Reply

8 years ago, # ^ |

← Rev. 5 →

+17

What do you mean by that? I do it in a most standard way of doing dps on trees

Dfs(v) {
  initialize dp[v]
  for child in children[v]:
    Dfs(child)
    merge dp[v] and dp[child]
}

where dp[v][cnt][coupon] is cheapest cost of buying cnt guys from v's subtree so that I used coupon on v if coupon==1

→ Reply

fofao_funk

8 years ago, # ^ |

How to prove the complexity is indeed O(n²)?

→ Reply

gabrielsimoes

8 years ago, # ^ |

Search the comments here in this page...

→ Reply

fofao_funk

8 years ago, # ^ |

Thanks for the help.

→ Reply

tfg

8 years ago, # ^ |

For each subtree you'll make Size of previous subtrees * Size of this subtree, the sum of everyone of these is the number of pairs of vertices (u, v), so it is O(n^2).

→ Reply

fofao_funk

8 years ago, # ^ |

Thanks for the help.

→ Reply

WuHongxun

8 years ago, # ^ |

← Rev. 3 →

well it works in O(n² * logn) in this task I guess

→ Reply

8 years ago, # |

As a forever yellow, I am very happy about the difficulty of Div1B and Div1C — usually Div1B is somehow clear (save for maybe some implementation challenges), and Div1C is just too difficult. This difficulty distribution definitely felt more fun.

Your mileage may vary, for others this difficulty jump might have been to much between Div1A and Div1B ... what are your thoughts?

→ Reply

camypaper

8 years ago, # |

+30

It's surprising week sample, week pretest and cute image :P

→ Reply

rajat1603

8 years ago, # |

+150

was there any better way to solve div1B than observe pattern in this

→ Reply

8 years ago, # ^ |

-8

I don't think so. I also tried to do it like this (but did a mistake in a brute xdd) and people I talked to also did same thing. You can also magically guess what the answer will be and check it manually :D.

→ Reply

Hikari9

8 years ago, # ^ |

I would like to know closed form for n%4 == 3 and n%4 == 0 as well. Will wait for that editorial :)

→ Reply

8 years ago, # ^ |

For $\text{[math]}$ it is $\text{[math]}$ .

→ Reply

rajat1603

8 years ago, # ^ |

for n%4 == 0 , let x = (n-2)/2 , then the sequence is xC0 , -xC0 , xC1 , -xC1 , ... , xCi , -xCi , ... xCx , -xCx.
for n%4 == 3 , try to observe nth and the n-1th row , its either [n-1][i] + [n-1][i-1] or [n-1][i] — [n-1][i-1] depending on parity.

→ Reply

silicon_lover

8 years ago, # ^ |

← Rev. 3 →

Since pattern for n%4 == 0 is really nice one. We can just perform the operation for n%4 times and then use the pattern for the n%4 ==0. One more observation to make is that if the last operation you performed in above step ( to reduce to n%4==0 ) is '+' then now our starting operation in the new scenario will be '-' which is different then the standard problem. Only change we need to make now is to use the same formula as mentioned by @majk but just omit the pow(-1,i) part ( all the values will be +ve if we start with a '-' operation ) my code

→ Reply

rizhiy

8 years ago, # |

good pretests for div2 C

→ Reply

sdpsarker88

8 years ago, # |

system testing is too slow! :(

→ Reply

Alhelal_01

8 years ago, # |

Very slow system testing.

→ Reply

BigBag

8 years ago, # |

+22

Am I the only who couldn't hack any solution because whenever I tried to open some solution it wrote that I need to install the newest version of Adobe flash player?

I spent 15 minutes and finally installed new version, but I still was recieving such messages.

→ Reply

ania

8 years ago, # ^ |

+13

I wanted to try hacking 5 minutes before the end so I just gave up after seeing that message.

→ Reply

8 years ago, # ^ |

+30

I always use Chrome but for hacking I use firefox xD (because I get same error and I don't know how to fix it xD)

→ Reply

Endagorion

8 years ago, # |

+59

A screencast of my (pathetic) performance.

→ Reply

PoomrokC

8 years ago, # |

Maybe I should study more math before participating future contests as of late so many DIV2 C,D are using maths. So the algorithms I know are not needed here. I wish I am a math guy lol.

→ Reply

rawr

8 years ago, # |

Just some complexity checking here. Can anyone tell me why my code runs only in 62ms ? http://codeforces.net/contest/816/submission/27862413 I use 4 nested loops with O(500*n*m*(n+m)) right here. Shouldn't 10^9 at least takes 1 second in codeforces judge?

Thanks.

→ Reply

rotavirus

8 years ago, # |

+28

ah i could hack a lot of solutions(( but i wasted time trying to solve D

→ Reply

apaar_97

8 years ago, # |

How to solve Div2 D

→ Reply

balalaika

8 years ago, # ^ |

← Rev. 2 →

ans = k0 * a0 + k1 * a1 + k2 * a2 + ... + k(n-1) * a(n-1)
Corner cases:
n % 4 == ???:

1: t = n / 2 — 1;
Then k = {C(t, 0), 0, C(t, 1), 0, ... }

2: t = (n — 1) / 2
Then k = {C(t, 0), C(t, 0), C(t, 1), C(t, 1), ...}

Other two cases for exercize.

→ Reply

apaar_97

8 years ago, # ^ |

How did you come this to solution, observation?

→ Reply

balalaika

8 years ago, # ^ |

yes, just bruteforce to 20

→ Reply

Radewoosh

8 years ago, # |

+93

:3 , just :3

→ Reply

vintage_Grigory_Reznikov

8 years ago, # ^ |

+10

Two first places in a row? Incredible :D

→ Reply

Radewoosh

8 years ago, # ^ |

← Rev. 2 →

+19

Marcin_smu did it some time ago, it can be seen that he's my "coach" on my university XD

→ Reply

vintage_Grigory_Reznikov

8 years ago, # ^ |

+12

Yea, 318 and 319. Poland strong :D

→ Reply

8 years ago, # ^ |

+56

→ Reply

I_love_Hoang_Yen

8 years ago, # ^ |

← Rev. 2 →

+11

On 318 and 319, Marcin_smu both took 1st place, mnbvmar (also from Poland) both took 2nd place.

→ Reply

shahed_ahmed

8 years ago, # |

← Rev. 2 →

Why so many people (including me) forgot to handle the n>m case (div2 C)?.... and nobody hacked my solution :'( :'(

→ Reply

8 years ago, # ^ |

Mine was hacked 2 minutes before the end... :D

→ Reply

Hussien_Ibrahiem

8 years ago, # |

+38

the best thing in this contest that the problems was clear and easy to understand thanks robinyu

→ Reply

8 years ago, # |

+40

It's over, I have the high ground!

→ Reply

yakamoz

8 years ago, # |

Finally I am blue again !!

I hope, I can see pink in future.

→ Reply

8 years ago, # |

Finally expert!!! <3

→ Reply

aquablitz11

8 years ago, # |

Div. 2 C n > m case. RIP.

Sometimes, I just wish. D:

→ Reply

amanbol

8 years ago, # |

← Rev. 2 →

When will the next round be?

→ Reply

https://pastebin.com/TzpachRc

8 years ago, # ^ |

In July =)

→ Reply

hmrockstar

8 years ago, # ^ |

nope!

→ Reply

dj3500

8 years ago, # |

+17

My screencast here (99th place :C)

→ Reply

sdnr1

8 years ago, # |

I cant figure out why my code is giving negative output on test 19 for Div1 B. Link http://codeforces.net/contest/815/submission/27857089

→ Reply

Anachor

8 years ago, # ^ |

In your code, a1 can be negative. So, say a1=-1e9, a2=1e9; Then (a1-a2+MOD) is still negative.

→ Reply

sdnr1

8 years ago, # ^ |

← Rev. 3 →

Okay but see this submission(i printed a1 and a2 if ans is negative) http://codeforces.net/contest/815/submission/27868207. So a1 is not negative here.

→ Reply

Anachor

8 years ago, # ^ |

Okay, This time the bug's in the other branch, ans=(a1+a2)%MOD. Here, a1+a2 becomes negative, since a2 is negative.

→ Reply

Len

8 years ago, # ^ |

just add if(ans < 0) ans += MOD

→ Reply

piyush1146115

8 years ago, # |

Can not get any idea about Div2 C..Help needed about realizing the solution of the problem ..

→ Reply

satyaki3794

8 years ago, # ^ |

← Rev. 2 →

If you fix the number of times you add to the first row, all other variables get fixed automatically. Let no of times you add to row i be ri and that of column j be cj. If you fix r1, cj = arr[1][j]-r1. Now, ri = arr[i][1] — c1. After that you just check if all ri>0 and cj>0 and ri+cj == arr[i][j]. Then it is valid. If it is valid, take the minimum number of steps, which is sum of ri and cj. There are atmost 500 values possible for r1, as 0<=r1<=500 because 0<=arr[1][1]<=500.
Time complexity is O(M*n*n) where M is max value in array.

Code

→ Reply

nimom

8 years ago, # |

In which category does problem C(Div 2) falls in?

→ Reply

gabrielsimoes

8 years ago, # ^ |

Greedy maybe?

→ Reply

desikachariar

8 years ago, # |

Had some weird errors during the contest in div2 C. Four five submissions. Please look into it so that it doesn't repeat. submission

→ Reply

scorer

8 years ago, # |

Can anyone tell me why my C answer is wrong.?

→ Reply

Jakube

8 years ago, # ^ |

You want to find the solution with the minimal number of moves. The solution 50 col 1 col 2 ... col 50 consists of less moves than your solution.

→ Reply

ManiSadati

8 years ago, # |

Nice both pictures and problems

→ Reply

segwit

8 years ago, # |

ARIGATO GOSAI MASSHH for the round... :D

→ Reply

derAdler

8 years ago, # |

How to prove that the order of making changes in various rows and columns in div2C is interdependent .... Someone plz help i have trouble in understanding....

→ Reply

derAdler

8 years ago, # ^ |

I mean can't we apply the transformation in any order i.e why do we only need to do the rows first and then the column or viceversa

→ Reply

Jakube

8 years ago, # ^ |

Each transformation can be represented by a matrix addition. And those operations are commutative.

→ Reply

Diplomate

8 years ago, # |

How to solve Div 2 B without a segment tree?

→ Reply

Emsawy

8 years ago, # ^ |

Using cumulative sum.

→ Reply

8 years ago, # ^ |

I used binary search. First, for each temperature you check if it's admissible or not(you can do it just iterating through them and calculating balance of segments) and add it to the array if it is(array will be sorted if you start from t = 1). Then on queries you just do binary search to find the first and the last suitable temperature for current query. My code: http://codeforces.net/contest/816/submission/27853021

→ Reply

eddy1021

8 years ago, # |

+64

My screencast

Hope you find it interesting

→ Reply

_khavin

8 years ago, # |

This is my submission for problem A:27853670

It says my solution failed at pretest 10. If i run that on my mac i'm getting the right answer which is 20. Can anybody explain where it went wrong...

→ Reply

jebouin

8 years ago, # ^ |

You are accessing the strings s1 and s2 but they are empty, which is undefined behavior. That's why it may work on your mac but not with the online judge.

→ Reply

sunil.dinday

8 years ago, # |

My approach for Div2 C:

first calculate minimum element in each row .it denotes the number of operation we can do in corresponding row.and store it inside a vector named row
Now calculate the maximum element among each element we have calculated in the previous step.let's denote it by mn
now for each column calculate its maximum element.let denotes it by mx .Then abs(mn-mx) will denotes the number of operaetion in a column, and store abs(mn-mx) inside a vector named col
now to check for invalid case.make a new matrix lets say ff.each cell(i,j) of the ff matrix will be row[i-1]+col[j-1].if g!=ff then print -1 else answer exit
now to calculate the answer.just calculate the sum of all element in vector row and col lets saya answer is ns1;
Now do the step-1 for column and step-3 for row and store the result inside vectores col1 and row1, and calculate the answer ns2
answer will be minimum of nsand ns2 see modeMy code

→ Reply

sdpsarker88

8 years ago, # |

Ok, I've upsolved Div2C in greedy approach after the contest, but I don't understand why it works! Can anyone explain?

→ Reply

lcnltv2019

8 years ago, # |

What problem B? I didn't understand :(( help me!!!

→ Reply

Lance_HAOH

8 years ago, # ^ |

You are tasked to find the sum of lengths of segments (all their values >= k) within given intervals [l,r] (both ends inclusive).

This problem is tailor-made for segment tree/fenwick tree. My solution using segment tree: link.

Of course, a fenwick tree solution is similar but easier.

→ Reply

shubham_827

8 years ago, # ^ |

Your solution is 4 times faster than mine, but I can't understand how?

Your solution's complexity:

build: O(NlogN)

First loop: O(NlogN)

Second loop: O(NlogN)

Third loop: O(N)

Queries Loop: O(Q)

My solution's complexity:

First loop: O(N)

Second loop: O(N)

Queries loop: O(Q)

So overall your solution runs in O(NlogN) and mine in O(N), but your solution passed in 486ms and mine in 1933ms.

My code link

P.S: I submitted it in practice, does it have any effect.I have seen other's solution there's too takes around 1800ms.

→ Reply

Mucosolvan

8 years ago, # ^ |

After adding ios_base::sync_with_stdio(0) (that makes cin/cout faster) your solution runs in 670 ms, so it's much closer to 500ms :)

→ Reply

frag.jdk

8 years ago, # |

← Rev. 2 →

I used java for solving 816A. It worked perfectly fine on my computer ( I have JAVA 8 too) but not on codeforces. It gave a runtime error. Following is the code snippet:

//      s: scanner
        StringBuilder in = new StringBuilder(s.readWord());
        StringBuilder rev2 = new StringBuilder(in);
        StringBuilder rev = rev2.reverse();
        //Error starts here
        int rm = Integer.parseInt(rev.substring(3,5)); //ERROR HERE

//

Thing is, if in = "05:39", for my computer rev.substring(3,5) = "50".
However for codeforces, rev.substring(3,5) = ":5".
Hence, for codeforces rev.substring(4,6) = "50", while for me it is an ArrayIndexOutOfBoundError
Can anyone tell me why is this happening?

→ Reply

luv94

8 years ago, # ^ |

← Rev. 3 →

I tried your solution on 1. "05:39" 2. "05:39 " It showed me the same error on (2), so I guess the test cases have a space character at the end and that is causing some problem.

→ Reply

frag.jdk

8 years ago, # ^ |

The scanner is set to stop amd ignore ' ' and '\n'. Is there any other characters I should ignore?

→ Reply

luv94

8 years ago, # ^ |

← Rev. 4 →

you are using a readline() and your readline() breaks when (c == '\n') or (c = read() != -1), so I guess it is still reading that space symbol. EDIT: your readWord() also fails, just try this->

if (c != ':' && !(c >= '0' && c <= '9')) in your readLine() or readWord(). This is a temporary fix just meant for this problem. I guess the input has some strange whitespace char at the end which I don't know about. I tried submitting your code with this and it worked! http://codeforces.net/contest/816/submission/27884725

→ Reply

frag.jdk

8 years ago, # ^ |

I guess this is the problem. Thanks a lot for your help, I was really confused!

→ Reply

luv94

8 years ago, # ^ |

No problem!

→ Reply

Azuz

8 years ago, # ^ |

Hello, frag.jdk

I think i found the error but if you can share your complete code i can be sure about it.

Here is what i think : the error is the in the rev.substring(3, 5). If you are working with integers and then trying to make a string like if hh = 12 and mm = 55 you create a string eaquals to (12:55) in other word some sort of concat... you will for sure get a run time error.

Why? imagine you have mm = 59 and you want to increment it to 60 then you which will give you 0. and imagine you have hh = 0 which you will increment to 1 the string will be "1:0" not "01:00" rev.substring have range from 3, 5 which are out of "1:0"'s range.

I hope i made it clear.

→ Reply

k0syan

8 years ago, # |

I have solved 2 problems and want to know why my answers are skipped, what is the reason???

→ Reply

RedNextCentury

8 years ago, # ^ |

It means you cheated

→ Reply

_namespace

8 years ago, # |

+32

Any idea when will the editorials be uploaded ? Thanks

→ Reply

Sert

8 years ago, # ^ |

+11

May be jury doesn't have their own solutions for all of the problems and they are now trying to understand the code of the guys who solved them.

→ Reply

8 years ago, # ^ |

Hi, so to me seems like a notorious coincidence

→ Reply

_hoang

8 years ago, # |

+37

Waiting for editorial

→ Reply

8 years ago, # |

+133

blackEarth's (North Korea, obviously) submissions times:

→ Reply

TimonKnigge

8 years ago, # ^ |

+36

Not to mention subtle differences in coding styles in the submissions on D/E (using LL or ll for long long, cin/cout vs scanf/printf, if (x) vs if(x), ...).

→ Reply

guptautkarsh028

8 years ago, # |

+21

Please provide the Editorial.

→ Reply

chinese

8 years ago, # |

+71

→ Reply

nima10khodaveisi

8 years ago, # ^ |

+20

Editorial will be uploaded by tomorrow

I am pretty sure that today is tomorrow for yesterday :D

→ Reply

8 years ago, # |

How to solve Karen and supermarket?

→ Reply

GreenGrape

8 years ago, # ^ |

Notice that coupons form a tree rooted at 1.

Then calculate dp[current vertex][total number of goods purchased in the subtree of this vertex][did we apply a coupon for the good in this vertex]. After that the answer will be maximum possible i such that either dp[root][i][0] or dp[root][i][1] is not greater than b.

Check my code for details :)

27885164

→ Reply

8 years ago, # ^ |

Thanks! So we are trying to minimize the cost of i goods at vertex v.

→ Reply

8 years ago, # ^ |

Your complexity looks high, close to n^3 :| How did this pass TL?

→ Reply

snek_Case

8 years ago, # ^ |

← Rev. 2 →

+29

It's not really n^3, though it looks like so.

Consider the two for loops for recalculating dp for current vertex u.

The outer one indicates how many goods you buy from the subtrees of all children of u, that go BEFORE the newly added vertex v.

The inner loop indicates how many you buy from the subtree of v.

Thus, the two loops effectively enumerate all pairs of vertices, where two vertices in a pair are FROM SUBTREES OF DIFFERENT CHILDREN OF u, that is, all pairs of vertices with LCA = u. This means, no pair is checked twice, resulting in overall complexity O(n^2)

→ Reply

GreenGrape

8 years ago, # ^ |

Nicely explained :)

→ Reply

8 years ago, # ^ |

Nice observation!

→ Reply

8 years ago, # ^ |

← Rev. 2 →

→ Reply

Zovube

8 years ago, # ^ |

If I'm not mistaken, the problem "Barricades" from here has much in common with this one. It's proved that the complexity is O(n^2).

→ Reply

warrior11

8 years ago, # |

editorial for problem B?

→ Reply

memcpy

8 years ago, # ^ |

Look my comment below.

→ Reply

memcpy

8 years ago, # |

← Rev. 2 →

My solution for problem B. Complexity is O(3nlogn + qlog²(MAX)) where is MAX = 200001 or more. So lets first build Segment Tree with adding on segment(with Lazy Propogation) and then when comes each l_i and r_i add 1 on segment l_i and r_i. Then lets create an array of size MAX and for each i from 1 to MAX assign arr_i its value in first segment tree. Secondary we need to build new 2D segment tree that called merge sort tree on the arr(you can see realization in my code). This kind of segment tree allows us to calculate how many numbers there are in array between elements L and R which are less than any K. Finally when we have query l_i and r_i the answer will be r_i - l_i + 1 - K where is K is the number of elements than less k between l_i and r_i. I know my solution is bad and very crazy thats why i am looking for an other solution. My code: http://codeforces.net/contest/816/submission/27852820 Also i noticed that my solution works when k is different for all queries.

→ Reply

8 years ago, # ^ |

You know, all of your queries are offline... Just use prefix sum array :)

→ Reply

memcpy

8 years ago, # ^ |

Oh... of course. Thank you very much

→ Reply

_hoang

8 years ago, # ^ |

you can use prefix sum to solve this problem .

→ Reply

Gapro06

8 years ago, # |

← Rev. 2 →

Waiting for editorials, Can anyone provide a tutorial for Div2-Problem D?

→ Reply

bigcrunch

8 years ago, # ^ |

In case you missed, refer to the following comments in order http://codeforces.net/blog/entry/52653?#comment-367266, http://codeforces.net/blog/entry/52653?#comment-367389

→ Reply

_hoang

8 years ago, # |

← Rev. 2 →

+12

Waiting for problem D div2 solution

→ Reply

amanbol

8 years ago, # |

27897999 div2B. What is wrong?

→ Reply