Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Before contest

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

01:49:04

Register now »

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

01:49:04

Register now »

*has extra registration

Before contest

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

01:49:04

Register now »

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

01:49:04

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 204 |

2 | SecondThread | 199 |

3 | Monogon | 196 |

4 | vovuh | 189 |

5 | Um_nik | 186 |

6 | pikmike | 185 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 181 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Technocup 2019 - Elimination Round 2

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/29/2020 08:15:57 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can someone explain exactly why does greedy solution works for Problem C ?

Update :- Understood Now, after translation of editorial

The greedy algorithm I use is a little bit more complicated but you can catch what I mean more easily.

The algorithm goes as follows:

1.binary search part. Use binary search to find how much lecture notes you can read In the two days.

greedy part for the checking function of binary search. Iterate through each note from x to 1. For note i, If you can put it in the day which has fewer hours to spend, It's always better. So we just iterate through. If we find a note that we can't put it in any of the days, we try a smaller amount.

To get the answer uses the same algorithm as the checking part. Just iterate from x to 1, and put the note in the day which has fewer hours to spend. If you didn't get this, I may post my code:44658856

Quick Editorials! And the editorials for 1031B & 1031C in English were mistakenly published in Russian.

Only I used DP for Div.2 B (maybe because I am just a Pupil), sadly?

Wait please, they're gonna be translated

can u plz explain why this is wrong ?? Div2D 44650538

Can you proof why this part-> "Let's iterate over all lecture notes from x to 1 , and on each step we put it into the first day if we can, otherwise if in the first day we have w > 0 free time then we put the lecture note w < x to the first day."

Why mentioned part gives the optimal solution?

There are two possibilities:

All lecture notes are in the first day, this case is trivial.

When we tried to put the

x-th lecture note into the first day, there was onlywfree hours. Let's put the lecturewinstead then. Now the first day is full, and sincea+bis at leastx(x+ 1) / 2, the second day is long enough to read the remaining notes.Why can't we start with 1 ?

I propose an algorithm to divide all lecture notes into two groups properly. If I started with 1, I couldn't fill the first day because the

w-th lecture note would have been already used, so iterating from the greatest is crucial for me.You can try to start with 1 and act in another way, maybe there is an algorithm which solves the problem.

I tried and it worked. I have started with 1 and filled the first day. The strategy I followed while filling is, I greedily filled the numbers until their sum became greater than the capacity of the first day. Then I removed (sum — a) from the set of the first day. And filled rest in the second day. It worked. Here is my submission : http://codeforces.com/contest/1072/submission/44715934

Yeah I see, it's ok, you fill the first day anyway, but you do it with some set like

k- 1,k+ 1, ...,l- 2,l- 1,l},while author does it with a set like

k,l,l+ 1,l+ 2, ...,n}.Can somebody please explain to me why my O(n^2) code for problem D is getting TLE? Help is very appreciated 44655948

EDIT:It's the string comparison, my mistake

Can anyone please help me with question B. I am new to programming and kind of stuck. how to move ahead with the hints given above?

I'm not a native English speaker, sorry for my poor explanation.

It's easy to find that if we get the first two items of the series

t, we will be able to determinate whether it's possible to build atmeets the conditions.Then we will try every possibilities for

t_{1}andt_{2}, we will be able to find the relationships betweentanda,b.Finally we try every possibilities for the first two items (not so much, though), and find if it is possible to meet every

a_{i}andb_{i}(we have one item oft_{i}, and it's easy to determinate whether it's OK for the other items).My solution using DP is described as following: Let

dp[i][j][0] standing for the possibility ofi-th number oftisj, anddp[i][j][1] means which number is the number beforei-th number ofj, we can easily iteratekfrom 0 to 3 for the last number oft, and we can get:Specially, we have

dp[1][0][0] =dp[1][1][0] =dp[1][2][0] =dp[1][3][0] = 1.Then we can judge if

dp[n][·][0] is 1, for`YES`

or`NO`

, and if the answer is`YES`

, usedp[n][·][1] with a stack to printt.Just use simple depth-first-search. The hint means(I think) that you when you brute force the problem, you will not get a TLE.

Hi, can you elaborate more on your DFS approach? Thanks!

Well this isn't so hard. The code is like the folloing

If the process give no answer, just output "NO".

44657446

It seems that DFS can be hacked by this data:

input:

output:

DFS will get TLE or RE (tested in my computer).

Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

Because if

t_{i}has been determined,t_{i + 1}will have only one value to choose. Specially, ifa= 3,b= 0,tcan be 0, 1, 2, 3. But ift_{i}has been determined, we should not worry aboutt_{i + 1}.There is some interesting observation.

there exist at most one value of t(i) for specific value of t(i+1),a(i),b(i).

formally, if there exist t(i) such that t(i) | t(i+1) == a(i) and t(i)&t(i+1)==b(i) then t(i) can be one of the {0,1,2,3}. it means that the equations t(i) | t(i+1) == a(i), t(i) & t(i+1) == b(i) has exactly one solution of t(i) if we know the value of t(i+1),a(i),b(i) or doesn't exist.

you can see this fact using my below code. just run the code and you will see that observation. ~~~~~

## include<bits/stdc++.h>

using namespace std;

int main(){ for(int i = 0;i<=3;i++){ // values of a(i)

} ~~~~~

now simply take t(n) as 0,1,2,3 one by one and find t(n-1),t(n-2),t(n-3)... if there exist sequence for some t(n) then print it otherwise change the value of t(n)..

see this for full code (c++)

sorry for my bad english. Please,right me if i'm wrong.

Problem 1031A - Golden Plate can be calculated directly by formula:

2

k(w+h- 4k+ 2)can you please explain problem B a little more ? i was not applying dp . the thing i concluded was these two conditions 1. a[i]|b[i]=a[i] 2. a[i]&b[i]=b[i] . If any of these fails for any index ,it will show "NO". How to proceed for rest solution ?

I'm not a native English speaker, sorry for my poor explanation.

There is something interesting about Bitwise operation:a^b=(a|b)-(a&b).

So let c[i]=a[i]-b[i],then just let t[1]=0~4 ,and calculate the others t by array c.After this,just judge the array t if or not satisfy the conditions

here's my code: click here...

golovanov399 I think there is some mistake in editorial of 1031B — Curiosity Has No Limits because 4th case "If t1=0 and a1=1 and b1=1 then t2= 1" is wrong as t2 can't have any value because since t1 is 0 , b1 can never be 1 as b1=t1&t2, instead it should be "then there is no such t2".

i agree

Can someone explain their solution for 1031D plz ?

Can someone help be with this solution for 1031B ? Link:44642434

how to solve the Div2.D with above algorithm and not get MLE?

My solution of C is showing error "wrong output format Unexpected end of file — int32 expected" someone please explain:- here is my code https://codeforces.com/contest/1072/submission/44658102

In Div2D, how to write DP for the lexicographically smallest path from (

i,j) to (n,m) inO(n^{2}) memory? My solution requiresO(n^{3}) memory (with recursion using memoization).I used something bfs-liked instead , I have the list of last-minimum block at that length then(For each row there can only be at most 1 element so this list will never exceed n) name A.

Considering this example

We know that the first character must be 'b' , second character must be 'c' , BUT WE DO NOT KNOW IF THE 'c' IS FROM (1,2) or (2,1) , so after we append 'c' to answer our A must contain both (1,2) and (2,1) for future use.

For the next length each block in A can generate 2 more blocks. For the sake of simplicity i used std::set name B to store it to get rid of duplicate blocks and auto sort for me.Then the next character of the answer is value of the first block in the set(set sorted for me). So I get all the blocks from B which has the value equal to the minimum block back into A and repeat until we reached the answer's length.

This way I do not need to store all the string length but only 1 letter for each block in list A. So the total memory used for this step never exceeds O(n) I guess...

Sorry for my bad English

Thank you! This makes sense. But I think this requires

O(n^{2}) time for every time we ask for path from some (i,j) to (n,m). If there are multiple such (i,j) pairs (letM) to check, this would takeO(M×n^{2}) time, whereMitself can be atmostO(n^{2}). How to handle this?UPDATE: I understand it now. We will initialize our set

Bwith these pairs.In question C, why can't be sum of the lecture notes be exactly equal to a+b, it will only affect the last term i.e. x; the sum n+m will still remain same!!

it can be but it won't increase the count of lectures. ex: a = 9, b = 12 output: 2 3 6 4 1 2 4 5 but for a = 10 and b = 12 output: 2 3 7 4 1 2 4 5 OR 2 3 6 4 1 2 4 5 here the sum of lecture notes is exactly a+b but it doesn't affect the count.

Why we always can make all elements be equal to zero when n>=8 in problem 1031e?

You can run bruteforce

If you have >= 8, you can get rid of a 1 in any position.

eg:

A)

Can be done with:

B)

Can be done with:

thus creating 2 instances of (A)

C)

Can be done with:

Similarly, D)

Can be done with:

Ones on the right hand side are of course symmetrical

Excuse me,could you please explain it more clearly?I am not very smart so I can't understand it.

Sorry,but PLEASE!!

In the problem C Cram time, I did the exact same thing, and i guess it runs in O(n)time, still it showed me Time limit in test case 15.

I would really appreciate it if someone could check my code once, please. http://codeforces.com/contest/1072/submission/44647241

44647241

Thanks a lot!

for(i=max(a,b);i>=0;i--) { if(((i*(i+1))/2)<=a+b) break; } this part gives TLE; reduce this through binary_search or directly use quadratic formula;

Thanks for your reply!! I did it in https://codeforces.com/contest/1072/submission/44680186 44680186

Now it shows Run time error in test case 15.Please help

long long int p[a],q[b]; it needs a lot memory for a, b <= 1e9.

I have an alternate solution of Div1D without graphs. We can use dynamic programming on each vector (

x_{1},x_{2}, ...,x_{n}).Assuming that the upper bound of number of divisors isn't great, we have a fast DP the states are

`(prod, pos)`

, where`prod`

is the target product,`pos`

is the current position in the vector. Iterating over all divisors of`prod`

, let's assume that`k`

is a divisor of`prod`

, then a possible state is`(prod / k, pos + 1)`

and it "costs"`abs(x[pos] - k)`

to go to this state. When we reached the end of the vector, we have another mini-DP to calculate the minimal number of operations to get remaining`prod`

. Then, the answer for (x_{1},x_{2}, ...,x_{n}) and (y_{1},y_{2}, ...,y_{n}) ismin(dp(i, 0,x) +dp(i, 0,y)), 0 ≤i≤ 256.Due to very small constants it works in no memory and in relatively small time.

I think Div.1 C involves some background knowledge about linear algebra. Each operation of flipping

a_{x},a_{y},a_{z}can be viewed as a 01-vectorvwhere onlyv_{x},v_{y},v_{z}are 1. We want to find a linear combination of all such vectors that equals to the given array (modulo 2), and it is easy to verify that only whenn> 7 the rank of all such vectors equals ton.LOL qlmupi we just learned this stuff

http://codeforces.com/contest/1072/submission/44700766 failed at testcase 6.

Approach: generate all possible pairs in (0,1,2,3) like p1 = {0,1},{0,2}... for each pair if condition satisfied then print . see my code.

Can Anyone point out mistake in my code.(Div2 C) http://codeforces.com/contest/1072/submission/44638820

Can anyone explain the solution of problem D ?

In Problem C My code shows time limit exceed at test case 15.....

please explain why is this happening while I follow the same concept as mentioned above.... 44751444 My code is working properly on test case 15 at (http://ideone.com)

`long`

is 32-bit on Codeforces but 64-bit on Ideone. Use`long long`

instead.How should actually brute force in div2 E work when we are left with <=10 elements?

For Div1E, do we really need to consider precision issues and prove that our solutions will be precise enough? Why don't we prove it for other problems which also require floating-point arithmetic?

As a contestant you don't have to prove anything, but as the editorialist, I felt responsible for doing this.

Problem C.I want to know why I get WA in test15. I put 1,2...,n into A as many as possible. defined the rest of A is x, I remove the n and put the n+x into A. the I put from 1 to INF if it is not in A.Your text to link here...

for Div.2 A I think the input 5 5 2; The answer is 17. Am I right ? ( if you add this to the main test, many would WA...

Even for

`5 5 1`

the answer is already 20 > 17 as the number of border cellsNo, answer for

`5 5 1`

is 16But

`5 5 2`

is impossible because of restriction onkYou see, I always had bad math

Can someone sent me code-solution of tasks from this contest, please?

Is it possible to add data after the contest?

I found that almost all AC submissions of Div1.E was wrong

It's possible (the solutions won't be rejudged, though). Moreover, if you happen to mean all AC submissions of

Div2.Eandduring the contest, then more tests have already been added.I see.There are 3 small sets of data.They are made when I debug my program using some of the AC codes.But I think my outputs are correct but their outputs are wrong.Would you please check if they're correct?

And I'd like to thank you for holding such a nice contest.

## in1

## out1

## in2

## out2

## in3

## out3

I've just started investigating your tests, and in each of them there is a point with

y= 0, while it's forbidden in the problem. As far as I remember, it's essential for the solution.Oh,I didn't see the data range clearly.I'm so sorry for bothering you.

Then it turns out that most of the AC codes are correct but only a few have problems.

in

out

I'm trying to find out why it works.