D3C0d3r's blog

How to approach array operation based question
By D3C0d3r, history, 16 months ago, In English

Hi everyone I'm practicing cp and always get some Special type of question where they ask to solve a question Related to array where they say u r given an array and can perform some operation like chose 2 index and do this and can repeat some number of time... I think u get the idea what I'm talking about... Can anyone tell me how to approach this kind of question since brute force always very expensive. Please I'm waiting for some lovely responses ....

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

Comments Comments (1)
| Write comment?
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  1. Yes, bruteforcing is expensive, but it can give you some insight on small cases.
  2. Using pen and paper (or if you're lazy to find some paper laying around, notepad and mspaint works) always helps.
  3. Thinking such tasks like constructive tasks can help. What will you do if the task asks not only for the ideal state, but also for the process to reach that state as well? This situation can happen anytime, and thinking about it like this helps you a lot.
  4. Optimization is not always greedy. For example, on that round where a Div.2C got *2000 (#840, I guess?), the task required you to think around the trivial cases — you had to think about cases where we temporarily perturb away from the ideal solution, and then enhance from there. (There is a metaheuristic method based on this idea called "Simulated Annealing" — though not very important in CP most of the time) Not all optimization tasks are greedy (well, almost never is a task greedy if we were tackling real-life problems instead of CP), remember!
→ Reply