Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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 only w free hours. Let's put the lecture w instead then. Now the first day is full, and since a + b is at least x(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.me/contest/1072/submission/44715934
Yeah I see, it's ok, you fill the first day anyway, but you do it with some set like
while author does it with a set like
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 a t meets the conditions.
Then we will try every possibilities for t1 and t2, we will be able to find the relationships between t and a, b.
Finally we try every possibilities for the first two items (not so much, though), and find if it is possible to meet every ai and bi (we have one item of ti, 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 of i-th number of t is j, and dp[i][j][1] means which number is the number before i-th number of j, we can easily iterate k from 0 to 3 for the last number of t, 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
orNO
, and if the answer isYES
, use dp[n][·][1] with a stack to print t.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 ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 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:
2k(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?
In Div2D, how to write DP for the lexicographically smallest path from (i, j) to (n, m) in O(n2) memory? My solution requires O(n3) 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(n2) time for every time we ask for path from some (i, j) to (n, m). If there are multiple such (i, j) pairs (let M) to check, this would take O(M × n2) time, where M itself can be atmost O(n2). How to handle this?
UPDATE: I understand it now. We will initialize our set B with 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.me/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.me/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 (x1, x2, ..., xn).
Assuming that the upper bound of number of divisors isn't great, we have a fast DP the states are
(prod, pos)
, whereprod
is the target product,pos
is the current position in the vector. Iterating over all divisors ofprod
, let's assume thatk
is a divisor ofprod
, 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 remainingprod
. Then, the answer for (x1, x2, ..., xn) and (y1, y2, ..., yn) is min(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 ax, ay, az can be viewed as a 01-vector v where only vx, vy, vz 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 when n > 7 the rank of all such vectors equals to n.
LOL fmqjpt we just learned this stuff
Can Anyone point out mistake in my code.(Div2 C) http://codeforces.me/contest/1072/submission/44638820
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. Uselong 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 on kYou see, I always had bad math
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.E and during 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.
why am i getting wa on test 36 solution link