My submission: link
I ran this code on codeblocks and it gives 8(correct) for input=>612220032 18 and codeforces shows 7 for it. Why?
You will be given a string of characters between ‘a’ to ‘j’ and a list of M pair of characters, u and v. You can perform the following operation.
First you have to choose a pair of characters, u and v from the given list. Then, you can replace a character u in the given string with v. After the replacement the new string will be your given string.
You have to output whether you can rearrange the characters in the given string in non-decreasing order by performing this operation any number of times.
INPUT: First line contains an integer T denotes the number of test cases. Each test case starts with a string of length N. Following line contains an integer M denotes the number of pairs of characters. Each of the following M lines contain two characters u and v. Here, 1 ≤ T ≤ 100, 1 ≤ N ≤ 10000, 0 ≤ M ≤ 500, ‘a’ ≤ u, v ≤ ‘j’.
OUTPUT: For each test case, you have to print ‘YES’ (without quotes) if the given string can be rearranged in non-decreasing order, otherwise print ‘NO’.
I don't understand why my code is getting wrong?
My approach to making the string non-decreasing as much as possible.
Can anyone please help me to fix my code for this problem or tell me a good approach to solve this problem?
*Now the submit option for this problem is disabled. It will be better if someone comes up with proof of his/her solution.:)
Solution 1(TLE): https://codeforces.com/contest/978/submission/98839909
Solution 2(AC): https://codeforces.com/contest/978/submission/98859922
Here, in solution 1, I used 3 unordered map and getting TLE but when I used 2 unordered map on solution 2 it gets AC. Why this happened while unordered map searches, inserts, and deletes elements in O(1)?
Problem statement: A little girl whose name is Anne Spetring likes to play the following game. She draws a circle on paper. Then she draws another one and connects it to the first cicrle by a line. Then she draws another and connects it to one of the first two circles by a line. She continues this way until she has n circles drawn and each one connected to one of the previously drawn circles. Her circles never intersect and lines never cross. Finally, she numbers the circles from 1 to n in some random order.
How many different pictures can she draw that contain exactly n circles? Two pictures are different if one of them has a line connecting circle number i to circle number j, and the other picture does not.
INPUT: The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 100).
OUTPUT: For each test case, output one line containing ‘Case #x:’ followed by X, where X is the remainder after dividing the answer by 2000000011.
My logic: example: n=3, then 1-2-3, 1-3-2, 2-1-3 ('-' means line connecting circles) these 3 different pictures can be drawn. According to my observation, for n=4, it will be 12 different pictures. This way I find that answer will be (n!/2)%2000000011;
I want to know, why my logic is not correct(got WA), what is the formula to solve this problem and why it will work?
Today I puzzled to find out the value of log2((2^59)-1). Here, (2^59)-1 = 576460752303423487. We know that the value of log2(4)=2, log2(3)=1.58496 and log2(576460752303423488)=59 but why log2(576460752303423487)=59 when log2(x)=y and x=2^y. This happens not only for (2^59)-1 but also for other values.
(I searched about it on google but couldn't find out the reason behind this.)
Problem link : lightoj 1028
My solution : link
AC solution : link
Here my approach was to find number of divisors by doing prime factorization. I used sieve.. algo to find prime up to 10^6 and this ac solution approach also almost same as my solution but my solution gets TLE.
Time limits for the question : 2s
My solution takes 2.286s and the ac solution above takes only 0.359s.
My question is, how this big change happened?(though both solutions are almost same.)