AtCoder Beginner Contest 172 Announcement

4 years ago, # |

They made problems hard this time seeing last time many solved D and E.

→ Reply

4 years ago, # ^ |

D wasn't hard at all, it was just OEIS.

→ Reply

Vik

4 years ago, # ^ |

What is OEIS? I wasn't able to solve it.

→ Reply

4 years ago, # ^ |

OEIS is a website which has information about all sequences, This one was 1, 5, 11, 23

→ Reply

Confused_Unga_Bunga

4 years ago, # ^ |

← Rev. 2 →

On-Line Encyclopedia of Integer Sequences Google this or simply OEIS. https://atcoder.jp/contests/abc172/submissions/14775013 D in O(nlogn)

→ Reply

myFakeHandle

4 years ago, # ^ |

it seems that you've successfully created an array div[n+1] , when n can be 1e7 .

i am getting segmentation fault(core dumped) when i try to create an array of 1e7+1 integers in main() . i don't understand why! can you explain please ?

→ Reply

4 years ago, # ^ |

There is something else wrong, array of size 1e7 is no problem.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Man, I used Sieve of Eratosthenes to calculate no of divisors of each number from 1 to n. Here's my AC Code

But I submitted it after the contest because when I run it on my laptop during the contest it didn't gave output to 3rd test case which was 10000000 because i thought it will give me TLE. Any possible reason for this?

→ Reply

4 years ago, # ^ |

You would need to provide a link to the code and an understandable question.

→ Reply

4 years ago, # ^ |

Please read my edited comment

→ Reply

4 years ago, # ^ |

Sorry, that link does not show the code.

→ Reply

4 years ago, # ^ |

I edited the link, don't know what has happened with me today. Sorry man.

→ Reply

4 years ago, # ^ |

Are you sure that this works: ll arr[n+1]={};

Usually there is an 0 between the braces. For vector it works because it calls the default constructor, which initializes all to zero. But on array?

→ Reply

faker_faker

4 years ago, # ^ |

A local array (AKA an array created in a function scope) depends on the size of the stack. Default stack size is not enough to create such a huge size array.

You have 3 options:

Create a global array of max size and use it.
Pass compiler flag to increase stack size.
(I recommend this) Use vectors.

→ Reply

4 years ago, # ^ |

Thanks for the suggestions. Also how to increase the stack size of function mentioned in 2nd option? Though I'll use global array now onwards. Just curious about 2nd option.

→ Reply

faker_faker

4 years ago, # ^ |

Assuming you are on Windows, passing -Wl,--stack=268435456 to the compiler will give same stack size as Codeforces gives.

On Linux, you can use ulimit.

→ Reply

myFakeHandle

4 years ago, # ^ |

i got AC with this code, but it gave segmentation fault in my device. As far as I can remember i've done creating similar sized array before in my device. these type of unexpected behaviors are really dissatisfying :( hope i will get an explanation .

thank you very much for your reply :)

→ Reply

4 years ago, # ^ |

I cannot see anything wrong with that code, and its proofed by AC.

So maybe/likely there is something wrong on your device, some wired compiler options or the like?

→ Reply

4 years ago, # ^ |

What's a wired compiler option? I've a dell laptop i3(5th gen) 64-bit. Don't know apart from this. But yes the problem is with the machine may be. Some people on this thread had same problem like me. Can't do anything now. (-_-)

→ Reply

4 years ago, # ^ |

If you run the code on your laptop you first compile it to a program. For this you use a compiler, and you call this compiler somehow. All compilers suppert uncountable optional parameters to do certein things.

→ Reply

myFakeHandle

4 years ago, # ^ |

Perhaps it might be. :( thank you for you kind replies.

→ Reply

isocyanide7

4 years ago, # ^ |

Or you could just use sieve of erasthothenes to keep count

→ Reply

4 years ago, # ^ |

Hey, I used sieve of eratosthenes but didn't get AC? How did you get it?

→ Reply

rahuliitkgp

4 years ago, # ^ |

Here is Code which uses Sieve

→ Reply

one_last_chance

4 years ago, # |

Really liked the Problem C.

→ Reply

moha.jain

4 years ago, # ^ |

C was awesome

→ Reply

Rocker21

4 years ago, # ^ |

Man I tried it so many times.

Don't know where it went wrong.

→ Reply

moha.jain

4 years ago, # ^ |

same but i got it right at last 1 minute i was taking lower_bound instead of upper_bound

→ Reply

netgear

4 years ago, # ^ |

← Rev. 2 →

indeed!!

→ Reply

one_last_chance

4 years ago, # ^ |

+16

Try to solve it using prefix sum and binary search

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Test cases are perfect. But your solution doesn't consider all the books that can give the better answer.

For example, Consider this test case-
6 4 25
5 15 1 1 1 1
4 15 8 8

Your answer- 3
Correct answer- 6.(As we can read all the books in first stack within given k)

I also couldn't solve it. It require a DP solution or some other solution explained by other coders. which I'm myself trying to understand :)

→ Reply

Rocker21

4 years ago, # ^ |

Can the books be sorted also ? Or is the order fixed?

→ Reply

Gheal

4 years ago, # ^ |

No, they cannot be sorted. It says in the statement that you can only read the books from the top (The first element; this works more like a queue than a stack).

→ Reply

Gheal

4 years ago, # ^ |

Not quite DP.

Calculate the prefix sums for the first array.

Then try to 'read books' from the second stack. For each number of books read from the second stack, use binary search to calculate how many books you can read from the first stack.

The answer is the maximum across the sum of books readable from both stacks.

Submission

→ Reply

torpedo11

4 years ago, # |

How to solve E?

→ Reply

pigeon_hole

4 years ago, # ^ |

← Rev. 2 →

I solved it using inclusion-exclusion principle.Submission

→ Reply

Lucina

4 years ago, # |

← Rev. 2 →

I think F is quite similar to 1325D - Ehab the Xorcist. Knowing idea of this problem could be a massive help.

→ Reply

Geothermal

4 years ago, # ^ |

+21

I didn’t find having solved that problem especially helpful. I would argue that the main challenge of F came from dealing with the condition of maximizing the first value without taking it above A[1].

→ Reply

Lucina

4 years ago, # ^ |

← Rev. 2 →

For me the useful idea is, $$$a+b=(a\oplus b)+2$$$(a & b)$$$ $$$. I didn't find this during that contest and thought it's quite tricky. The idea of digit dp is quite simple in my opinion.

→ Reply

faresbasbas

4 years ago, # ^ |

-8

lol it doesn't require digit dp it was just x = a^b which is xoring boxes 2..n , y = a+b , a is A[0] , b is A[1] , then you just have to find the a&b which is w = (a+b-a^b)/2 , then the answer at first is w then you have to iterate from left to right on x and if you can add this bit to the answer without exceeding a then just add it. this is the solution briefly but you have to add the -1 cases inside

→ Reply

Lucina

4 years ago, # ^ |

Yeah, I messed things up a bit. Thanks for telling. :)

→ Reply

shobhit907

4 years ago, # ^ |

I could infer we have to make xor of first two numbers equal to xor of the rest of the array. How to proceed further?

→ Reply

pranav1152

4 years ago, # |

← Rev. 2 →

How to solve C? Question: https://atcoder.jp/contests/abc172/tasks/abc172_c My solution: https://atcoder.jp/contests/abc172/submissions/14773409

→ Reply

AM_I_Learning

4 years ago, # ^ |

Make prefix sum of array a and b try taking upto ith element in a then find remaining k if ith books in A are being read , with this remaining k binary search in prefix sum of array B to find maximum possible number of books you can read, do the same by taking ith index of array B also.

→ Reply

Dorost

4 years ago, # ^ |

Solved with partial sum and binary search
My code
hope it helps

→ Reply

Geothermal

4 years ago, # |

+34

My solutions to all the problems are outlined at this link.

→ Reply

HurricKane

4 years ago, # |

can anyone tell the logic behind how to solve C?my all sample test cases were coming out right but still it was showing WA for many

→ Reply

Newton

4 years ago, # ^ |

apply binary search

→ Reply

Newton

4 years ago, # ^ |

link to the solution solution

→ Reply

qi003-

4 years ago, # |

Can someone plz explain the solution of problem C.....??plzz

→ Reply

sumit_kk10

4 years ago, # ^ |

Problem C: It can be done using binary search. We will try to select (0, 1, 2, ... , n) elements from a[] and then the differnce that remains = k — prefix_sum[i]. Now, we will binary search the index in B[] in which prefix_sum1[j] is less than difference obtained above. The time complexity of this solution is O(n logm). My solution : https://atcoder.jp/contests/abc172/submissions/14766605

→ Reply

BenL

4 years ago, # ^ |

+12

Using 2-pointer can solve it in linear time.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

can you explain please? I also tried 2 pointers but failed.

→ Reply

blobugh

4 years ago, # |

How to solve E and F?

→ Reply

vineetjai

4 years ago, # ^ |

← Rev. 3 →

For E: Use the inclusion-exclusion principle. Solution

→ Reply

Imtiaz1710

4 years ago, # ^ |

Is it an special algorithm ? or a technique which we use in math?

→ Reply

vineetjai

4 years ago, # ^ |

← Rev. 2 →

just Basic maths.

→ Reply

pigeon_hole

4 years ago, # ^ |

for E: I solved it using inclusion-exclusion principle Submission

→ Reply

4 years ago, # ^ |

F: From the nim-conclusion, the problem is equivalent to "given a, b, x, find k such that (a-k) xor (b+k) = x".

Given an interval [l, r] where l is an multiple of 2^20 and r is less than l + 2^20, we can check in O(1) if there can possibly be an answer k in said interval. Once we find the interval with smallest l, we directly enumerate all values to check if there actually exists one.

How do we check in O(1)? Notice that (a-l)>>21 and (a-r)>>21 must have a difference of at most 1, and likewise for (b+l)>>21 and (b+r)>>21. If there exists a pair (a, b), where a is one of [(a-l)>>21, (a-r)>>21] and b is one of [(b+l)>>21, (b+r)>>21], such that a^b=x>>21, then one exists.

→ Reply

happy15

4 years ago, # ^ |

your algorithm is interesting. however, i can't understand the last part:

if pair (aa,bb) exists and satisfies:

aa belongs to [(a-l)>>21,(a-r)>>21]
bb belongs to [(b+l)>>21,(b+r)>>21]
aa^bb=x>>21

then there is an answer.

could you please explain it more in detail?

→ Reply

4 years ago, # ^ |

Hey! I'll try my best to explain my logic here:

Notice that for any i between l and r (l <= i <= r), then (a-i)>>21 must be either (a-l)>>21 or (a-r)>>21. Likewise, (b+i)>>21 must be either (b+l)>>21 or (b+r)>>21. Since in (a-i) xor (b+i) the first bits of (a-i) do not affect the other bits, we can regard them separately. Just taking the xor of the (almost) constant first bits, we can check if their could possibly exist an i in interval [l, r].

→ Reply

happy15

4 years ago, # ^ |

← Rev. 2 →

now I can prove some of your claims to help me understand:

(a-l)>>21 and (a-r)>>21 must have a difference of at most 1

and

any i between l and r (l <= i <= r), then (a-i)>>21 must be either (a-l)>>21 or (a-r)>>21

proof:

suppose l=x*2^k,r=(x+1)*2^k (which in your case k==20).

(a-l)>>(k+1)
=floor((a-l)/2^(k+1))
=(a-l-d1)/2^(k+1) (where 0<=d1<2^(k+1))
=(a-x*2^k-d1)/2^(k+1)
=a/2^(k+1)-x/2-d1/x^(k+1)

likewise,

(a-r)>>(k+1)
=floor((a-r)/2^(k+1))
=(a-r-d2)/2^(k+1) (where 0<=d2<2^(k+1))
=(a-(x+1)*2^k-d2)/2^(k+1)
=a/2^(k+1)-(x+1)/2-d2/x^(k+1)

hence,

(a-l)>>(k+1)-(a-r)>>(k+1)
=1/2+(d2-d1)/2^(k+1)

because 0<=d1,d2<2^(k+1), -2^(k+1)<d2-d1<2^(k+1). thus

(a-l)>>(k+1)-(a-r)>>(k+1)
=1/2+(d2-d1)/2^(k+1)

belongs to (1/2-1,1/2+1)=(-0.5,1.5)

since (a-l)>>(k+1) and (a-r)>>(k+1) are both integer, thus (a-l)>>(k+1)-(a-r)>>(k+1) belongs to [0,1].

→ Reply

4 years ago, # ^ |

Yep, as far as I can tell that's correct.

Once you find an interval [l, r] that can potentially contain an answer, you just iterate through the entire interval to check.

→ Reply

happy15

4 years ago, # ^ |

so your main strategy is:

search for higher bits of a' and b'
fix higher bits of a' and b'
search for lower bits of a' and b'

am i right?

→ Reply

https://atcoder.jp/contests/abc172/submissions/14745041

4 years ago, # ^ |

Yes, that is correct. This will give a total runtime of O(M sqrt(max(a))) where M is the number of higher bit matches. Although I don't know how to prove that M=O(1), it works very fast :) I'd be grateful if someone can hack my solution or prove that M is constant.

→ Reply

DrSwad

2 years ago, # ^ |

I tried implementing your idea here. It passes all of the tests, except one named after_contest_01.txt. I think this test case was specially constructed to fail this solution idea.

The input array is: $$$2^{39}-2,\ 1,\ 2^{39}-3$$$.

There's no possible solution. But all of the intervals seem to appear as potential, thus timing out.

PS: I know this is necroposting. But many people train using Atcoder problems and view these discussions to learn new approaches. So it might be helpful to some.

→ Reply

vineetjai

4 years ago, # |

How to solve F?

→ Reply

Atish508

4 years ago, # |

Can anyone help me why this is wrong?

→ Reply

Ainur_Mukhtarow

4 years ago, # ^ |

← Rev. 2 →

try test 3 3 5

a = [1, 2, 3]

b = [3, 1, 1]

answer = 3, just take all second array

→ Reply

AlwaysACoder

4 years ago, # |

+13

E had a solution quite similar to Placing Rooks

→ Reply

m_scofield

4 years ago, # |

what is wrong in my solution of problem C https://atcoder.jp/contests/abc172/submissions/14763812 getting WA on 10 test cases.

→ Reply

trailblazer995

4 years ago, # ^ |

Here greedy solution doesn't work as you might get a better solution picking the higher one, Consider the following case, N = 3, M = 3, K = 5, A = [1,2,3], B = [3,1,1], here you can pick the whole B array and answer will be 3

→ Reply

m_scofield

4 years ago, # ^ |

Ohh yes, now I get it, thank you so much

→ Reply

BenL

4 years ago, # |

problem E can be solved by IEP. The closed form answer is:

$$$\left(M!+\sum_{k=1}^{N}(-1)^k\binom{N}{k}(M-k)!\right)\frac{M!}{(M-N)!^2} $$$

→ Reply

hydro_lyte

4 years ago, # ^ |

What is IEP?

→ Reply

BenL

4 years ago, # ^ |

Inclusion–exclusion principle

→ Reply

Dragon_warrior7

4 years ago, # |

does E has something to do with derangements?

→ Reply

PRESS_F_2_PAY_RESPECT

4 years ago, # ^ |

Principle of Inclusion-Exclusion.

→ Reply

Imtiaz1710

4 years ago, # |

I am new in Atcoder. I did't see any English editorial for the problems. Is there any English tutorial available?

→ Reply

majorro

4 years ago, # ^ |

← Rev. 2 →

For International Readers: English editorial will be published in a few days.

It's written in editorial

→ Reply

_nivedit_

4 years ago, # ^ |

will take some time for the translation.

→ Reply

Gagandeep98

4 years ago, # ^ |

They generally come out a day later.

→ Reply

mickeyandkaka

4 years ago, # |

← Rev. 4 →

+11

for problem E, assuming fixed A is [1,2,3...,n], ans = C(m,n) * n! * G(n, m)

which G(n, m) means given 1 ~ n for A, using 1 ~ m for B that satisfy the condition

then G(n, m) = (m — n) * G(n — 1, m — 1) + (n — 1) * ( G(n-1, m-1), G(n-2, m-2) )

G(0, m) = 1, G(1, m) = m — 1

when n == m, G(n, n) = D(n), which is derangements

→ Reply

venky_77

4 years ago, # ^ |

Can you please explain how you got that recursive relation

or any link related to that derivation would be nice

→ Reply

4 years ago, # ^ |

Assuming A is [1,2,3,...,n]

When looking at what G(n, m) should be, let's imagine what the last number, x, in B should be.

There are (m - n) ways to select x greater than n, leading us to a position where our new size is n - 1 where we still have (m - n) available numbers greater than the size (we lose the number we selected, but we gain n as a choice) This gives us the (m - n) * G(n - 1, m - 1) part of the formula

There are (n - 1) ways to select x < n. From here, we have 2 options:

1) select the xth number in B to n.

This leave us with a new size to fill of n - 2, and there were still (m - n) numbers available that are not in A. This gives us the (n - 1) * G(n - 2, m - 2) part of the formula

2) select the xth number in B to be something other than n

Here we can imagine that x is our new 'last number', but instead of being unable to select x for it, it cannot select n for itself. Every other number works the same, so this is the same as G(n - 1,m - 1), giving us the (n - 1) * g(n - 1, m - 1) part of the formula

→ Reply

4 years ago, # ^ |

Is there a way to solve the problem without blindly using any memorized formulas? Some form of dp? What would be a useful definition of dp[i]?

→ Reply

faker_faker

4 years ago, # ^ |

Yes? It's just Principle of Inclusion-Exclusion.

Let $$$S_k$$$ be number of permutations with $$$>= k$$$ positions fixed (as given permutation).

$$$S_k =$$$ (no of ways to choose set of $$$k$$$ positions) * (no of ways to permute $$$(n - k)$$$ positions from $$$(m - k)$$$ elements) = $$${n \choose k} * {m - k \choose n - k} * (n - k)$$$.

Then, Derangements $$$= \Sigma_{i = 0}^{n} (-1) ^ i * S_i$$$

→ Reply

4 years ago, # ^ |

It looks to me that G(n,m) is easy to turn into a dp, since you always decrease m by the same amount you decrease n, so you can disregard m and just keep track of n in each state.

Submission

→ Reply

https://atcoder.jp/contests/abc172/submissions/14765903

4 years ago, # ^ |

Thanks

→ Reply

mickeyandkaka

4 years ago, # ^ |

this is my submission in the contest

→ Reply

cryptomanic

4 years ago, # ^ |

During the contest, I was able to derive this formula

G(n, m) = (m — n) * G(n — 1, m — 1) + (n — 1) * (n - m + 1) * G(n - 2, m - 1)

I am sure this recurrence is correct but this form didn't let the computation to be in O(N)

Thanks for sharing the formula @mickeyandkaka

→ Reply

yzy1

4 years ago, # |

← Rev. 2 →

-6

I have a solution to the D problem with time complexity O(n).

$$$F(n) = \sum_{k=1}^n (\dfrac{k}{2} \times \left\lfloor{\dfrac{n}{k}}\right\rfloor\times \left\lfloor{1+\dfrac{n}{k}}\right\rfloor)$$$

Code (C++):

Read(&n);
for (int i = 1; i <= n; ++i) { ans += (lf(i) / 2) * (n / i) * (1 + n / i); }
printf("%.0Lf\n", ans);

→ Reply

silverfish

4 years ago, # ^ |

Why does it work?

→ Reply

4 years ago, # ^ |

because OEIS

→ Reply

yzy1

4 years ago, # ^ |

This

→ Reply

Harshil_

4 years ago, # ^ |

+10

number 2 appears as the divisor in (n / 2) numbers from total n numbers

In 2,4,6, ... number 2 appears as a divisor exactly one time,

So our answer will increase by

2 * 1 + 4 * 1+ 6 * 1 + ...

2 *( 1 + 2 + 3 + .. + n / 2)

Do the same for 1 to n

Spoiler

for(int i = 1; i <= n; i++)
{
    k = (n / i);
    m = (k * (k + 1)) / 2;
    ans += m * i;
}

→ Reply

AliZainAldeen

4 years ago, # |

C was way harder than D for me , i dont know if its me or the problem.

→ Reply

Gagandeep98

4 years ago, # |

I used 2 pointers instead of binary search in problem C. That was easier to implement in my opinion.

→ Reply

codehacker02

4 years ago, # ^ |

bro can you give me link to you solution using 2 pointers?

→ Reply

KHVic

4 years ago, # ^ |

here's mine for using 2 pointer for C https://atcoder.jp/contests/abc172/submissions/14740634

→ Reply

pranavsindura

4 years ago, # |

Really liked problem E! Good contest!

→ Reply

Compiler_Error

4 years ago, # |

is there any English editorial in atcoder? i am new at Atcoder

→ Reply

Mksiyak

4 years ago, # ^ |

For International Readers: English editorial will be published in a few days.

but you can use google doc translater (its not accurate but you can understand the logic)

→ Reply

hydro_lyte

4 years ago, # |

O(sqrt(n)) solution for D:

ll fun(ll n){
   ll x=(n*(n+1)*(2*n+1))/6;
   return x;	
}
void solve(){
    //input
   double n;
   cin>>n;
   ll i;
   ll sum=0,sum1=0;
   for(i=1;i<=sqrt(n);i++){
	   sum+=i*(i+floor(n/i))*(floor(n/i)+1-i)/2;
   }
   ll ans=2*sum-fun(sqrt(n));
   cout<<ans<<endl;
}

→ Reply

Ilish

4 years ago, # |

← Rev. 3 →

-8

Here is my solution to C.

#include <bits/stdc++.h>
using namespace std;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long n, m, k;
	cin >> n >> m >> k;
	vector <long long> a(n), b(m);
	for (auto &i : a) cin >> i;
	for (auto &i : b) cin >> i;
	long long i=0LL, j=0LL, count = 0LL;
	while (i<n && j<m) {
		if(a[i] <= b[j]) {
			k -= a[i++];
		}
		else {
			k -= b[j++];
		}
		if (k >= 0LL)
			++count;
		else break;
	}
	bool state = true;
	while (i<n) {
		k -= a[i++];
		if (k >= 0LL)
			++count;
		else {
			state = false;
			break;
		}
	}
	if (state) {
		while (j < m) {
			k -= b[j++];
			if (k >= 0LL)
				++count;
			else break;
		}
	}
	cout << count << '\n';
}

Can anyone tell me why the above code gets WA in 10 test cases. Isn't the problem solvable by 2 pointer kinda technique?

→ Reply

ankrypt

4 years ago, # ^ |

Try a case like :-

1 2 120 101 110 10

The correct answer should be 2 by reading the books from array B which take 110 and 10 minutes(collectively a value less than or equal to 120), but your solution gives 1(by picking 101 from array A instead).

→ Reply

Ilish

4 years ago, # ^ |

Ahh, so that means greedy will not give the optimal solution right?! Any help on how to solve the problem? The English editorial is going to take some days to come :(

→ Reply

ankrypt

4 years ago, # ^ |

Since it is clear from the statement that we have to pick books exactly in the order as how they appear, the first intution can be to construct prefix sum arrays for both arrays A and B(say, arrays, prefA and prefB). Why? Because, having two prefix arrays (one for A and other for B) means that, we can find out the time to read books upto the ith book(included), in O(1) for both the arrays A and B, separately. Now, the only part remaining is to search efficiently, the maximum number of books we can read in <= K mins. We can do a binary search since, prefix arrays are always sorted. One approach could be to fix the number of books we can take from array A (0,1,2...N) one by one and if for any of these values, the time taken i.e., prefA[i] is <= K, we do a binary search on prefB to see how many books can be picked from array B, and keep updating the answer, accordingly. Hope it helps :)

→ Reply

dush1729

4 years ago, # |

← Rev. 3 →

why greedy fails for C? at each step pick up the minimum of the two.

UPD — Got it.

Testcase

N = 2
M = 4
K = 13
A = [9,10]
B = [10,1,1,1]

Answer — 4

UP2 — Thank you for so many testcases :)

→ Reply

majorro

4 years ago, # ^ |

Try this

3 3 8
3 3 3
6 1 1

The correct answer is 3, but greedy gives 2

→ Reply

trailblazer995

4 years ago, # ^ |

https://mirror.codeforces.com/blog/entry/79405?#comment-651442, you can check this comment

→ Reply

Cloud_

4 years ago, # ^ |

Try this case

→ Reply

shettypriyesh

4 years ago, # |

Can any one tell why C fails using two pointer approach and any test case for the same.

→ Reply

adisava

4 years ago, # |

← Rev. 3 →

This is a nice explanation of how inclusion-exclusion principle can be used to find the number of derangements. It can be extended to solve E.

Edit: Look for the proof under the formulae section.

→ Reply

Just_A_Nice_Kid

4 years ago, # |

i wonder why this solution WA : https://ideone.com/VIzSXP

someone helps :((

→ Reply

Into_Your_Arms

4 years ago, # ^ |

consider the sequence on desk1 as $$$(1,2,3,4,8)$$$ and on deks2 as $$$(10,1,1,1,1,1,1,1,1)$$$ for $$$k=18$$$. Your $$$ans$$$ is $$$5$$$ but it's 9.

→ Reply

Afia_PCIU

4 years ago, # |

No English Editorial.

→ Reply

ProfessorChaos

4 years ago, # |

← Rev. 3 →

I am new to cpp, so not sure whats the problem. The code gives WA in one test case and RE in one. Rest all is accepted. Any help would be nice.

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    ll A[n]; ll B[n]; ll preA[n+1]; ll preB[m+1];
    preA[0] = 0; preB[0] = 0;
    for (ll i = 0; i < n; ++i) {
        cin >> A[i];
        preA[i+1] = preA[i] + A[i];
    }
    for (ll i = 0; i < m; ++i) {
        cin >> B[i];
        preB[i+1] = preB[i] + B[i];
    }
    ll max = 0;
    ll index = m;
    for (ll i = 0; i <= n; ++i) {
        ll totalLeft = k - preA[i];
        if (totalLeft < 0){
            break;
        }
        while (preB[index] > totalLeft){
            index--;
        }
        if (index + i > max) {
            max = index+i;
        }
    }
    cout << max;
}

→ Reply

4 years ago, # ^ |

ll B[n]; wrong size

→ Reply

ProfessorChaos

4 years ago, # ^ |

yes, that was the problem tysm

→ Reply

Rudro25

4 years ago, # |

← Rev. 2 →

C using upper bound

ll n,m,k,i,s1=0,s2=0,ans=0;
           string s;
           cin>>n>>m>>k;
           ll ar1[n+5],ar2[m+5];
           vector<long long> v1,v2;
           v1.push_back(0);
           for(i=1;i<=n;i++){
            cin>>ar1[i];
            s1+=ar1[i];
            v1.push_back(s1);
           }
           //ck=0;
           for(i=1;i<=m;i++){
            cin>>ar2[i];
            s2+=ar2[i];
            v2.push_back(s2);
           }

           for(i=0;i<=n;i++){
             ll bal=v1[i];
             ll baki=k-bal;
             if(baki<0) continue;
             auto it=upper_bound(v2.begin(),v2.end(),baki);
             ll dis=it-v2.begin();
             //cout<<dis<<endl;
             ans=max(ans,(i+dis));
           }

           cout<<ans<<endl;

→ Reply

agrajgarg

4 years ago, # |

Can somebody explain the solution for problem E, I am not able to understand it.

→ Reply

i_love_my_mom

4 years ago, # ^ |

first of all watch this video then read this comment under this blogpost

→ Reply

agrajgarg

4 years ago, # ^ |

thanks a lot, bro!!!!! Learned a lot from this question

→ Reply

aKILLL

4 years ago, # |

← Rev. 2 →

https://atcoder.jp/contests/abc172/submissions/14775983 can anyone help in C I used sliding window and binary search but getting wrong answers on 4 tcs .UPD-I found the bug

→ Reply

Rudro25

4 years ago, # |

← Rev. 2 →

Easy solution of D just by loop for time limit 3 sec

           ll n,i,j;
           cin>>n;
           ll divs[n+5]={0};
           ll ans=0;
           for(i=1;i<=n;i++){
            for(j=i;j<=n;j+=i){
                divs[j]++;
            }
           }
           for(i=1;i<=n;i++)
            ans+=i*divs[i];
           cout<<ans<<endl;

→ Reply

4 years ago, # ^ |

You can go even simpler than that

    ll n,i,j;
    cin>>n;
    ll ans=0;
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j+=i){
            ans += j;
        }
    }
    cout<<ans<<endl;

or in kotlin

    fun main() {
        val n = readLine()!!.toInt()
        var ans = 0L
        for(f in 1..n){
            for(x in f..n step f){
                ans += x
            }
        }
        print(ans)
    }

→ Reply

Rudro25

4 years ago, # ^ |

Thank you for giving us more simpler way.

→ Reply

_aadiupadhyay_

4 years ago, # |

Hey can anyone help me out where I did wrong in problem C https://atcoder.jp/contests/abc172/submissions/14753662 Thanks in advance

→ Reply

https://atcoder.jp/contests/abc172/submissions/14789913

4 years ago, # ^ |

You implemented a greey solution which does not work well. Consider first stack of books all 2, ie 2 2 2 2 ... and the other one starting with 3, ie 3 1 1 1 1 1....

So you will read all 2-books, but never a 1-book.

→ Reply

_aadiupadhyay_

4 years ago, # ^ |

Thank you sir

→ Reply

kroc44

4 years ago, # |

← Rev. 2 →

Does anybody know why my approach to prob D gives TLE? I ran the Sieve storing, for each number, its prime factors (instead of "crossing off" the number, I stored the prime it's a multiple of.) This should be NloglogN. Then, for each number, I compute the exponent of each of it's prime factors via prime factorization (I already know all of it's prime factors, so this should be NlogN, since we can divide the number at most logN times) in order to get the number of divisors.

Note that this approach works; I don't get any WA, only some TLEs.

Does anybody have any clue?

Thanks!

→ Reply

Believe

4 years ago, # ^ |

I solved D in exact same way. My run time was 2733 ms which is really tight. Actually they expect us to write an O(n) solution for this problem. BTW below is the link to my submission:-

→ Reply

WaterColor2037

4 years ago, # ^ |

← Rev. 2 →

Does the problem can be solved in $$$O(N)$$$? I thought $$$O(N \log N)$$$ is the best.

→ Reply

Believe

4 years ago, # ^ |

Yes it can be solved in O(n). Just think about the contribution to sum of ith integer.

→ Reply