С Новым Годом всех! Итак, встречайте очередной раунд от синего :)
<copy-pasted-part>
Привет! В 09.01.2019 17:35 (Московское время) начнётся Codeforces Round 531 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</copy-pasted-part>
UPD1:
Поздравляем победителей:
Место | Участник | Задач решено | Штраф |
---|---|---|---|
1 | Jester | 6 | 196 |
2 | eneas | 6 | 224 |
3 | Nutella3000 | 6 | 267 |
4 | pedulia | 6 | 288 |
5 | I_love_albeXL | 6 | 297 |
Поздравляем лучших взломщиков:
Место | Участник | Число взломов |
---|---|---|
1 | ______-__________-______ | 299:-99 |
2 | im0qianqian | 100:-3 |
3 | greencis | 97:-23 |
4 | minhson | 52:-2 |
5 | MarcosK | 35 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
Задача | Участник | Штраф |
---|---|---|
A | IQOver20 | 0:01 |
B | ThankGodItsFriday | 0:05 |
C | VorivaN | 0:05 |
D | GiveMeAGirlFriend | 0:16 |
E | EremKa | 0:21 |
F | RedDreamer102 | 0:43 |
UPD2: Разбор опубликован!
UPD3: Я также забыл поблагодарить eddy1021 за помощь в тестировании раунда.
I was a bit surprised when I saw the black MikeMirzayanov lol
upd: I mean I am used to the magic MikeMirzayanov
He is white...
deep message ._.
Why his ears are white?
cause im a programmer not a graphist
Dont be racist nigga
u are white. Don't tell me u wrote that with a black pen cuz it is still offensive roflan
When u write a question of this kind in English u put the verb in the second position. It's common knowledge. It also sounds really odd. come'on! Pls don't call me a grammar nazi lmao
a PROgrammar nazi
Gold.
Man, at first sight I thought you were Radewoosh who changed his handle or something.
That dp though xD
Заранее спасибо за еще один замечательный контест!
Good luck to everyone <3 !!
Good luck to everyone <3 !!
I think CODEFORCES loves me! Whatever comment(or reply) I make (I tried many kinds. Contributed, Made memes, Helped people etc.), always get dozens of upvotes. I'm really happy about it. I want to keep contribute.
17.35 (MSK) for contests is really inconvenient time for all who works in the office )
See you guys at expert. I wish..
I didnt like first div3s but I think it evolved and now there some good problems init
I changed my rank with magic, it will be rated for me?
6 or 7?
Oh no... "copy-pasted-part" is reaching another level. People will make memes with it (probably). Then it will die. Although it makes me laugh when I see a round begining and starting with it, stop overusing it. It will die :(
Кто такой славик?
Узнаешь во время раунда)
I am using magic, hope so after this contest, without magic my color still there!!!!
OMG, Mr vovuh, when did u become blue? (( so sad... Is it because u are tired of session?
I wish u fast uprate
Well, in last two rounds I had really bad luck and missed too many easy key ideas because of my brain (idk what's wrong with it) and because I didn't participate in any contests after NEERC at all. So I forget how to solve problems fast
Lol. I thought you used the 'color changer' to get blue.
"You will be given 6 or 7 problems and 2 hours to solve them."
Can we assume that or as bitwise OR? 6|7 = 7
Actually, because of precedence of operators, it is: (given 6) | (7 problems) = 69. So today we will have 69.
Задача С:
Мент, чего тебе надо?! ... Че те надо у меня дома? ... Дверь мне запили!
смешно, с меня плюсяндрий
Feeling like gotta explain the reference in task C to English speaking participants.
It is about a Russian video where policemen broke into an insane man's flat, by breaking his door. He was kind of surprised by that. He also appears to be very concerned and upset about that and wants them to repair the door and leave.
Here's the video (NSFW to anyone who knows Russian): https://www.youtube.com/watch?v=pJTSfvtM8iY
It made me laugh so hard, I wasted 10 minutes of my time on that. Well done, Vovuh! (how to tag a user btw?)
to tag a user: press "user" in the right of spacebar at the top of a message
тоже узнали отсылку в задаче С?
The problems are in appropriate difficulty for div3 contest,thanks.
A today : 899C - Dividing the numbers
не подскажете как решать задачу F?
Можно построить взвешенный граф на n вершинах. Вершины соответствуют строкам, между двумя вершинами проведем ребро весом k, если все разности (поточечные) больше или равны k и k — наименьшее.
Теперь рассмотрим граф и метрику в нем: наименьшее ребро на пути
Теперь в этом графе посчитаем динамику dp[mask][start][finish] — это длина наименьшего пути из start в finish из вершин, лежащих в mask
Зная динамику, несложно понять ответ
спасибо!
I'd love to see the look on this guys face after he got WA on this test I specifically crafted just for the similar solutions (48143945) :D
if(m==69) return 0;
Submitted F successfully at 1:59:20 ... Phew!!!
How to prove A?
You can construct the solution for x from solution of (x-4)
Base cases: n = 0 => ans = 0, n = 1 => ans = 1, n = 2 => ans = 1, n = 3 => ans = 0
Suppose you have numbers x, x + 1, x + 2 and x + 3. Then you can take x and x + 3 to the first set, x + 1 and x + 2 to the second set and the difference between their sums will be 0. So you can take n modulo 4 and just solve it manually.
The summation from 1 to n is n*(n+1)/2, let it be S, if S is even we can straight away divide the array into two subsets such that, the sum for both the subsets are equal, thus giving a minimum of 0, in the case of S being odd, since the division will not happen equally, the difference between the sum of two partitions will be at least 1, since the difference will be caused by any two numbers which are consecutive in nature.
Thank you! I solved it but didn't know why it worked tho :D
This argument isn't thorough. I agree that the optimal difference will be equal to the parity of the sum, but it's not guaranteed we can achieve that.
For example, if your array is [2, 4, 8], the sum is 14, but the best possible division is [2, 4] and [8], which has an absolute difference of 2. It's important to prove that the optimum division can be achieved for the set [1, 2, 3, ..., n]. I proved this using the same logic as Vovuh above.
(48141727) why this solution for problem E is wrong? what is testcase 32?
You could try this test case: 1 1 2 2
Hi! Please help me with problem F. Thankyou.
After some precalculations, one can do bitmask DP to find the maximum answer
My recurrence relation was DP[mask][first line][last line]
Thank you! Unfortunately, I could not solve this during the contest :(
Для тех, кто не понял отсылки из задачи С. (Осторожно,присутствует нецензурная лексика)
Hello mister Vovuh. First things fist, thanks for the support that you've shown to us with these rounds but i think this was a bit messed up.
Problem A was ok, but i don't quite enjoy these "intuition" type problems because when i saw it i was like : "yes, that got to be the solution", without proving it.
Problems C and D was really good, altough the 10^100 statement was a bit unclear (infinite number of turns worked as well :p)
But gosh, problem B was a nightmare and it seemed terrible tbh, like i think that excluding the case where max_appearance of a number < k would have made it a perfect 1000-1200 B problem. C was easier than B.
I didn't have time to think on E or F, but my guess is E was solved using DP but F i dunno
Thanks for the round yet again! Waiting for that editorial.
Haha, I actually think difficulties worked out surprisingly well. When I solved C (it was B at the time), I said Vovuh it's really hard for B (and for C, tbh). He told me the less complicated solution, but still. After that E was added and I felt it was even easier than C. And it turned out, Vovuh was about right about all the difficulties (considering B had hard to understand statement).
I got C really quick but i don't know if my solution was optimal. I still think C was a better B. Now i tried an easy O(n^2) solution for B and it worked....During the contest i was so sure it wouldn't work that i didn't even try it. Pff, in my country, the complexity, time limit and things matter so much, i wouldn't even think about these types of solutions.
could anyone explain problem F?i have no idea about it,thanks.
After some precalculations, one can do bitmask DP to find the maximum answer 48133701
My recurrence relation was DP[mask][first line][last line]
You could write a backtracking with randomized order. Solution
Hi, Could anybody help me what is wrong in my solution for problem D Solution
Thanks!
it is because your code make more changes than the minimum.see my code
why this solution on A, didn't get TLE while its running a for loop of n, where n can be as large as 2e9?
Compiler optimizations
can you explain more please? do the compiler translate this kind of stuff like for loops calculating sum of numbers 1 to n, or similar things into an o(1) pre-process refrencing?
Compiler optimizes simple stuff and makes them O(1). Given that CF is very fast, such solutions will pass system tests too
It's not O(1). It's O(N), however, the operations done in the loop are very simple and C++ is very fast in those situations. It's possible that the compiler does some optimizations like loop unrolling, but it's still O(N).
So his solution has a loop of size 2 × 109 which the compiler optimizes for him. And he overflows 32-bit integer which does not matter since we're only interested in the last bit.
I cannot understand, why this Div.3 was about 2 times harder than last Div.2, and even others
i am agree with you for problem b.but others are not really hard.
Problem B was terrible and F was too hard for Div.3 imo Others were right
Problem B is not that terrible if you think in the right way. It's pretty easy to check if there is a way to give them a color or not. To choose the colors you can, sort the values, iterate through them and give them an increasing color using modulo.
In Open Hacking Phase, If I hack someone's solution, How will it effect my ranking. Also, Can someone explain the role of penalty.
If you hack someone's solution, you (may) climb 1 place. Your ranking will increase(or decrease, in case you get hacked).
Penalty is meant to separate contestants with the same amount of problems solved.
Can someone explain,How penalty is calculated ?
Sum of times in which you get accepted + 10 minutes * amount of wrong submissions
Aren't they the same?
48146681 48149357
Oops, doesnt seem right 265918 :think:
Thanks for nice problems, vovuh!
Too bad I couldn't translate my solution for F 48149115 from python to C++ in time (got it accepted late by several minutes with 48154003) :'c
By the way, I know that Codeforces community mostly code in C++, but wouldn't it be better if there were different TLs for different languages, as on HackerRank?
I understand that such a change requires a lot of resources (both human time and hardware) and, probably, is not in the priority queue of Codeforces' developers (or have a low priority).
I also haven't searched Codeforces for the discussion of this idea, so maybe there is already a consensus that such a change won't be introduced, (in this case I kindly ask you not to dovnvote my comment as duplicate), but otherwise it can be food for thought for the amazing Codeforces team.
this would give an advantage to python coders, because coding in python may take less time than coding the same solution in c++ because of built in functions, simplifications, etc;
First, in order to use something you should know about it, and I think that it is a good idea to reward any such knowledge.
Second, all less or more advanced C++ contest programmers have a lot of pre-written code that somewhat equalize the powers. Not to mention that there is a lot more code online implementing different algorithms in C++ (e-maxx is a nice example) than in Python.
By the way, writing Python code is not always easier than writing C++ code.
Those time limits are incredibly difficult to get right — HackerRank has many problems where writing a suboptimal solution in a slower language actually nets you more points, which is pretty counter-intuitive. This system, while harsh to slower languages, minimizes the work testers / setters have to do and has fewer slow solutions unexpectedly pass.
In "Baekjoon Online Judge", Korea's biggest online judge, we can submit in about 40 (Not quite sure the exact number. Different compiler version counted.) different languages and they all get different time and memory bonuses. For example, if C++ solution has TL x second and ML y MB, all python solutions will judged with TL (3x+2) second and ML (2y+32) MB. Kotlin Native solution will be judged with same TL with C++ and (y+16) MB ML.
This is great for python coders and most of JAVA coders. However, this had also made countless problems too. There are a lot of problems which something like in C++ you'll get TL with naive solution but with python you can actually fit the naive solution.
To solve this problem, community members make harder datas or even "temporarily change the TL/ML bonus only for that question". This actually happens a lot. Then the system rejudges every single solution submitted for that problem — which is possible because it is online judge, not a competitive programming platform, and There are only 1/4 problems there.
Baekjoon Online Judge holds Competitive Programming contests like codeforces gym, and to avoid these problems some setters just ignore the BOJ basic policy and make sure that the contest will ignore TL/ML bonuses (and it is allowed for setter to do so).
I believe it is not only extremely difficult in terms of resources, it may have some unintended results which in Codeforces it will be harder to fix.
Can someone tell me the error in this? I don't see any difference between my output and the answer for Testcase #6 (as far it's visible on screen). Submission
Maybe I am missing smth obvious, but can you explain me why you don't
one--
here:It looks like you are using
one
after this loop, and therefore it should have a correct value.Can someone help me with problem B?The verdict says its wrong on test case 1 which is 4 2 1 2 2 3 my code has given output NO but on my laptop its running correctly. i really am confused about this..i checked others (successful)code as well the logic is same as mine. what is really shocking to me is how my code is giving a different out put on my pc and different on codeforces. the link is herethis
Second for loop "i" is reaching the number 5001 and checking if (hash[i] > k), while the maximum index of that array is 5000 as you defined it. the index is out of bound , so it is calculating the wrong number and flagging it. it works on some compilers and on others it doesn't. fixing this should let you pass the first test.
From line 16 to 27: you are traversing the variable i from 0 to 5001, which caused a certain undefined behavior / memory violation since element
hash[5001]
didn't exist.Yeah got it thanks!!Totally overlooked it and i dont know why my compiler didnt give a wrong output.
The name of the problem type said it all — "undefined behaviors". Thus, different compilers might behave differently, sometimes correct, sometimes not. One assurance you can make for yourself is to test your solution on "Custom invocations" tab of Codeforces.
It's undefined behaviour, happens on your second
for
when you accesshash[5001]
I saw an accepted code for the problem 'A' in which he/she uses a loop to calculate counter.LOL.I thought to hack it but then normal test cases are also of that order and the program passed for it as well. I have no idea.
https://codeforces.com/contest/1102/submission/48130657
48157132 — what am I doing wrong? :(
You cannot simply divide the answer by 2 in the last line, since such division might not work.
For example: if the true answer before dividing is 998244354, if you divide its modulo, your output will be 0 instead of expected 499122177.
To do this, you'll need to multiply your answer by modular inverse of 2 by modulo 998244353. Remember to take the remainder of the product again (since obviously there is a high chance that it might exceed 998244353).
Thank you so much! You're amazing :)
Неизвестный вердикт по взломам 521664 и 521671.
Решение тестера упало с TLE из-за
unordered_map
:( P.S. Сейчас должно быть нормальноНу, бывает :)
How to solve F?
DP+Bitmasking. DP states are mask,last row,starting row.Here mask represents which rows are selected and cannot be selected again.Starting row represents the first row and last row represents the row of previous position.
Can you elaborate more ?
We will use 0-index array, so row index are from 0 to n - 1, column index are from 0 to m - 1.
For each choice, to calculate the acceptable of table we need to calculate minimum of |ai, j - ai - 1, j| and |ax, k - ay, k - 1| where x and y is first row and last row. So we realize DP state should have first row and last row.
Assume we have a DP state (x, y) and we want to add a row z behind row y. Then we want to make sure row z doesn't appear in above state. So we should add a binary state which tells you which rows are used, because number of rows is small. Then the DP state is (x, y, p) (1 ≤ x, y ≤ n, 1 ≤ p < 2n). We call it fx, y, p.
If we let fx, y, p be minimum of |ai, j - ai - 1, j| and |ax, k - ay, k - 1| of a table with state (x, y, p), it would be impossible to calculate fx, z, q depends on fx, y, p. In fact, fx, y, p should only be minimum of |ai, j - ai - 1, j| of table with state (x, y, p), and minimum of |ax, k - ay, k - 1| can be calculated later.
For each pair (x, z), we iterate all states (x, y, p) which bit x and y are represented in p, while z is not, and fx, y, p exists (has been calculated). Then p' = p + 2z and f(x, z, p') = max(f(x, z, p'), min(f(x, y, p), min(|ay, i - az, i|))). Result is min(fx, y, 2n - 1, min(|ax, k - ay, k - 1|)). We can see from the formula above that if fx, y, p has been calculated, then x and y must be represented in p, so we don't need to check x and y.
To initialize DP state, we assign all value to - 1, to show that these value hasn't been calulated.The only value we know is fi, i, 2i and we should assign them to ∞ (notice our DP formular). When n = 1, f1, 1, 1 = ∞, but it doesn't matter because we can iterate in last step to calculate result, since 2 ≤ nm.
I want to warn you of iteration order. We should iterate the binary state first to get correct answer. It seems to give us correct order of DP. I haven't figured out why iterating x and y before p could give wrong answer. I think it due to the way we treat which DP value is calculated.
Thank you :)
why we can't do using only DP states mask and last row.
I want to be an expert in this round :D
Контест был крутым!!! Скоро нутелой стану)
My solution for E:
1) We will start filling array b from the left as we know b[1]=0, we can either increment this 0 in the next element in b array or not (as stated in the third condition)
2) if we think about the second condition (if a[i]=a[j] --> b[i]=b[j]), we notice that not only b[i]=b[j], but also all b[i]=b[k] ; such that i<=k<=j, as we cant decrement as we move from left to right. Let's call elements from index i to j 'connected component'.
Consider this example:
1 2 3 1 3 2 10 10 10
b[1]=b[4]=0 (first & second condition), so if we have b[3]=1, then the third condition is violated
The solution depends mainly on the number of these 'connected components' that must have the same value in array b, in the previous example we have 2 components. First one is: (1 2 3 1 3 2) , Second one: (10 10 10)
So how many ways are possible? Thinking of it like for every position we can increment or stay constant (2 choices). Then, the answer is just 2^(CNT-1), not 2^(CNT) as we can't increment in the first connected component, it must be 0.
Remember to use mod, correctly count number of connected components.
My submission link: https://codeforces.com/contest/1102/submission/48158289
Can anyone share your idea of problem D? Thanks :)
Basically we count the 0's 1's and 2's.
they should all equal X = (the string length) / 3;
if not then we swap these depending on the best lexicographical outcome.
if the 0's are more than X then we need to swap some 0's to 1's or 2's, and the best way for lexicographical order is to swap the last 0's from the string because the 0's on the left assure a smaller lexicographical string, if we are missing both 1's and 2's we swap the 1's first because the 1's also assure lower value, after that we swap to 2's , else we just swap the number that is lower than X.
if the 1's are more than X then we swap the first 1's with 0's -**IF (0's are missing)** — and then swap the last 1's with 2's — IF (2's are missing).
if the 2's are ore than X then we swap the first 2's with 0's — IF (0's are missing) - and then NEXT first 2's with 1's — IF (1's are missing) .
I'm too lazy for write the proof, my solution use a greedy approach, i put the numbers in order (0, 1, 2) of course if is necessary to put them (cnt(#i) < n/3), and can be generalized for k digits instead of three. 48136350
what is the problem with this solution : https://codeforces.com/contest/1102/submission/48159076 or even this : https://codeforces.com/contest/1102/submission/48143613
what i am doing is giving first k elements color 1 to k then storing the max value given to elements in a list l3 , i.e if i give 2 1's 1 , 2 then i store the higher value + 1 , 3 in my l3 . L3 contains sort of hashes for no. of distinct elements. Then i just cyclicly update values from i to k , 1 to i-1
I guess Mr. vovuh purposely gave weak testcases in B. Array K-Coloring. This is bad, users are not given to chance to improve during the contests. They solve and move forward.
B has a simple solution, I(and probably the problemsetters too) don't get why people tend to overcomplicate things for problems like A and B which can be solved with naive solutions most of the times.
For example, even though I obviously know how to solve B in O(n log n), it wasn't needed in this case, and O(5000^2) works fine enough and it's simple to write.
Also, in the end, no matter how strong the initial tests are, they are still pretests so fails can come at any problem
Oh yes, I made weak tests in purpose! Of course! OMG... How this thought comes into your head?
You just said
B was easy to understand
?It's only the problem of weak testcases, not incorrect problem statement. Thus, it's your fault that your solution got hacked or failed system test. Practice more, and try to map out every possible case within your mind.
I am getting a runtime error (exit code 3) on test 5 for problem B.
https://codeforces.com/contest/1102/submission/48162017
Can someone tell me where the error is caused? The testcase isn't being shown completely since it's too big. I considered a vector of sets and tried to insert the numbers and stored the equivalent locations in l.
Line 61 in b.at(j)
Thank you for your reply. I checked the value of j with the watch(x) function #define-d and saw j's range is [0,k-1]. b is a vector of size k, so b.at(j) should be ok, I think. I'm not able to find out what exactly is going wrong. Can you please explain?
I tried it on my computer with 5000 200 and 5000 random numbers and it worked, I didn't get a runtime error
Try:
Today's problemset : A B A B B D
What do I get for one successful hack?
Что я получу за один успешный хак?
Hello, for this submission (48133245), I think it outputs a redundant character at the same time after outputting the answer. It passes the test point. I am not sure whether this submission is correct or incorrect, or checker does not solve this problem completely.
Thank you!
I guess that's a null-character, and the checker probably ignored it or considered it as a whitespace.
Do we have system testing? Run all hacking test to all competitors?
I think we have
Okay. We had :)
Yesterday's contest : ABABBD
When will the ratings change?
Yeah, Im Expert now xD :D
What happened to good ol' editorials?
I think, it would be a great idea if blue/purple/orange/red guys that solved all problems during the contest will write editorials. I mean, for div3 and div2 contests, there are a lot of people who could do that. For div3, even I can write an acceptable editorial.
It's also hard for vovuh to write every editorial, it's really exhausting. Moreover, writing editorials will increase your contribution (if someone is interested in it).
Could anyone give me a solution for problem B?? It was terrible
https://codeforces.com/contest/1102/submission/48132783 I put first k colours to the first k numbers. Then I start iterating over remaining elements and create variable cur initialised with 1 and check if 1 hasnt been used for the same number before by using hash. If it isnt simply put cur in the answer for that element. Else increase cur.If cur>=k at any time answer as false.
In problem E..submission made in C++14 using unordered_map gives tle..
https://codeforces.com/contest/1102/submission/48176297
while same submission using map gives correct verdict
https://codeforces.com/contest/1102/submission/48176416
Is there any way to know when to use map and when to use unordered map as in both cases pretest are passed!
You just need to understand what each of those data structures do.
unordered_map
implememts a hash table and, as such, it takes contsant time per operation on average BUT linear time in the worst-case.Cleverly designed anti-hash tests can be conceived to force the worst-case scenario (and this is very likely to happen with 12-hour open hacking). There are some tricks you can do to get around that though (you can find countless threads about this on codeforces).
map
on the other hand implements a BST and, as such, will run in logarithmic time in both average and worst case scenarios.Maybe it'll get away with hashhack.48279914
Anything wrong with the standings?
My contests in profile says my rank is 14 and the current standings says it's 6th.
What's going on? :P What Abracadabra is that? xD
Remember that only the trusted participants of the third division will be included in the official standings table.
Take a look at the link to see the criteria for "trusted participants". There might be users, which are still eligible to have this contest as rated, but do not fulfill the "trusted participants" criteria.
Thanks AkiLotus for your response. I'm quoting the important part collected from that link if anyone's interested to know as well.
It seems like the statement for problem C isn't available anymore
48184426 I am getting TLE on testcase 48 of problem E. Can anyone point out what can I do to improve it?
You are using an unordered map. Either change it to a map or randomize the key(example by taking xor with a random number generated using high resolution clock) in unordered map to avoid anti hash tests.
See the comment above for more information : https://codeforces.com/blog/entry/64379?#comment-483358
This blog explains it very well — https://codeforces.com/blog/entry/62393
Why the problem E is "Time limit exceeded on test 48" if i used "unordered_map", but code is right if i used "map".