Vendetta.'s blog

By Vendetta., 3 weeks ago, In English,

The tutorials for problems B & E were written by 1am, D by The-Legend, F by Qumair, J & K by Motarack and M by abo_od303. Thank you guys for also reviewing the rest of the tutorial!

A. Careful Thief

It’s enough to try all segments of size K that either starts with the start of a range or ends with the end of a range, suppose that the optimal solution is somewhere that starts in some range and ends in some other range (possibly ranges of zeroes), then shifting the segment to one direction will increase the answer, and shifting it in the other direction will decrease it until you reach the boundary of the range, or if both ranges have the same amount of money then shifting will not affect the answer. This can be done using a sorted array of the ranges and for each range that starts with li we can binary search for li + k - 1 and to get the result of all the ranges in between we can do a prefix summation for (ri - li + 1) × vi. Same process can be done for trying the ends of all ranges.
Complexity per test-case: .

Solution

B. Friends and Cookies

This problem simply requires implementation with basic modulus and division calculations. Please observe the following image:

The first iteration, Abood will start to give his friends cookies starting from the 1st friend, till the nth. We can simply loop this, since n is maximum 1000. Or add 1 to all friends if x ≥ n. After that, it's just careful calculations. Decrease n from x, and divide what is left by n - 1. This is because in the iterations after the first one, Abood will give cookies to the first n - 1 friends, then to the last n - 1 friends. So by dividing, I can figure out how much each friend will eat without having to loop x times. The only thing left to deal with is , the remainder cookies. Depending on whether is even or not, I can figure out the direction of the last iteration, and where I start giving (either start n - 1 and move to the left, or start at 2 and move to the right). Using that, I loop accordingly only the remainder until I have no more cookies left. It is possible to loop because we know the remainder will be less than n - 1. I’m too lazy to discuss exact calculations, if anything is unclear please feel free to write in the comments. Oh and don't forget to clear the array between iterations, and be careful of division by zero when n = 1.
Complexity per test-case: O(N).
Solution

C. Flip the Bits

The maximal number m which is less than n is n - 1, so the number of flipped bits will be exactly the number of different bits between n and n - 1 which is equal to the number of 1 bits in n XOR (n - 1).
Complexity per test-case: .

Solution

D. Magic Sticks

Let us use these terminologies:

  • Each line belong to 1 × 1 cell we will call it edge
  • Each line parallel to one of the biggest rectangle's sides n × m and equal to its length we will call it line.

Our solution depends on these two observations about the selected edges:

  • They should be parallel to each others.
  • They should be parallel to the shorter line in the biggest rectangle n × m.

Assume n ≤ m (you can otherwise swap the numbers to satisfy that) And the shorter side n is vertical.
We have m + 1 vertical lines with length n from each one of them if we take an edge then we have to not take the one below or above But how do we select the edges?
We should select them alternatively, why? Let us not take two consecutive edges then there are two cells that are not covered by at least one edge till now so in the next line we must take two consecutive edges to get these two cells covered by at least one edge which will violate the problem's constraints (edges should not touch).
Now let us continue with taking the alternative edges. One of the lines we will take edges among n, the next one and so on..
You have to notice that we have to start with taking from the first line not since we need to take as much as we can in comparing with to minimize the number of edges in the required group.
Here's an example for a 5 × 6 grid:

Complexity per test-case: O(1).
Solution

E. N-Dimensional Grid

There are many different solutions for this problem that can pass, let's discuss the one where you calculate all pairs and subtract the incorrect ones. For every cell, we need to know how many cells have a manhattan distance of 1 with it. It is clear that these pairs will have the same values for n - 1 dimensions, with only one dimension having a different value by an absolute difference of 1.
So for every cell, keep fixed n - 1 dimensions, and decrease the value for one dimension by 1 will give us one non repeated pair. For each cell, there are n ways to do this. Since number of cells is the product of the sizes of all dimensions in the input, we multiply this product by n to get the number of pairs.
Notice that not all these pairs are valid, because we are considering pairs that get matched with a cell with a 0 as one of its values. All we must do now is decrease these invalid pairs. Fix one dimension with a value as 0. The number of valid cells that will be wrongly matched with this invalid one is the product of all dimensions sizes ai except for the one that's currently fixed. Therefore for each fixed i, decrease the product of all dimension sizes except for ai from our number of pairs. This is our final answer.
Complexity per test-case: O(N).

Solution

F. Minimum Sum of Array

Let’s define a frequency array for the original array and a visited array for the values, now for every number x from 1 to 106 with frequency more than zero (it exists in the array) then loop over the multiples of x, if a multiple of x say y is not visited before then we should change y into x as x is the smallest divisor for y in the array.
Complexity per test-case: .

Solution

G. Power of String

Notice that the position of the characters doesn't matter because, for example, if you have character ch repeated Fch times then no matter what their positions are in the string they will add the same value which is equal to , So we are only interested in Fch.
Suppose that we have determined what characters we will change, then all of them should be changed to the same character ch1, and any other equal characters ch should all be changed into ch1 or none, except for one character ch2 that we can change part of it, check the proof below.
Now if we will fix ch1 and ch2, we can calculate knapsack-like DP on all other characters (we know that we will change either all or none of all equal characters).
Complexity per test-case: O(K × A3) (O(A2) for iterating over (ch1, ch2), and O(K × A) for knapsack) where A is equal to the number of different characters in the string which is 26.

Proof
Solution

H. Making Friends

Find the maximum value for ai + a2 × n - i - 1 for all i < 2 × n - i - 1.
Complexity per test-case: O(N).

Solution

I. Split the Number

The minimum difference is either 0 or 1, splitting x equally over the n parts giving each part , now we have as left-over which is less than n, we can split them over the last parts. note that if equals 0 then there is no strictly positive solution so print  - 1.
Complexity per test-case: O(N).

Solution

J. T-Shirts Dilemma

Let ai, bi and vi be the ith bit of a, b and v correspondingly, and let's iterate from the most significant bit to the least significant bit, and each time check the following:

  • If vi = 1 and ai = bi = 0 then we can take the segment segment [a, b] as their cost will be less than v.
  • If vi = 0 and ai = bi = 1 then we can't take any number as the cost of every number is greater than v.
  • If vi = ai = bi = 0 we don't have enough information so we go to the next bit.
  • If vi = ai = bi = 1 we don't have enough information here either, so we set ai, bi and vi to 0 and go to the next bit (note that flipping the bits won't affect the answer because the OR of any set of numbers before and after the flipping will remain the same expect for the flipped bit, but that bit is the same for v and all numbers in [a, b], so it doesn't matter).
  • If vi = ai = 0 and bi = 1 then we can't include any number with it's ith bit 1, let c = number with all bits after ith bit 1, and rest of bits 0, then the answer for (a, b, v) equals answer for (a, c, v), so we replace b with c and go to the next bit.
  • If vi = 1, ai = 0 and bi = 1, if all the bits to the right of the ith bit in v are 1s then we can take the segment [a, b] as our answer, else let c = number with all bits after ith bit 1, and rest of bits 0, then we can either take the segment [a, c] as an answer or take the answer of the problem (c + 1, b, v) with setting the ith bit for all the numbers to 0 (note that we don't benefit by taking the answer of the problem (c, b, v) because c OR (c + 1) is already larger than v), we take the max of those two as our answer.

Cases where ai = 1 and bi = 0 are impossible because all the bits to the left of the ith bit are always 0 and b ≥ a. See the code below for better understanding of how the algorithm works.
Complexity per test-case: .

Solution

K. League of Demacia

Let's say that θ is the angle in which Lux will rotate clockwise, and an optimal θ is an angle which will kill the maximum number of soldiers, notice that there could be an infinite amount of optimal θs, but at least one of them will have a soldier intersecting with either the left border of the laser or the left half of the laser's base (the line intersecting with the point (0,0) and having length z), note that this is true because if we take any optimal θ we can keep increasing θ until such soldier appears.
Now let's for each soldier figure out if he can be the chosen one, this can be done by calculating the corresponding θ and counting the number of dead soldiers for such a θ.
let d be the distance of the soldier to the point (0, 0), if the soldier will intersect with the base, otherwise he will intersect with the left border (imaging a circle at (0, 0) with radius ).
Let be vector that resembles the left side of the base and be a vector from (0, 0) to our soldier, if then (in terms of direction), else we can get by rotating by θ 2 counter clockwise, .

A soldier is dead if he's to the right of (can be checked using cross product) and he's inside the laser beam (| after normalizing , if it's not clear read more about the dot product as this is a classical usage of it).
Complexity per test-case: O(N2).
Solution

L. Lazy Teacher

The problem can be solved using Dynamic Programming, the DP state is dp[i][j][p1][p2][p3][p4][p5] which i and j means at the ith row and jth column and the colors of the last 5 cells are pi where p1 is the earliest one and p5 is the latest one, that is because only the last 5 cells colored will affect the result if we move column by column making sure no two adjacent cells have the same color.
Now pi values can reach 105 each, but some different coloring patterns have the same result, for example if you have the colors 5, 9, 5, 2, 1 for p1, p2, p3, p4, p5 the answer for dp[i][j][p1][p2][p3][p4][p5] will be the same for the colors 0, 1, 0, 2, 3 which means mapping the colors to smaller numbers in a smart way will make: p1 < 1, p2 < 2, p3 < 3, p4 < 4, p5 < 5 while giving the same result, this way we only need to try colors from 0 to 4, and the rest from 5 to k will give the same answer as they will have the same mapping so in the DP we only need to iterate over min(k, n + 1) colors.
Complexity per test-case: O(N2 × M × N!), the extra N is from the loop inside the DP.

Solution

M.Greedy Pirate

It's obvious that we need to traverse the maximum number of edges. Let's denote u as the starting node and v as the finishing node, the only edges that we can not traverse are the edges on the path directed from v to u, so we need to calculate the sum of coins on this path and then subtract it from the total number of coins on all edges. Calculating the sum of coins on a path can be done easily by finding the lowest common ancestor(LCA) of node u and node v, the answer will be: cost1(u) - cost1(lca) + cost2(v) - cost2(lca) where cost1(x) is the cost of the directed path from the root to x and cost2(x) is the cost of the directed path from x to the root which can be pre-calculated with a DFS.
Complexity per test-case: .

Solution

Read more »

 
 
 
 
  • Vote: I like it  
  • +66
  • Vote: I do not like it  

By Vendetta., 3 weeks ago, In English,

Hello Codeforces,

I would like to invite you all to participate in the 2018 ACM Amman Collegiate Programming Contest (AmmanCPC 2018). The contest was originally held on the 5th of May, and it will launch in Codeforces Gym on Saturday, 2 June 2018 10:00 UTC.

The problems were prepared by Kudo. (Ali Fadel), Vendetta. (Ibraheem Tuffaha) and The-Legend (Abdulmajeed Alzoubi).

Thanks to Flerynn (Yosef Darwish), M.Dawwas (Mohammad Abu Dawwas), abo_od303 (Abdalrhman Ali) and Qumair (Fares Obaid) for sharing the ideas of four problems, to Motarack (Motasem AL-Kayed), abo_od303 (Abdalrhman Ali) and SAFWAN.K (Safwan Olaimat) for testing some of the problems and to Ownography (Eyad Hajja) for reviewing problem statements.

Also a big thanks to Um_nik (Alex Danilyuk) for sharing the solution idea for a problem and to Hasan0540 (Hasan Alhamsh) and justHusam (Husam Musleh) for the contest wouldn't have been possible without their help. :)

The duration of the contest is 5 hours, and the registration will be open 6 hours before the start of the contest.

Good luck for everyone, and I wish you all Accepted solutions.

UPD: Tutorial

Read more »

 
 
 
 
  • Vote: I like it  
  • +76
  • Vote: I do not like it  

By Vendetta., history, 2 months ago, In English,

A. Will he Die?

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5

Vendetta. solution: https://ideone.com/N8WC9O
justHusam solution: https://ideone.com/oAPb42
Complexity: O(N) for pre-calculating factorials and per test case for the multiplicative inverse.

B. Ran and the Lock Code

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/VNyo8h
justHusam solution: https://ideone.com/KChjCF
Complexity: per test case.

C. Professor Agasa Lab

Hint 1
Hint 2

Vendetta. solution: https://ideone.com/Vz5u8p
Complexity: for pre-calculating totient and O(1) per test case.
justHusam solution 1: https://ideone.com/yXLv7v
justHusam solution 2: https://ideone.com/s4EdLm

D. Help Conan

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/g6gcKd
Complexity: O(2N × N) per test case.
Complexity: O(2N × M) for the other slower solution per test case.
justHusam solution: https://ideone.com/uXfZUV (A bit different solution)

E. Rescue Haibara

Hint 1

Vendetta. solution: https://ideone.com/bF0axw
justHusam solution: https://ideone.com/LxK1PD
Complexity: O(N) per test case.

F. Median and Queries

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/3EZ1SY
Complexity: per test case: O(N2 × Max(Ai)) for construction and O(Max(Ai)) per query.
justHusam solution: https://ideone.com/WEkeVH
Complexity: per test case: O(N2 × Max(Ai)) for construction and per query.

G. Preparing for Exams

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/yKYgb9
justHusam solution 1: https://ideone.com/u8xofZ
justHusam solution 2: https://ideone.com/XNvyX9
Complexity: per test case since sqrt(x) complexity is .

H. Genta Game

Hint 1

Vendetta. solution: https://ideone.com/C6X94O
justHusam solution: https://ideone.com/YYrF7f
Complexity: O(1) per query.

I. UEFA Champions League

Hint 1

Vendetta. solution: https://ideone.com/NWtBvZ
justHusam solution: https://ideone.com/c7m35z
Complexity: O(1) per test case.

J. Gin Passwords

Hint 1
Hint 2

Vendetta. solution: https://ideone.com/bLV0UI
Complexity: O(Max(gn)) per test case where gn is the nth prime gap.

K. Conan and Scoreboard

Hint 1

Vendetta. solution: https://ideone.com/0bLR7c
Complexity: per test case.
justHusam solution: https://ideone.com/aBKduB
Complexity: per test case.

Read more »

 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

By Vendetta., history, 9 months ago, In English,

A. Subarrays Beauty

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/PL7s1U
Vendetta. solution: https://ideone.com/23iukT
Complexity: O(Nlog(Max(Ai))).

B. Array Reconstructing

Hint 1

justHusam solution: https://ideone.com/IDqwCe
Complexity: O(N).

C. Large Summation

Hint 1
Hint 2

justHusam solution: https://ideone.com/1mSW7q
Vendetta. solution: https://ideone.com/V2wqJT
Complexity: O(NLog(N)).

D. Counting Test

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/BbGc7w
Complexity: O(26N + Q).

E. Game of Dice

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/pFtGym
Vendetta. solution: https://ideone.com/udraup
Complexity: .
Note: O(6N) gives TLE because 614 is approximately 78 × 109.

F. Strings and Queries

Hint 1
Hint 2
Hint 3

Sparse Table with Hashing solution: https://ideone.com/iVZNHd (Running Time: 1621 ms)
Segment Tree with Hashing solution: https://ideone.com/UPsA6o (Running Time: 2042 ms)
Complexity: O(NL2 + NLog(N) + Q(L + Log(N))).
Sparse Table with Trie solution: https://ideone.com/pn4haB (Running Time: 1716 ms)
Complexity: O(NL2 + NLog(N) + NL + QL).
Note: You don't need to worry about collision in hashing since you don't need to use at all, the max hash value will be 430 which is approximately 1018 which fits into long long.

G. Magical Indices

Hint 1
Hint 2

justHusam solution: https://ideone.com/9SzqJb
Complexity: O(N).

H. Corrupted Images

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/wS5TPl
Complexity: O(NM).

I. The Crazy Jumper

Solution 1
Solution 2

justHusam solutions:
BFS: https://ideone.com/P2yACH
DP top-down: https://ideone.com/UnBst5
DP buttom-up: https://ideone.com/ysugUh
Complexity: O(N).

J. The Hell Boy

Solution 1
Solution 2

Vendetta. solutions:
Math: https://ideone.com/rYmHOD
DP: https://ideone.com/IDWlkQ
Complexity: O(N).

K. Palindromes Building

Hint 1
Hint 2
Hint 3

justHusam next_permutation solution: https://ideone.com/zaXvKc
Complexity: .
Note: O(N!) gives TLE because 20! is approximately 2.4 × 1018.
Vendetta. math solution: https://ideone.com/0BNI2r
Complexity: O(N).

Read more »

 
 
 
 
  • Vote: I like it  
  • +32
  • Vote: I do not like it